Skip to content

Instantly share code, notes, and snippets.

@YieldNull
Created September 5, 2016 11:44
Show Gist options
  • Save YieldNull/cbe70dc07f0c53c73b2478ec6b877882 to your computer and use it in GitHub Desktop.
Save YieldNull/cbe70dc07f0c53c73b2478ec6b877882 to your computer and use it in GitHub Desktop.
Sorting algorithms
#!/usr/bin/env python3
"""
Sorting algorithms
Created By YieldNull at 4/14/16
"""
def insertion_sort(lst):
for i in range(1, len(lst)):
ptr = i - 1
temp = lst[i]
while ptr >= 0 and temp < lst[ptr]:
lst[ptr + 1] = lst[ptr]
ptr -= 1
lst[ptr + 1] = temp
return lst
def selection_sort(lst):
def _min(start):
value = lst[start]
index = start
for i in range(start + 1, len(lst)):
if lst[i] < value:
value = lst[i]
index = i
return index
for i in range(len(lst) - 1):
min_index = _min(i)
if min_index != i:
lst[i], lst[min_index] = lst[min_index], lst[i]
return lst
def merge_sort(lst):
last = len(lst) - 1
def merge(left, right, count):
temp = []
end = right + count - 1 if right + count - 1 <= last else last
p_left = left
p_right = right
while p_left < right and p_right <= end:
if lst[p_left] <= lst[p_right]:
temp.append(lst[p_left])
p_left += 1
else:
temp.append(lst[p_right])
p_right += 1
if p_left <= right - 1:
temp += lst[p_left:right]
if p_right <= end:
temp += lst[p_right: end + 1]
for i in range(len(temp)):
lst[left + i] = temp[i]
count = 1
while count < len(lst):
left = 0
right = count
while right <= last:
merge(left, right, count)
left += count * 2
right += count * 2
count *= 2
return lst
def heap_sort(lst):
def heapify():
for start in range(((len(lst) - 1) // 2), -1, -1):
shift_down(start, len(lst) - 1)
def shift_down(start, end):
if start * 2 + 1 > end:
return
left_index = start * 2 + 1
right_index = start * 2 + 2
parent = lst[start]
left = lst[left_index]
right = lst[right_index] if right_index <= end else left - 1
if parent < max(left, right):
if left > right:
lst[start], lst[left_index] = lst[left_index], lst[start]
shift_down(left_index, end)
else:
lst[start], lst[right_index] = lst[right_index], lst[start]
shift_down(right_index, end)
heapify()
for end in range(len(lst) - 1, 0, -1):
lst[0], lst[end] = lst[end], lst[0]
shift_down(0, end - 1)
return lst
def quick_sort(lst):
def sort(left, right):
if left < right:
p_left = left
p_right = right + 1
while p_left < p_right:
p_left += 1
p_right -= 1
while p_left <= right and lst[p_left] < lst[left]:
p_left += 1
while p_right >= left and lst[p_right] > lst[left]:
p_right -= 1
if p_left < p_right:
lst[p_left], lst[p_right] = lst[p_right], lst[p_left]
lst[left], lst[p_right] = lst[p_right], lst[left]
sort(left, p_right - 1)
sort(p_right + 1, right)
sort(0, len(lst) - 1)
return lst
def bubble_sort(lst):
for end in range(len(lst) - 1, 0, -1):
swapped = False
for i in range(end):
if lst[i] > lst[i + 1]:
lst[i], lst[i + 1] = lst[i + 1], lst[i]
swapped = True
if not swapped:
break
return lst
def shell_sort(lst):
gap = len(lst) // 2
while gap >= 1:
for start in range(gap):
for i in range(start, len(lst), gap):
# insertion
ptr = i - gap
temp = lst[i]
while ptr >= 0 and temp < lst[ptr]:
lst[ptr + gap] = lst[ptr]
ptr -= gap
lst[ptr + gap] = temp
gap //= 2
return lst
if __name__ == '__main__':
import random
lst = [random.randrange(1000) for i in range(100)]
insertion = lst.copy()
insertion = insertion_sort(insertion)
selection = lst.copy()
selection = selection_sort(selection)
bubble = lst.copy()
bubble = bubble_sort(bubble)
merge = lst.copy()
merge = merge_sort(merge)
heap = lst.copy()
heap = heap_sort(heap)
quick = lst.copy()
quick = quick_sort(quick)
shell = lst.copy()
shell = shell_sort(shell)
out_format = '{:>16} : {}'
print(out_format.format('origin list', lst))
print(out_format.format('python library', sorted(lst)))
print(out_format.format('insertion sort', insertion))
print(out_format.format('selection sort', selection))
print(out_format.format('bubble sort', bubble))
print(out_format.format('merge sort', merge))
print(out_format.format('heap sort', heap))
print(out_format.format('quick sort', quick))
print(out_format.format('shell sort', shell))
print(out_format.format('identical', insertion == selection == bubble == merge == heap == quick == shell))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment