FIT1045 Lecture Notes - Lecture 4: Counting Sort, Selection Sort, Hidden Surface Determination
30 May 2018
School
Department
Course
Professor
="basic"building"block"for"many"algorithms"(eg."finding"
convex"hulls"in"2D,"hidden"surface"elimination)
Methods
Divide"&"conquer
•
Brute"force
•
Heap"sort
•
Selection sort
•
Insertion sort
•
Counting sort
•
Merge"sort
•
Quick"sort
•
Input:"(unsorted)"list"of"'orderable'"elem"types)
**"lists"like"[1,'hj','0,'j']"can't"be"sorted"unless"you"
define"your"own"comparison"functn"for"diff"types"of"
objects
Output:"list"w/"same"elements"BUT"sorted"in"
increasing/decreasing"order
Selection-sort
For"list"list of"length"n,
Select"smallest"number"in"list"and"swap"with"
list[0]
1.
Select"smallest"number"between"list[1,n-1]
and"swap"with"list[1]
2.
…
3.
list = [78, 5, 33, 20]
n = len(list)
def selectionSort(aList):
min_position = 0
for index in range(n-1,0,-1):
if list[index]
< list[min_position]:
temp = list[index]
list[index] =
list[min_position]
list[min_position] = temp
index = index + 1
b = selectionSort(list)
print(b)
Insertion-sort
Pick"first"card1.
Pick"2nd"card"and"sort"it"with"1"other"card2.
Pick"3rd"card"and"sort"it"with"the"other"2"cards3.
…4.
def insertionSort(alist):
for index in range(1,len(alist)):
#assigning value being compared
currentvalue = alist[index]
position = index
while position>0 and
alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1
alist[position]=currentvalue
alist = [54,26,93,17]
insertionSort(alist)
print(alist)
Counting-sort
If"integers"not"unique,
Week$4:$Sorting
Sunday,"13"August"2017
16:14
Document Summary
= basic building block for many algorithms (eg. finding convex hulls in 2d, hidden surface elimination) ** lists like [1,"hj","0,"j"] can"t be sorted unless you define your own comparison functn for diff types of objects. Output: list w/ same elements but sorted in increasing/decreasing order. Select smallest number in list and swap with list[0] Select smallest number between list[1,n-1] and swap with list[1] 3. list = [78, 5, 33, 20] n = len(list) def selectionsort(alist): min_position = 0 for index in range(n-1,0,-1): if list[index] < list[min_position]: temp = list[index] list[index] = list[min_position] list[min_position] = temp index = index + 1. Pick 2nd card and sort it with 1 other card. Pick 3rd card and sort it with the other 2 cards. #assigning value being compared currentvalue = alist[index] position = index while position>0 and alist[position-1]>currentvalue: alist[position]=alist[position-1] position = position-1 alist[position]=currentvalue alist = [54,26,93,17] insertionsort(alist) print(alist)
