Selection sort

Selection sort

Computer Science and Programming 

  • Develop and test i)an iterative2) a recursive implementation of Selection sort.This sorting algorithm works by repeatedly finding the smallest number in a list and placing it in the first place, and then sorting rest of the list in the same way. 

Example of how Selection sort works (From the slides):

Example of  theinput/output in the program: 

A = [75 , 30 , 9 , 14  , 1 , 18]

A_sorted = Selection_sort(A, 0, len(A))

print(“The sorted list is:”, A_sorted)

iteration 1: 1 , 30 , 9 , 14  , 75 , 18

iteration 2: 1 , 9, 30 , 14  , 75 , 18

iteration 3: 1 , 9, 14 , 30  , 75 , 18

iteration 4: 1 , 9, 14 , 18 , 75 , 30

iteration 5: 1 , 9, 14 , 18 , 30 , 75 

The sorted list is : 1 , 9, 14 , 18 , 30 , 75                  

  • i) Write a sorting algorithm for a list that is based on the following concept:

First element of the list is picked as a base.

Start from the element after the base (second element) to compare:

Create two new lists.

List1 (green) consisting of elements less than OR equal to the base.

List2 (blue) containing elements greater than the base.

The base will be added to the end of the List1.

The final sorted list is simply sorted List1 followed by sorted List2.

You require to writetwo functions:

# returns a list containing all elements in List less than or equal to base

deffindleft (List, base)

# returns a list containing all elements in List greater than base

deffindright (List, base)

  1. ii) Develop a recursive implementation of This algorithm.

Example of how the algorithm works:

A = [15  , 30 , 9 , 14  , 1 , 18]

[9, 14 , 1 ,  15] [30,18]

[ 1 , 9 ][ 14 ,15 ]          [ 18 ,30]

[1][9] [14] [15][18] [30]

[ 1  ,  9 ]   [14 ,  15]     [ 18  ,  30 ]

[ 1 ,  9 ,  14  ,  15 ]

[1 ,  9 ,  14  ,  15 , 18 ,  30 ]

Example of  theinput/output in the program: 

A = [15 , 30 , 9 , 14  , 1 , 18]

A_sorted = q2_sort(A, 0, len(A))

print(“The sorted list is:”, A_sorted)

base= 15List1 = [9, 14, 1, 15]List2 = [30, 18] base= 9List1 = [1, 9]List2 = [14, 15]  base= 1List1 = [1]List2 = [9] base= 14List1 = [14]List2 = [15] base= 30List1 = [18, 30]List2 = [] base= 18List1 = [18]List2 = [30] 

The sorted list is :[1, 9, 14, 15, 18, 30]

  • Compute the time taken by each of these 3 algorithms (iterative selection sort, recursive selection sort and question 2) to sort 100 and 1000 random numbers between 1 and 1000. Import random module for generating random numbers.

Example of computing time taken for binary search function on: 

importtime
start = time.time()        # take start time
binar(inputList_100, target)  # run binary search on inputList
end = time.time()          # take end time
print(“Runtime of Binary Search is: ” + (end – start) + ” sec”)     Solution   q2  q2Sort.py  

# recursive sorting function

def q2Sort(arr):

iflen(arr)<=1:

returnarr

base = arr[0]

green = findLeft(arr,base)

blue=findRight(arr,base)

green.append(base)

print()

print(“base= {:d}”.format(base))

print(“List1 =”,green)

print(“List2 =”,blue)

if(len(green)>1 and len(green)<len(arr)):

green = q2Sort(green)

if(len(blue)>1 and len(blue)<len(arr)):

blue = q2Sort(blue)

returngreen+blue

# findLeft and findRight

deffindLeft(arr,base):

green=[]

for i in range(1,len(arr)):

if(arr[i]<=base):

green.append(arr[i])

return green

deffindRight(arr,base):

blue=[]

for i in range(1,len(arr)):

if(arr[i]>base):

blue.append(arr[i])

return blue

# function to print the sorted list

defprintArr(a,i):

if(i==len(a)):

print(“The sorted list is : “,end=””)

else:

print(“iteration {:d}:”.format(i),end=” “)

for j in range(0,len(a)-1):

print(a[j],end=” , “)

print(a[j+1])

def main():

test = [4,4]

test = q2Sort(test)

print()

printArr(test,len(test))

main()

   selRec.py   

# recursiveselectionsort

defselectionSortRec(arr,i,it):

if(i==len(arr)-1):

returnarr

j = min(arr,i)

if(j!=i):

temp = arr[j]

arr[j] = arr[i]

arr[i] = temp

it = it+1

printArr(arr,it)

arr = selectionSortRec(arr,i+1,it)

returnarr

#function to print array in current iteration

defprintArr(a,i):

if(i==len(a)):

print(“The sorted list is : “,end=””)

else:

print(“iteration {:d}:”.format(i),end=” “)

for j in range(0,len(a)-1):

print(a[j],end=” , “)

print(a[j+1])

# function to find minimum element in array

def min(a,j):

min=a[j]

index=j

for i in range(j,len(a)):

if(a[i]<min):

min = a[i]

index =i

return index

def main():

test  = [5,3,8,2,1,4,5,2]

test = selectionSortRec(test,0,0)

printArr(test,len(test))

main()

    q3   q2SortTest.py  

def q2Sort(arr):

iflen(arr)<=1:

returnarr

base = arr[0]

green = findLeft(arr,base)

blue=findRight(arr,base)

green.append(base)

if(len(green)>1 and len(green)<len(arr)):

green = q2Sort(green)

if(len(blue)>1 and len(blue)<len(arr)):

blue = q2Sort(blue)

returngreen+blue

# findLeft and findRight

deffindLeft(arr,base):

green=[]

for i in range(1,len(arr)):

if(arr[i]<=base):

green.append(arr[i])

return green

deffindRight(arr,base):

blue=[]

for i in range(1,len(arr)):

if(arr[i]>base):

blue.append(arr[i])

return blue

  selRecTest.py  

defselectionSortRec(arr,i):

if(i==len(arr)-1):

returnarr

j = min(arr,i)

if(j!=i):

temp = arr[j]

arr[j] = arr[i]

arr[i] = temp

arr = selectionSortRec(arr,i+1)

returnarr

# function to find minimum element in array

def min(a,j):

min=a[j]

index=j

for i in range(j,len(a)):

if(a[i]<min):

min = a[i]

index =i

return index

   sortTest.py  

importselRecTest

import q2SortTest

import time

import random

import sys

defnewList(i):

arr=[]

for j in range(i):

arr.append(random.randint(1,i))

returnarr

def main():

print()

inputList_100= newList(100)

start = time.time()

selRecTest.selectionSortRec(inputList_100,0)

end = time.time()

print(“Runtime of Selective Search for size 100 is: {:f} sec”.format(end-start))

start1 = time.time()

q2SortTest.q2Sort(inputList_100)

end1 = time.time()

print(“Runtime of q2 Search for size 100 is: {:f} sec”.format(end1-start1))

print()

inputList_1000= newList(1000)

start2 = time.time()

selRecTest.selectionSortRec(inputList_1000,0)

end2 = time.time()

print(“Runtime of Selective Search for size 1000 is: {:f} sec”.format(end2-start2))

start3 = time.time()

q2SortTest.q2Sort(inputList_1000)

end3 = time.time()

print(“Runtime of q2 Search for size 1000 is: {:f} sec”.format(end3-start3))

sys.setrecursionlimit(10000)

main()