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. The merge() 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
defselectsort(L):# start filling from the end of the listfor slot inrange(len(L)-1, 0, -1): positionOfMax =0# find the position of the maximum valuefor location inrange(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]= tempprint(L)return Ldefinsertsort(L):# scan every element to determined where it must be inserted# Location 0 constitutes a "sorted" list already. So begin from 1for index inrange(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 rightwhile j >=0and (L[j]> key): L[j +1]= L[j] j = j -1print(L)# end of inner while loop# update the list with the current element in consideration L[j +1]= key# end of outer for loopreturn Lalist = [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
defselectsort(alist):for i inrange(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]= tempreturn alistdefinsertsort(alist):for i inrange(len(alist)): sublist = alist[:i] key = alist.pop()# element to insertfor j inrange(len(sublist)):if key < alist[j]: alist.insert(j, key)breakelse:# insert it at the top of the sublist alist.insert(i, key)return alist
index-based insert sort
First see the video and then code! http://j.mp/insertSortVideo
defins_sort(k):for i inrange(1,len(k)): j = iwhile j >0and k[j]< k[j-1]:# swapping values and it is expensive k[j], k[j-1]= k[j-1], k[j] j = j -1return k
Pythonic versions
defselectsort(alist):for i inrange(len(alist)): smallest, idx =min( (v, i) for i, v inenumerate(alist[i:])) alist[i], alist[idx+i]= alist[idx+i], alist[i]return alistimport bisectdefinsert_sort(alist):for i inrange(len(alist)): key = alist.pop() bisect.insort(alist, key, hi=i)return alist
defselection_sortr(L):ifnot L:return [] # terminal case# select the minimum value and the index where it is located idx, v =min(enumerate(L), key=lambdae: 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:])
defqsort(L):iflen (L)<=1:return Lreturnqsort([n for n in L[1:] if n < L[0]])+\ [L[0]] +\qsort([n for n in L[1:] if n >= L[0]])
or
defqsort(L):iflen(L)<=1:return LdefsubList(pivot,op):return [elem for elem in L[1:]ifop(elem, pivot)]returnqsort(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 lesserdefqsort(L):iflen(L)<=1:return L pivot = L[0] sublist =lambdaop: [*filter(lambdanum: op(num, pivot), L[1:])]returnqsort(sublist(lesser))+ [pivot] +qsort(sublist(greater))print(qsort([3,1,4,2,5]) == [1,2,3,4,5])
and the most efficient:
import randomdefquicksort(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]returnquicksort(L)+ E +quicksort(G)
Improved version of lambda code (without using filter):
from operator import ge, ltdefqsort(L,first=True):iflen(L)<=1:return L L = L[:]if first else L pivot = L.pop() sublist =lambdaop: [n for n in L ifop(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)
defmergesort(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 piecemergesort(nums1)mergesort(nums2)# merge the sorted pieces back into original listmerge(nums1, nums2, nums)defmerge(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 +1else: lst3[i3]= lst2[i2] i2 = i2 +1 i3 = i3 +1# avoid `extend`, as it will not do in-placewhile i1 < n1: lst3[i3]= lst1[i1] i1 = i1 +1 i3 = i3 +1while i2 < n2: lst3[i3]= lst2[i2] i2 = i2 +1 i3 = i3 +1print("Interim (nums):", lst3)
defswap(arr,x,y): mem = arr[x] arr[x]= arr[y] arr[y]= memdefqsort(ar,start,end):# base caseif 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 inrange(start,end): elem = ar[i]if elem <= pivot:# move lesser elements to the left sideswap(ar,i,ind) ind +=1else:# leave greater elements as-ispassswap(ar,ind,end)# swap in the pivot elementprint(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 arn =int(input())ar = [int(x)for x ininput().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, lambdax: print(x), [n]).start()
Read the analysis here - http://j.mp/sleepSortGeek