Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

3 quick sort#1

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
RohanSaxena2020 merged 4 commits intomasterfrom3_QuickSort
Mar 27, 2024
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
84 changes: 84 additions & 0 deletions2.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
# ### Bubble Sort Exercise

# Modify [bubble_sort function](https://github.com/codebasics/data-structures-algorithms-python/blob/master/algorithms/2_BubbleSort/bubble_sort.py) such that it can sort following list of transactions happening in an electronic store,
# ```
# elements = [
# { 'name': 'mona', 'transaction_amount': 1000, 'device': 'iphone-10'},
# { 'name': 'dhaval', 'transaction_amount': 400, 'device': 'google pixel'},
# { 'name': 'kathy', 'transaction_amount': 200, 'device': 'vivo'},
# { 'name': 'aamir', 'transaction_amount': 800, 'device': 'iphone-8'},
# ]
# ```
# bubble_sort function should take key from a transaction record and sort the list as per that key. For example,
# ```
# bubble_sort(elements, key='transaction_amount')
# ```
# This will sort elements by transaction_amount and your sorted list will look like,
# ```
# elements = [
# { 'name': 'kathy', 'transaction_amount': 200, 'device': 'vivo'},
# { 'name': 'dhaval', 'transaction_amount': 400, 'device': 'google pixel'},
# { 'name': 'aamir', 'transaction_amount': 800, 'device': 'iphone-8'},
# { 'name': 'mona', 'transaction_amount': 1000, 'device': 'iphone-10'},
# ]
# ```
# But if you call it like this,
# ```
# bubble_sort(elements, key='name')
# ```
# output will be,
# ```
# elements = [
# { 'name': 'aamir', 'transaction_amount': 800, 'device': 'iphone-8'},
# { 'name': 'dhaval', 'transaction_amount': 400, 'device': 'google pixel'},
# { 'name': 'kathy', 'transaction_amount': 200, 'device': 'vivo'},
# { 'name': 'mona', 'transaction_amount': 1000, 'device': 'iphone-10'},
# ]
# ```

# base bubble_sort. you can use this to sort strings too
def bubble_sort(elements):
size = len(elements)

for i in range(size-1):
swapped = False
for j in range(size-1-i):
if elements[j] > elements[j+1]:
tmp = elements[j]
elements[j] = elements[j+1]
elements[j+1] = tmp
swapped = True

if not swapped:
break

def bubble_sort_by_key(elements, key):
size = len(elements)

for i in range(size-1):
swapped = False
for j in range(size-1-i):
if elements[j][key] > elements[j+1][key]:
tmp = elements[j]
elements[j] = elements[j+1]
elements[j+1] = tmp
swapped = True

if not swapped:
break


elements = [5,9,2,1,67,34,88,34]
elements = [1,2,3,4,2]
elements = ["mona", "dhaval", "aamir", "tina", "chang"]

bubble_sort(elements)
print(elements)

elements2 = [ { 'name': 'kathy', 'transaction_amount': 200, 'device': 'vivo'},
{ 'name': 'dhaval', 'transaction_amount': 400, 'device': 'google pixel'},
{ 'name': 'aamir', 'transaction_amount': 800, 'device': 'iphone-8'},
{ 'name': 'mona', 'transaction_amount': 1000, 'device': 'iphone-10'},
]
bubble_sort_by_key(elements2,key='transaction_amount')
print(elements2)
66 changes: 66 additions & 0 deletions3.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
def swap(a, b, arr):
if a!=b:
tmp = arr[a]
arr[a] = arr[b]
arr[b] = tmp

# Sorts a (portion of an) array, divides it into partitions, then sorts those
def quicksort(A, lo, hi):
if lo >= 0 and lo < hi:
lt, gt = partition(A, lo, hi) # Multiple return values
quicksort(A, lo, lt - 1)
quicksort(A, gt + 1, hi)

