Selection sort

Selection sorting technique in python and C

Selection sort 

It is one of the sorting techniques. In this technique, we repeatedly sort the array by finding the minimum element in the array and swapping the minimum element with the element in the first index, the second minimum element with the element in the second index, and so on. By repeating the procedure we will be having two sub arrays, a sorted array, and an unsorted array. At the end, finishing the above procedure till the last index we'll be having a single sub array that is the sorted array.

Explanation :

Selection sort

Look at the above example, where we have the array [5, 3, 4, 1, 6, 2] to be sorted.

At First, we have to find the first minimal element in the array, the minimum element is 1. Now swap it with the element at index 0, which is 5. After swapping 1 and 5, the array will be [1, 3, 4, 5, 6, 2].

Then swap the second smallest element (2)  with the element at index 1 ( 3), the array will be

[1, 2, 4, 5, 6, 3].

Swapping the third smallest element (3) with the element at index 2 (4), the resultant array will be [1, 2, 3, 5, 6, 4].

Swapping the fourth smallest element (4) with the element at index 3 (5), the array will be [1, 2, 3, 4, 6, 5].

Now swapping the fifth smallest element (5) with the element at index 4 (6), the resultant array will be [1, 2, 3, 4, 5, 6].

Thus the final array is sorted.

Procedure :

1. Start.

2. Get the elements of the array from the user.

3. Loop (0 to length of array)

    => find the nth smallest number.

    => Swap the nth smallest number with the element at nth position.

5. Print the array.

6. End.

Code :

Python 

#Selection sort

#Getting elements of the list from user separated by space

l = list(map(int, input().split()))

for i in range(len(l)):

#initiate minimum element

min_elt = l[i]

#initiate minimum index

min_idx = i

#find the nth smallest element

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

if(l[j]<min_elt):

min_elt = l[j]

min_idx = j

#swap minimum element with the corresponding index

temp = l[i]

l[i] = min_elt

l[min_idx] = temp

print(l)

C

#include <stdio.h>

int main(){

    int count,arr[50],min_idx,temp;

    printf("Enter the number of elements in the array : ");

    scanf("%d",&count);

    printf("Enter array elements : ");

    for(int i=0;i<count;i++){

        scanf("%d",&arr[i]);

    }

    for(int i=0;i<count;i++){

        min_idx=i;

        for(int j=i+1;j<count;j++){

            if(arr[j]<arr[min_idx]){

                min_idx=j;

            }

        }

        temp=arr[i];

        arr[i]=arr[min_idx];

        arr[min_idx]=temp;

        for(int k=0;k<count;k++){

            printf("%d ",arr[k]);

        }

        printf("\n");

    }

}

Time complexity :

• Best case - O(N²)
• Average case - O(N²)
• Worst case - O(N²)

Space complexity : 

• Auxiliary space - O(1)