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

added my shell sort exercise solution code#91

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

Open
RohanSaxena2020 wants to merge11 commits intocodebasics:master
base:master
Choose a base branch
Loading
fromRohanSaxena2020:master
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
Show all changes
11 commits
Select commitHold shift + click to select a range
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
105 changes: 105 additions & 0 deletions1.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
# ### Binary Search Exercise
# 1. When I try to find number 5 in below list using binary search, it doesn't work and returns me -1 index. Why is that?

# ```numbers = [1,4,6,9,10,5,7]```

# This is because the array is not sorted in order from lowest to highest.
# Once it splits the first time, it starts looking in the [1,4,6] range and doesn't find 5

# 1. Find index of all the occurances of a number from sorted list

# ```
# numbers = [1,4,6,9,11,15,15,15,17,21,34,34,56]
# number_to_find = 15
# ```
# This should return 5,6,7 as indices containing number 15 in the array

from util import time_it

@time_it
def linear_search(numbers_list, number_to_find):
for index, element in enumerate(numbers_list):
if element == number_to_find:
return index
return -1

@time_it
def binary_search(numbers_list, number_to_find):
left_index = 0
right_index = len(numbers_list) - 1
mid_index = 0

while left_index <= right_index:
mid_index = (left_index + right_index) // 2
mid_number = numbers_list[mid_index]

if mid_number == number_to_find:
return mid_index

if mid_number < number_to_find:
left_index = mid_index + 1
else:
right_index = mid_index - 1

return -1

def binary_search_recursive(numbers_list, number_to_find, left_index, right_index):
if right_index < left_index:
return -1

mid_index = (left_index + right_index) // 2
if mid_index >= len(numbers_list) or mid_index < 0:
return -1

mid_number = numbers_list[mid_index]

if mid_number == number_to_find:
return mid_index

if mid_number < number_to_find:
left_index = mid_index + 1
else:
right_index = mid_index - 1

return binary_search_recursive(numbers_list, number_to_find, left_index, right_index)

#this should run the binary search, find the index, and then recursively run the search on both the right and left side
def binary_search_multiple(numbers_list, number_to_find):

index = binary_search(numbers_list,number_to_find)
result_indices = [index]

# find all indices on the left
i = index - 1
while i>=0:
if numbers_list[i] == numbers_list[index]:
result_indices.append(i)
else:
break
i = i-1

# find all indices on the right
i = index + 1
while i<len(numbers_list):
if numbers_list[i] == numbers_list[index]:
result_indices.append(i)
else:
break
i = i+1

return sorted(result_indices)

numbers_list = [12, 15, 17, 19, 21, 21, 21, 21, 24, 45, 67]
number_to_find = 21

index = binary_search_multiple(numbers_list, number_to_find)
print(f"Number found at index {index} using binary search")

numbers = [1,4,6,9,11,15,15,15,15,17,21,34,34,56]
number_to_find = 15

index = binary_search_multiple(numbers, number_to_find)
print(f"Number found at index {index} using binary search")

#Lesson: I was approaching it wrong. If something isn't working, scratch the approach.
#Lesson #2: Try the simplest solution first. Although in this case it's a bit ugly since you're just doing a linear search after your binary search
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)
Loading
[8]ページ先頭
©2009-2025 Movatter.jp