lab8-kgashok.py
Table of Contents
Lab 8: Sorting
Sort the given list using selection sort and insertion sort.
[TOC]
Select vs Insert vs Merge vs Quick
In
selectsort, the position of the update is pre-determined, starting from the end of the list. We then go select the maximum value among the unsorted elements of the list, and swap it with the element in the pre-determined location.In
insertsort, given a key, a copy of a pre-determined element in the list, we insert it at the appropriate location after comparing it with the unsorted elements of the list.In
mergesort, a divide-and-conquer partitioning algorithm (which more often requires extra memory), the input array is divided in two halves, calls itself recursively for the two halves and then merges the two sorted halves. Themerge()function is used for merging two halves.In
quicksort, also a divide-and-conquer partitioning algorithm (lends itself to be efficiently implemented in-place without extra memory), the choice of the pivot element determines how the elements get partitioned, and calls itself recursively for the two partitions.
Solution Key
def selectsort(L):
# start filling from the end of the list
for slot in range(len(L)-1, 0, -1):
positionOfMax = 0
# find the position of the maximum value
for location in range(1, slot + 1):
if L[location] > L[positionOfMax]:
positionOfMax = location
# swap the slot with the maximum value
temp = L[slot]
L[slot] = L[positionOfMax]
L[positionOfMax] = temp
print(L)
return L
def insertsort(L):
# scan every element to determined where it must be inserted
# Location 0 constitutes a "sorted" list already. So begin from 1
for index in range(1, len(L)):
key = L[index]
# start with the immediate previous element
j = index - 1
# determine which 'j' it should be at
# meanwhile, keep shifting elements to the right
while j >= 0 and (L[j] > key):
L[j + 1] = L[j]
j = j - 1
print(L)
# end of inner while loop
# update the list with the current element in consideration
L[j + 1] = key
# end of outer for loop
return L
alist = [54,26,93,17,77,31,44,55,20]
selectsort(alist)
print(alist)
alist = [54,26,93,17,77,31,44,55,20]
insertsort(alist)
print(alist)English-like sorting code
def selectsort(alist):
for i in range(len(alist)):
sublist = alist[i:]
smallest = min(sublist)
index_of_smallest = alist.index(smallest, i)
#swap
temp = alist[index_of_smallest]
alist[index_of_smallest] = alist[i]
alist[i] = temp
return alist
def insertsort(alist):
for i in range(len(alist)):
sublist = alist[:i]
key = alist.pop() # element to insert
for j in range(len(sublist)):
if key < alist[j]:
alist.insert(j, key)
break
else:
# insert it at the top of the sublist
alist.insert(i, key)
return alistindex-based insert sort
First see the video and then code! http://j.mp/insertSortVideo
def ins_sort(k):
for i in range(1,len(k)):
j = i
while j > 0 and k[j] < k[j-1]:
# swapping values and it is expensive
k[j], k[j-1] = k[j-1], k[j]
j = j - 1
return kPythonic versions
def selectsort(alist):
for i in range(len(alist)):
smallest, idx = min(
(v, i) for i, v in enumerate(alist[i:]))
alist[i], alist[idx+i] = alist[idx+i], alist[i]
return alist
import bisect
def insert_sort(alist):
for i in range(len(alist)):
key = alist.pop()
bisect.insort(alist, key, hi=i)
return alistRelated Material
http://interactivepython.org/runestone/static/pythonds/SortSearch/TheInsertionSort.html
http://interactivepython.org/runestone/static/pythonds/SortSearch/TheSelectionSort.html
http://bit.ly/insertVisualizer - insertSort in the visualizer
3-problem series for learning/teaching insertsort
Part 1- https://www.hackerrank.com/challenges/insertionsort1
Part 2 - https://www.hackerrank.com/challenges/insertionsort2
Part 3 - https://www.hackerrank.com/challenges/correctness-invariant (fix the bug)
Recursive SelectionSort
Credits: https://code.activestate.com/recipes/576917-functional-selection-sort/#c1
def selection_sortr(L):
if not L: return [] # terminal case
# select the minimum value and the index where it is located
idx, v = min(enumerate(L), key=lambda e: e[1])
#v, idx = min((v, i) for i, v in enumerate(L))
print(v, L[:idx], L[idx+1:])
return [v] + selection_sortr(L[:idx] + L[idx+1:])Output
>> selection_sortr([1,56, 99, -1, 22, 99])
-1 [1, 56, 99] [22, 99]
1 [] [56, 99, 22, 99]
22 [56, 99] [99]
56 [] [99, 99]
99 [] [99]
99 [] []
=> [-1, 1, 22, 56, 99, 99]Visualize a slight variant of this code at https://tinyurl.com/x697cwwj
Recursive InsertionSort
import bisect
def insertion_sortr(L, nsorted=1):
if nsorted >= len(L): return L # terminal case
key = L.pop() # pre-determined location
print(key, L)
# insert key in sublist of 'nsorted' elements
bisect.insort(L, key, hi=nsorted)
return insertion_sortr(L, nsorted + 1)Output
insertion_sortr([1, 56, 99, -1, 22, 99])
99 [1, 56, 99, -1, 22]
22 [1, 99, 56, 99, -1]
-1 [1, 22, 99, 56, 99]
99 [-1, 1, 22, 99, 56]
56 [-1, 1, 22, 99, 99]
=> [-1, 1, 22, 56, 99, 99]Recursive QuickSort
http://mcsp.wartburg.edu/zelle/python/sigcse-workshop/mgp00064.html
def qsort(L):
if len (L) <= 1: return L
return qsort([n for n in L[1:] if n < L[0]]) + \
[L[0]] + \
qsort([n for n in L[1:] if n >= L[0]])or
def qsort(L):
if len(L) <= 1: return L
def subList(pivot, op):
return [elem for elem in L[1:] if op(elem, pivot)]
return qsort(subList(L[0], operator.lt)) + \
[L[0]] + \
qsort(subList(L[0], operator.ge))or using lambda and filter
from operator import ge as greater, lt as lesser
def qsort(L):
if len(L) <= 1: return L
pivot = L[0]
sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]
return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))
print(qsort([3,1,4,2,5]) == [1,2,3,4,5])and the most efficient:
import random
def quicksort(s):
len_s = len(s)
if len_s < 2:
return s
pivot = s[random.randrange(0, len_s)]
L = [x for x in s if x < pivot]
E = [x for x in s if x == pivot]
G = [x for x in s if x > pivot]
return quicksort(L) + E + quicksort(G)Improved version of lambda code (without using filter):
from operator import ge, lt
def qsort(L, first=True):
if len(L) <= 1:
return L
L = L[:] if first else L
pivot = L.pop()
sublist = lambda op: [n for n in L if op(n, pivot)]
return [*qsort(sublist(lt), False), pivot, *qsort(sublist(ge), False)]Related Material
http://bit.ly/quickSortVideoCD - a video explaining QuickSort incrementally in a CyberDojo session.
Recursive MergeSort (in-place)
def mergesort(nums):
print ("nums:", nums)
n = len(nums)
if n > 1:
# split into sublists
m = n // 2
nums1, nums2 = nums[:m], nums[m:]
# recursively sort each piece
mergesort(nums1)
mergesort(nums2)
# merge the sorted pieces back into original list
merge(nums1, nums2, nums)
def merge(lst1, lst2, lst3):
i1, i2, i3 = 0, 0, 0
n1, n2 = len(lst1), len(lst2)
print(lst1, lst2, lst3)
while i1<n1 and i2<n2:
print(i1, i2, i3)
if lst1[i1] < lst2[i2]:
lst3[i3] = lst1[i1]
i1 = i1 + 1
else:
lst3[i3] = lst2[i2]
i2 = i2 + 1
i3 = i3 + 1
# avoid `extend`, as it will not do in-place
while i1 < n1:
lst3[i3] = lst1[i1]
i1 = i1 + 1
i3 = i3 + 1
while i2 < n2:
lst3[i3] = lst2[i2]
i2 = i2 + 1
i3 = i3 + 1
print("Interim (nums):", lst3)Unit test file
from mergesort import mergesort
import unittest
import random
class Test_mergesort(unittest.TestCase):
def test_simple_lists(self):
alist = [1, 4, 5, 2, 4, 3, 10, 2, -4]
expected = sorted(alist)
mergesort(alist)
self.assertEqual(expected, alist)
def generate_random_list(self):
alist = []
for i in range (10):
x = [random.randrange(-100, 101, 1)] * random.randrange(0, 6)
alist.extend(x)
random.shuffle(alist)
# print(sorted(alist))
return alist
def test_random_list(self):
alist = self.generate_random_list()
expected = sorted(alist)
mergesort(alist)
self.assertEqual(expected, alist)
if __name__ == '__main__':
unittest.main()Recursive QuickSort, in-place
def swap(arr,x,y):
mem = arr[x]
arr[x] = arr[y]
arr[y] = mem
def qsort(ar,start,end):
# base case
if end-start <= 0:
return ar
# pivot
pivot = ar[end]
# init index for the next pivot
# which is used in the next recursive qsort calls below
ind = start
# loop less final value (pivot)
for i in range(start,end):
elem = ar[i]
if elem <= pivot:
# move lesser elements to the left side
swap(ar,i,ind)
ind += 1
else:
# leave greater elements as-is
pass
swap(ar,ind,end) # swap in the pivot element
print(ar)
# left side contains pivot, and lesser elements
ar = qsort(ar,start,ind-1)
# right side contain greater elements than pivot
ar = qsort(ar,ind+1,end)
return ar
n = int(input())
ar = [int(x) for x in input().split()]
qsort(ar,0,n-1)Related Material
http://bit.ly/quickSortVideo
What exactly does this accomplish?
from threading import Timer
l = [8, 2, 4, 6, 7, 1]
for n in l:
Timer(n, lambda x: print(x), [n]).start()Read the analysis here - http://j.mp/sleepSortGeek
Last updated