Each team works on assigned sorting algorithms and will give

Each team works on assigned sorting algorithms and will give demonstration and PowerPoint presentation on Nov. 16^th during lab class. Search internet for tutorials and source code in python on sorting algorithms assigned to your team. Modify the python code to count the number of comparisons and the number of swaps when sorting a random list of size n, n>=100, for example, n = 100, 1000, 10000. To test your program use a small size of n for example, n = 10, and print the list before and after sorting. Once confirmed the your program sorts correctly, try larger size of n without print the list. In your presentation, explain how do the sorting algorithms work and given their worst case and average case complexity, and include following table: Submit the source code and presentation to D2L Assignment for Team Project 1 before 11:00PM. 11/16/2016 Sorting Algorithms: Selection sort, quick sort Insertion sort, shell sort Bubble sort, merge sort Heap sort Radix sort

Solution

Selection Sort:

def selectionSort(list1):
for x in range(len(list1)-1,0,-1):
max_pos=0
for location in range(1,x+1):
if list1[location]>list1[max_pos]:
max_pos = location

temp = list1[x]
list1[x] = list1[max_pos]
list1[max_pos] = temp

list1 = [100,550,12,10,9]
selectionSort(list1)
print \"Sorted List\"
print(list1)

================================================

Output:

Sorted List
[9, 10, 12, 100, 550]

==================================================

Quck sort

def quickSort(list1):
quickSortHelper(list1,0,len(list1)-1)

def quickSortHelper(list1,left,right):
if left<right:

splitpoint = partition(list1,left,right)

quickSortHelper(list1,left,splitpoint-1)
quickSortHelper(list1,splitpoint+1,right)

def partition(list1,left,right):
pivot = list1[left]

l = left+1
r = right

done = False
while not done:

while l <= r and list1[l] <= pivot:
l = l + 1

while list1[r] >= pivot and r >= l:
r = r -1

if r < l:
done = True
else:
temp = list1[l]
list1[l] = list1[r]
list1[r] = temp

temp = list1[left]
list1[left] = list1[r]
list1[r] = temp

return r

list1 = [100,550,12,10,9]
quickSort(list1)
print(list1)

=============================================

Output:

[9, 10, 12, 100, 550]

=================================================

insertion sort:

def insertionSort(list1):
for i in range(1,len(list1)):

currentvalue = list1[i]
position = i

while position>0 and list1[position-1]>currentvalue:
list1[position]=list1[position-1]
position = position-1

list1[position]=currentvalue

list1 = [100,550,12,10,9]
insertionSort(list1)
print(list1)

===================================================

Output:

[9, 10, 12, 100, 550]

=================================================

Bubble sort:

def bubbleSort(list1):
for x in range(len(list1)-1,0,-1):
for i in range(x):
if list1[i]>list1[i+1]:
temp = list1[i]
list1[i] = list1[i+1]
list1[i+1] = temp

list1 = [100,550,12,10,9]
bubbleSort(list1)
print(list1)

======================================

Output:

[9, 10, 12, 100, 550]

====================================

def mergeSort(list1):
print(\"Splitting list \",list1)
if len(list1)>1:
mid = len(list1)//2
lefthalf = list1[:mid]
righthalf = list1[mid:]

mergeSort(lefthalf)
mergeSort(righthalf)

i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
list1[k]=lefthalf[i]
i=i+1
else:
list1[k]=righthalf[j]
j=j+1
k=k+1

while i < len(lefthalf):
list1[k]=lefthalf[i]
i=i+1
k=k+1

while j < len(righthalf):
list1[k]=righthalf[j]
j=j+1
k=k+1
print(\"Merging \",list1)

list1 = [100,550,12,10,9]
mergeSort(list1)
print(list1)

========================================

Output:

(\'Splitting list \', [100, 550, 12, 10, 9])
(\'Splitting list \', [100, 550])
(\'Splitting list \', [100])
(\'Merging \', [100])
(\'Splitting list \', [550])
(\'Merging \', [550])
(\'Merging \', [100, 550])
(\'Splitting list \', [12, 10, 9])
(\'Splitting list \', [12])
(\'Merging \', [12])
(\'Splitting list \', [10, 9])
(\'Splitting list \', [10])
(\'Merging \', [10])
(\'Splitting list \', [9])
(\'Merging \', [9])
(\'Merging \', [9, 10])
(\'Merging \', [9, 10, 12])
(\'Merging \', [9, 10, 12, 100, 550])
[9, 10, 12, 100, 550]

===========================================

Heap sort

def heapsort( list1 ):
# convert list1 to heap
length = len( list1 ) - 1
Parent = length / 2
for i in range ( Parent, -1, -1 ):
downAdjust( list1, i, length )

# flatten heap into sorted array
for i in range ( length, 0, -1 ):
if list1[0] > list1[i]:
swap( list1, 0, i )
downAdjust( list1, 0, i - 1 )


def downAdjust( list1, first, last ):
largest = 2 * first + 1
while largest <= last:
# right child exists and is larger than left child
if ( largest < last ) and ( list1[largest] < list1[largest + 1] ):
largest += 1

# right child is larger than parent
if list1[largest] > list1[first]:
swap( list1, largest, first )
# move down to largest child
first = largest;
largest = 2 * first + 1
else:
return # force exit


def swap( A, x, y ):
tmp = A[x]
A[x] = A[y]
A[y] = tmp

list1 = [100,550,12,10,9]
heapsort(list1)
print(list1)

=====================================

Output:

akshay@akshay-Inspiron-3537:~/Chegg$ python heap.py
[9, 10, 12, 100, 550]

============================================

Radix sort

def radixsort( list1 ):
div = 10
Length = False
tmp , placement = -1, 1

while not Length:
Length = True
# declare and initialize buckets
buckets = [list() for _ in range( div )]

# split list1 between lists
for i in list1:
tmp = i / placement
buckets[tmp % div].append( i )
if Length and tmp > 0:
Length = False

# empty lists into list1 array
a = 0
for b in range( div ):
buck = buckets[b]
for i in buck:
list1[a] = i
a += 1

# move to next digit
placement *= div

list1 = [100,550,12,10,9]
radixsort(list1)
print(list1)

============================================

Output:

akshay@akshay-Inspiron-3537:~/Chegg$ python radix.py
[9, 10, 12, 100, 550]