Selection Sort Using Divide and Conquer

Selection Sort-

Selection sort is one of the easiest approaches to sorting.
It is inspired from the way in which we sort things out in day to day life.
It is an in-place sorting algorithm because it uses no auxiliary data structures while sorting.

How Selection Sort Works?

Consider the following elements are to be sorted in ascending order using selection sort-

6, 2, 11, 7, 5

Selection sort works as-

It finds the first smallest element (2).
It swaps it with the first element of the unordered list.
It finds the second smallest element (5).
It swaps it with the second element of the unordered list.
Similarly, it continues to sort the given elements.

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11

Selection Sort Algorithm-

Let A be an array with n elements. Then, selection sort algorithm used for sorting is as follows-

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

{

   index = i;

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

   {

      if(A[j] < A[index])

      index = j;

   }

   temp = A[i];

   A[i] = A[index];

   A[index] = temp;

}

Here,

i = variable to traverse the array A
index = variable to store the index of minimum element
j = variable to traverse the unsorted sub-array
temp = temporary variable used for swapping

Selection Sort Example-

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

The above selection sort algorithm works as illustrated below-

Step-01: For i = 0

Step-02: For i = 1

Step-03: For i = 2

Step-04: For i = 3

Step-05: For i = 4

Loop gets terminated as ‘i’ becomes 4.

The state of array after the loops are finished is as shown-

With each loop cycle,

The minimum element in unsorted sub-array is selected.
It is then placed at the correct location in the sorted sub-array until array A is completely sorted.

Time Complexity Analysis-

Selection sort algorithm consists of two nested loops.
Owing to the two nested loops, it has O(n²) time complexity.

	Time Complexity
Best Case	n²
Average Case	n²
Worst Case	n²

Space Complexity Analysis-

Selection sort is an in-place algorithm.
It performs all computation in the original array and no other array is used.
Hence, the space complexity works out to be O(1).

Important Notes-

Selection sort is not a very efficient algorithm when data sets are large.
This is indicated by the average and worst case complexities.
Selection sort uses minimum number of swap operations O(n) among all the sorting algorithms.

To gain better understanding about Selection Sort Algorithm,

Watch this Video Lecture

Next Article- Bubble Sort

Other Popular Sorting Algorithms-

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Tag: Selection Sort Using Divide and Conquer

Selection Sort Algorithm | Example | Time Complexity