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 - added 7.py#2

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 3 commits intomasterfrom3_QuickSort
Apr 1, 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
109 changes: 109 additions & 0 deletions6.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
# # Exercise: Shell Sort

# Sort the elements of a given list using shell sort, but with a slight modification. Remove all the repeating occurances of elements while sorting.

# Traditionally, when comparing two elements in shell sort, we swap if first element is bigger than second, and do nothing otherwise.

# In this modified shell sort with duplicate removal, we will swap if first element is bigger than second, and do nothing if element is smaller, but if values are same, we will delete one of the two elements we are comparing before starting the next pass for the reduced gap.



# For example, given the unsorted list `[2, 1, 5, 7, 2, 0, 5, 1, 2, 9, 5, 8, 3]`, after sorting using shell sort without duplicates, the sorted list would be:

# ```
# [0, 1, 2, 3, 5, 7, 8, 9]
# ```

# [23,3,1,56,34]

def shell_sort(arr):
size = len(arr)
gap = size//2

while gap > 0:
for i in range(gap,size):
anchor = arr[i]
j = i
while j>=gap and arr[j-gap]>anchor:
arr[j] = arr[j-gap]
j -= gap
arr[j] = anchor
gap = gap // 2

# [23,3,1,56,34]

# def shell_sort_remove_duplicates(arr):
# size = len(arr)
# gap = size//2

# while gap > 0:
# i = gap
# while i < size:
# anchor = arr[i]
# j = i
# while j>=gap:
# if arr[j-gap] > anchor:
# arr[j] = arr[j-gap]
# elif arr[j - gap] == anchor: # If elements are the same, prepare to delete one
# del arr[j] # Delete the current element
# size -= 1 # Decrease the size because we've removed an element
# i -= 1 # Adjust i since we've shifted the array elements
# break # Exit the inner while loop since we've handled the duplicate
# else:
# break
# j -= gap
# if j != i: # Ensures that we don't reset anchor if it was deleted
# arr[j] = anchor
# i += 1
# gap = gap // 2

def shell_sort_remove_duplicates(arr):
size = len(arr)
gap = size // 2

while gap > 0:
for i in range(gap, size):
anchor = arr[i]
j = i
while j >= gap and arr[j - gap] > anchor:
arr[j] = arr[j - gap]
j -= gap

# Place anchor at its correct position
arr[j] = anchor

# After each gap reduction, remove duplicates
i = 0
while i < (size - 1):
# If duplicate found
if arr[i] == arr[i+1]:
del arr[i+1]
size -= 1 # Reduce size after deletion
else:
i += 1 # Only increase i if no deletion happened to check next element

gap = gap // 2

return arr


tests = [
[89, 78, 61, 53, 23, 21, 17, 12, 9, 7, 6, 2, 1],
[],
[1,5,8,9],
[234,3,1,56,34,12,9,12,1300],
[5]
]

# for elements in tests:
# shell_sort(elements)
# print(elements)


elements2 = [2, 1, 5, 7, 2, 0, 5, 1, 2, 9, 5, 8, 3]
shell_sort_remove_duplicates(elements2)
print(elements2)

elements = [23,12,23,1,1,1,56,34,34]
shell_sort_remove_duplicates(elements)
print(elements)
155 changes: 155 additions & 0 deletions7.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
# # Exercise: Selection Sort

# Implement a Multi-Level Sort of a given list of dictionaries based on a given sorting order.
# If user wants to sort dictionary based on First Key 'A', Then Key 'B',
# they shall pass list of keys in the order of preference as a list ['A','B'].
# Your code should be able to sort list of dictionaries for any number of keys in sorting order list.

# Using this multi-level sort, you should be able to sort any list of dictionaries based on sorting order preference

# Example:
# A single dictionary entry contains two keys 'First Name' and 'Last Name'. the list should be sorted first based on 'First Name', then based on 'Last Name', w.r.t. common/same 'First Name' entries.

# for this, one shall past sorting order of preference list [ 'First Name' , 'Last Name' ]

# For this, Given the following sequence List:

# ```
# [
# {'First Name': 'Raj', 'Last Name': 'Nayyar'},
# {'First Name': 'Suraj', 'Last Name': 'Sharma'},
# {'First Name': 'Karan', 'Last Name': 'Kumar'},
# {'First Name': 'Jade', 'Last Name': 'Canary'},
# {'First Name': 'Raj', 'Last Name': 'Thakur'},
# {'First Name': 'Raj', 'Last Name': 'Sharma'},
# {'First Name': 'Kiran', 'Last Name': 'Kamla'},
# {'First Name': 'Armaan', 'Last Name': 'Kumar'},
# {'First Name': 'Jaya', 'Last Name': 'Sharma'},
# {'First Name': 'Ingrid', 'Last Name': 'Galore'},
# {'First Name': 'Jaya', 'Last Name': 'Seth'},
# {'First Name': 'Armaan', 'Last Name': 'Dadra'},
# {'First Name': 'Ingrid', 'Last Name': 'Maverick'},
# {'First Name': 'Aahana', 'Last Name': 'Arora'}
# ]
# ```


