Sorting( Selection Sort, Insertion Sort )

 Sorting

Insertion sort:

  It is a very simple sorting algorithm in which the sorted array (or list) is built one element at a time.

 Insertion sort works similar to the sorting of playing cards in hands. It is assumed that the first card is already sorted in the card game, and then we select an unsorted card. If the selected unsorted card is greater than the first card, it will be placed at the right side; otherwise, it will be placed at the left side. Similarly, all unsorted cards are taken and put in their exact place

The same approach is applied in insertion sort. The idea behind the insertion sort is that first take one element, iterate it through the sorted array. Although it is simple to use, it is not appropriate for large data sets as the time complexity of insertion sort in the average case and worst case is O(n2), where n is the number of items. Insertion sort is less efficient than the other sorting algorithms like heap sort, quick sort, merge sort, etc.

 

The simple steps of achieving the insertion sort are listed as follows 

Step 1 - If the element is the first element, assume that it is already sorted. Return 1. 

Step2 - Pick the next element, and store it separately in a key. 

Step3 - Now, compare the key with all elements in the sorted array. 

Step 4 - If the element in the sorted array is smaller than the current element, then move to the next element. Else, shift greater elements in the array towards the right. 

Step 5 - Insert the value.

Step 6 - Repeat until the array is sorted.

Working of Insertion sort Algorithm:

To understand the working of the insertion sort algorithm, let's take an unsorted array. It will be easier to understand the insertion sort via an example.

Let the elements of array are

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order. So, for now, 12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along with swapping, insertion sort will also check it with all elements in the sorted array.

For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence, the sorted array remains sorted after swapping

Now, two elements in the sorted array are 12 and 25. Move forward to the next elements that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Both 12 and 8 are not sorted.

So, swap them.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that are 31 and 32.

 

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.

Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

Insertion sort complexity:

Time Complexity:

Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of insertion sort is O(n).

Average Case Complexity - It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of insertion sort is O(n2).

Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of insertion sort is O(n2).

#include <stdio.h>  

  

void insert(int a[], int n) /* function to sort an aay with insertion sort */  

{  

    int i, j, temp;  

    for (i = 1; i < n; i++) {  

        temp = a[i];  

        j = i - 1;  

  

        while(j>=0 && temp <= a[j])  /* Move the elements greater than temp to one position ahead from their current position*/  

        {    

            a[j+1] = a[j];     

            j = j-1;    

        }    

        a[j+1] = temp;    

    }  

}  

  

void printArr(int a[], int n) /* function to print the array */  

{  

    int i;  

    for (i = 0; i < n; i++)  

        printf("%d ", a[i]);  

}  

  

int main()  

{  

    int a[] = { 12, 31, 25, 8, 32, 17 };  

    int n = sizeof(a) / sizeof(a[0]);  

    printf("Before sorting array elements are - \n");  

    printArr(a, n);  

    insert(a, n);  

    printf("\nAfter sorting array elements are - \n");    

    printArr(a, n);  

  

    return 0;  

}    

Advantages of Insertion Sort

·  It is easy to implement and efficient to use on small sets of data.

·  It can be efficiently implemented on data sets that are already substantially sorted.

· It performs better than algorithms like selection sort and bubble sort. Insertion sort algorithm is simpler than shell sort, with only a small trade-off in efficiency. It is over twice as fast as the bubble sort and almost 40 per cent faster than the selection sort.

· It requires less memory space (only O(1) of additional memory space).

· It is said to be online, as it can sort a list as and when it receives new elements.

****************************************************

SELECTION SORT

Selection sort is generally used for sorting files with very large objects (records) and small keys.

In selection sort, the first smallest element is selected from the unsorted array and placed at the first position. After that second smallest element is selected and placed in the second position. The process continues until the array is entirely sorted.

Selection sort is generally used when -

• A small array is to be sorted
• Swapping cost doesn't matter
• It is compulsory to check all elements

 SMALLEST (arr, i, n, pos) 

Step 1: [INITIALIZE] SET SMALL = arr[i] 

Step 2: [INITIALIZE] SET pos = i  

Step 3: Repeat for j = i+1 to n 

if (SMALL > arr[j]) 

     SET SMALL = arr[j] 

SET pos = j 

[END OF if] 

[END OF LOOP] 

Step 4: RETURN pos  

SELECTION SORT(arr, n)    

Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 

Step 2: CALL SMALLEST(arr, i, n, pos) 

Step 3: SWAP arr[i] with arr[pos] 

[END OF LOOP] 

Step 4: EXIT 

Working of Selection sort Algorithm

Now, let's see the working of the Selection sort Algorithm.

To understand the working of the Selection sort algorithm, let's take an unsorted array. It will be easier to understand the Selection sort via an example.

Let the elements of array are -

Now, for the first position in the sorted array, the entire array is to be scanned sequentially.

At present, 12 is stored at the first position, after searching the entire array, it is found that 8 is the smallest value.

So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the sorted array.

For the second position, where 29 is stored presently, we again sequentially scan the rest of the items of unsorted array. After scanning, we find that 12 is the second lowest element in the array that should be appeared at second position.

Now, swap 29 with 12. After the second iteration, 12 will appear at the second position in the sorted array. So, after two iterations, the two smallest values are placed at the beginning in a sorted way.

The same process is applied to the rest of the array elements. Now, we are showing a pictorial representation of the entire sorting process.

Now, the array is completely sorted.

 

Selection sort complexity 

Time Complexity 

Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of selection sort is O(n2).

 

Average Case Complexity - It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of selection sort is O(n2).

 

Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of selection sort is O(n2).

#include <stdio.h>    
void selection(int arr[], int n)  
{  

    int i, j, small;  

 for (i=0;i<n-1; i++) 

    // One by one move boundary of unsorted subarray  

    {  

        small = i; //minimum element in unsorted array  

         for (j = i+1; j < n; j++)  

        if (arr[j] < arr[small])  

            small = j;  

// Swap the minimum element with the first element  

    int temp = arr[small];  

    arr[small] = arr[i];  

    arr[i] = temp;  

    }  

}  
  void printArr(int a[], int n) 

    /* function to print the array */  

{  

    int i;  

    for (i = 0; i < n; i++)  

        printf("%d ", a[i]);  

}  

 int main()  

{  

    int a[] = { 12, 31, 25, 8, 32, 17 };  

    int n = sizeof(a) / sizeof(a[0]);  

    printf("Before sorting array elements are - \n");  

    printArr(a, n);  

    selection(a, n);  

    printf("\nAfter sorting array elements are - \n");    

    printArr(a, n);  

    return 0;  

}    

Advantages of Selection Sort

 

It is simple and easy to implement.

It can be used for small data sets.

It is 60 per cent more efficient than bubble sort.

However, in case of large data sets, the efficiency of selection sort drops as compared to insertion sort.

 

**************************************