Selection Sort

• The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.

• In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

• It is repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

• The algorithm maintains two subarrays in a given array.

        1) The subarray which is already sorted.
        2) Remaining subarray which is unsorted.

Example:

        0             1            2                3           //Index

       7   4 5       2     // Values

Step 1:  set i, min=0 location and j=1st location

min / i= 0       j=   1               2                3

   7   4 5       2

Step 2: for i in N:   set min=i ie min=0

Step 3: for j in N:

compare arr[ j ]< arr[ min ]              ie arr[ 1 ]< arr[0]                            4<7                

If yes,  min=j min=1

Step 4: repeat to step 3

 compare arr[ j ]< arr[ min ]        ie arr[ 2 ]< arr[1]   5<4               

                    If yes,  min=j    

 compare arr[ j ]<arr[min]             arr[3] < arr[1]     2<4 

If yes,    min =j min=3

Step 5:  Swap the elements   arr[i], arr[min] = arr[min], arr[i]       i= 0         j=1           2           min=  3

                               2 4 5       7 

Step 6:  Repeat step 2 and 3  from min=i

                                    sorted    i/ min = 1       j=2                3

                                    2 4 5       7 

 compare arr[ j ]< arr[ min ]   ie arr[2]< arr[1]       5<4

               

If yes,  k=min k=1

compare arr[ j ]<arr[min]       arr[3] < arr[1]     7<4 

If yes,    k =min

    

             sorted    i/ min = 1       2             j=  3

                    2 4 5       7

 

Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending order

then, the worst case occurs.

Best Case Complexity: O(n2)
It occurs when the array is already sorted

Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither

ascending nor descending)

Program in Python:

L=[]
def get():
    n=int(input("Enter no of elements store in array"))
    for i in range(n):
        no=int(input("Enter no"))
        L.append(no)
def dis():
    for i in L:
        print(i,end=" ")

def sel():
    for i in range(len(L)):
        min=i
        print("\nIteration No:",i)
        for j in range(i+1,len(L)):
            if L[j]<L[min]:
                min=j
        L[i],L[min]=L[min],L[i]
        print(L,end="\n")

    j = -1  # [1,2,3,4]  
#index=(0,1,2,3)-> forward index  #(-4,-3,-2,-1)
    print("\n****Top five scores****=")
    while (j != -6):
        print(L[j], end=" ")
        j = j - 1

get()
print("****Displaying List****")
dis()
sel()