# Your algorithm should generate sorted list:

# ```
# [
# {'First Name': 'Aahana', 'Last Name': 'Arora'}
# {'First Name': 'Armaan', 'Last Name': 'Dadra'}
# {'First Name': 'Armaan', 'Last Name': 'Kumar'}
# {'First Name': 'Ingrid', 'Last Name': 'Galore'}
# {'First Name': 'Ingrid', 'Last Name': 'Maverick'}
# {'First Name': 'Jade', 'Last Name': 'Canary'}
# {'First Name': 'Jaya', 'Last Name': 'Seth'}
# {'First Name': 'Jaya', 'Last Name': 'Sharma'}
# {'First Name': 'Karan', 'Last Name': 'Kumar'}
# {'First Name': 'Kiran', 'Last Name': 'Kamla'}
# {'First Name': 'Raj', 'Last Name': 'Nayyar'}
# {'First Name': 'Raj', 'Last Name': 'Sharma'}
# {'First Name': 'Raj', 'Last Name': 'Thakur'}
# {'First Name': 'Suraj', 'Last Name': 'Sharma'}
# ]
# ```

def selection_sort(arr):
size = len(arr)
for i in range(size-1):
min_index = i
for j in range(min_index+1,size):
if arr[j] < arr[min_index]:
min_index = j
if i != min_index:
arr[i], arr[min_index] = arr[min_index], arr[i]

# def selection_sort_multi(arr,keys):
# size = len(arr)
# # for key in keys[-1::-1]:
# # for i in range(size):
# # min_index = i
# # for j in range(i+1,size):
# # if arr[j][key] < arr[min_index][key]:
# # min_index = j
# # arr[i], arr[min_index] = arr[min_index], arr[i]
# for key in reversed(keys):
# for i in range(size):
# min_or_max_index = i
# for j in range(i+1, size):
# if arr[j][key] < arr[min_or_max_index][key]:
# min_or_max_index = j
# # Swap the found minimum element with the first element
# arr[i], arr[min_or_max_index] = arr[min_or_max_index], arr[i]

# def selection_sort_multi(elements, sort_by_list):
# for sort_by in sort_by_list[-1::-1]:
# for x in range(len(elements)):
# min_index = x
# for y in range(x, len(elements)):
# if elements[y][sort_by] < elements[min_index][sort_by]:
# min_index = y
# if x != min_index:
# elements[x], elements[min_index] = elements[min_index], elements[x]

def selection_sort_multi(arr, keys):
size = len(arr)

# Adjusted loop to clearly iterate through keys in reversed order
for key in reversed(keys):
# Selection sort adapted for multiple keys
for i in range(size):
# Initially, min_index is the starting index
min_index = i
# Find the minimum element in remaining unsorted array
for j in range(i+1, size):
# Check condition for current sorting key
if arr[j][key] < arr[min_index][key]:
min_index = j

# Swap the found minimum element with the first element
arr[i], arr[min_index] = arr[min_index], arr[i]

def multilevel_selection_sort(elements, sort_by_list):
for sort_by in sort_by_list[-1::-1]:
for x in range(len(elements)):
min_index = x
for y in range(x, len(elements)):
if elements[y][sort_by] < elements[min_index][sort_by]:
min_index = y
if x != min_index:
elements[x], elements[min_index] = elements[min_index], elements[x]

tests = [
[89, 78, 61, 53, 23, 21, 17, 12, 9, 7, 6, 2, 1],
[],
[1,5,8,9],
[234,3,1,56,34,12,9,12,1300],
[78, 12, 15, 8, 61, 53, 23, 27],
[5]
]

# for elements in tests:
# selection_sort(elements)
# print(elements)

element2 = [
{'First Name': 'Raj', 'Last Name': 'Nayyar'},
{'First Name': 'Suraj', 'Last Name': 'Sharma'},
{'First Name': 'Karan', 'Last Name': 'Kumar'},
{'First Name': 'Jade', 'Last Name': 'Canary'},
{'First Name': 'Raj', 'Last Name': 'Thakur'},
{'First Name': 'Raj', 'Last Name': 'Sharma'},
{'First Name': 'Kiran', 'Last Name': 'Kamla'},
{'First Name': 'Armaan', 'Last Name': 'Kumar'},
{'First Name': 'Jaya', 'Last Name': 'Sharma'},
{'First Name': 'Ingrid', 'Last Name': 'Galore'},
{'First Name': 'Jaya', 'Last Name': 'Seth'},
{'First Name': 'Armaan', 'Last Name': 'Dadra'},
{'First Name': 'Ingrid', 'Last Name': 'Maverick'},
{'First Name': 'Aahana', 'Last Name': 'Arora'}
]

multilevel_selection_sort(element2,['First Name','Last Name'])
print(element2)
Loading
[8]ページ先頭
©2009-2025 Movatter.jp