# Divides array into three partitions
def partition(A, lo, hi):
# Pivot value
pivot = A[(lo + hi) // 2] # Choose the middle element as the pivot (integer division)

# Lesser, equal and greater index
lt = lo
eq = lo
gt = hi

# Iterate and compare all elements with the pivot

while eq <= gt:
if A[eq] < pivot:
# Swap the elements at the equal and lesser indices
swap(eq, lt, A)
# Increase lesser index
lt += 1
# Increase equal index
eq += 1
elif A[eq] > pivot:
# Swap the elements at the equal and greater indices
swap(eq, gt, A)
# Decrease greater index
gt -= 1
else: # A[eq] == pivot
# Increase equal index
eq += 1

# Return lesser and greater indices
return lt, gt

elements = [11,9,29,7,2,15,28]
# elements = ["mona", "dhaval", "aamir", "tina", "chang"]
quicksort(elements, 0, len(elements)-1)
print(elements)

tests = [
[11,9,29,7,2,15,28],
[3, 7, 9, 11],
[25, 22, 21, 10],
[29, 15, 28],
[],
[6]
]

try:
# Your script's entry point, e.g., function calls
for elements in tests:
quicksort(elements, 0, len(elements)-1)
print(f'sorted array: {elements}')
except Exception as e:
print(f"Error occurred: {e}")
44 changes: 44 additions & 0 deletions4.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
# ### Exercise: Insertion Sort

# Compute the running median of a sequence of numbers. That is, given a stream of numbers, print out the median of the list so far on each new element.

# Recall that the median of an even-numbered list is the average of the two middle numbers in a *sorted list*.

# For example, given the sequence `[2, 1, 5, 7, 2, 0, 5]`, your algorithm should print out:

# ```
# 2
# 1.5
# 2
# 3.5
# 2
# 2
# 2
# ```

def find_median_value(elements):
if len(elements) == 1: #if the array has 1 element
return elements[0]
if len(elements) % 2 != 0: #if the array has an odd number of elements
return elements[(len(elements)//2)]
else: #if the array has an even number of elements
return ((elements[int(len(elements)/2)]+elements[int(len(elements)/2-1)])/2)

def insertion_sort(elements):
for i in range(1, len(elements)):
print(find_median_value(elements[0:i]))
anchor = elements[i]
j = i - 1
while j>=0 and anchor < elements[j]:
elements[j+1] = elements[j]
j = j - 1
elements[j+1] = anchor
print(find_median_value(elements))

# print (find_median_value([1,2,3,4,5,7,20,33,34]))
# print (find_median_value([1,2,3,4,8,7,20,33]))

elements = [2, 1, 5, 7, 2, 0, 5]
# print(elements[0:1])
insertion_sort(elements)
print(elements)
158 changes: 158 additions & 0 deletions5.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
# ### Merge Sort Exercise

# Modify [merge_sort function](https://github.com/codebasics/data-structures-algorithms-python/blob/master/algorithms/5_MergeSort/merge_sort_final.py) such that it can sort following list of athletes as per the time taken by them in the marathon,
# ```
# elements = [
# { 'name': 'vedanth', 'age': 17, 'time_hours': 1},
# { 'name': 'rajab', 'age': 12, 'time_hours': 3},
# { 'name': 'vignesh', 'age': 21, 'time_hours': 2.5},
# { 'name': 'chinmay', 'age': 24, 'time_hours': 1.5},
# ]
# ```
# merge_sort function should take key from an athlete's marathon log and sort the list as per that key. For example,
# ```
# merge_sort(elements, key='time_hours', descending=True)
# ```
# This will sort elements by time_hours and your sorted list will look like,
# ```
# elements = [
# {'name': 'rajab', 'age': 12, 'time_hours': 3},
# {'name': 'vignesh', 'age': 21, 'time_hours': 2.5},
# {'name': 'chinmay', 'age': 24, 'time_hours': 1.5},
# {'name': 'vedanth', 'age': 17, 'time_hours': 1},
# ]
# ```
# But if you call it like this,
# ```
# merge_sort(elements, key='name')
# ```
# output will be,
# ```
# elements = [
# { 'name': 'chinmay', 'age': 24, 'time_hours': 1.5},
# { 'name': 'rajab', 'age': 12, 'time_hours': 3},
# { 'name': 'vedanth', 'age': 17, 'time_hours': 1},
# { 'name': 'vignesh', 'age': 21, 'time_hours': 2.5},
# ]
# ```

# [Solution](https://github.com/codebasics/data-structures-algorithms-python/blob/master/algorithms/5_MergeSort/merge_sort_exercise_solution.py)

# def merge_sort(arr):
# if len(arr) <= 1:
# return

# mid = len(arr)//2

# left = arr[:mid]
# right = arr[mid:]

# merge_sort(left)
# merge_sort(right)

# merge_two_sorted_lists(left, right, arr)

# def merge_two_sorted_lists(a,b,arr):
# len_a = len(a)
# len_b = len(b)

# i = j = k = 0

# while i < len_a and j < len_b:
# if a[i] <= b[j]:
# arr[k] = a[i]
# i+=1
# else:
# arr[k] = b[j]
# j+=1
# k+=1

# while i < len_a:
# arr[k] = a[i]
# i+=1
# k+=1

# while j < len_b:
# arr[k] = b[j]
# j+=1
# k+=1

# def merge_two_sorted_by_key(a,b,arr,key):
# len_a = len(a)
# len_b = len(b)

# i = j = k = 0

# while i < len_a and j < len_b:
# if a[i][key] <= b[j][key]:
# arr[k] = a[i]
# i+=1
# else:
# arr[k] = b[j]
# j+=1
# k+=1

# while i < len_a:
# arr[k] = a[i]
# i+=1
# k+=1

# while j < len_b:
# arr[k] = b[j]
# j+=1
# k+=1

def merge_sort_by_key(arr, key,descending=False):
if len(arr) <= 1:
return arr

mid = len(arr)//2

left = arr[:mid]
right = arr[mid:]

left = merge_sort_by_key(left,key,descending)
right = merge_sort_by_key(right,key,descending)

return merge_two_sorted_lists_by_key(left, right,key,descending)

def merge_two_sorted_lists_by_key(a,b,key,descending):
sorted_list = []

len_a = len(a)
len_b = len(b)

i = j = 0

while i < len_a and j < len_b:
if descending:
condition = a[i][key] > b[j][key] # Note the change here for descending
else:
condition = a[i][key] <= b[j][key]

if condition:
sorted_list.append(a[i])
i += 1
else:
sorted_list.append(b[j])
j += 1

while i < len_a:
sorted_list.append(a[i])
i+=1

while j < len_b:
sorted_list.append(b[j])
j+=1

return sorted_list


elements = [
{ 'name': 'vedanth', 'age': 17, 'time_hours': 1},
{ 'name': 'rajab', 'age': 12, 'time_hours': 3},
{ 'name': 'vignesh', 'age': 21, 'time_hours': 2.5},
{ 'name': 'chinmay', 'age': 24, 'time_hours': 1.5},
]

print(merge_sort_by_key(elements,key="age",descending=False))
[8]ページ先頭
©2009-2025 Movatter.jp