Introduction to Selection Sort

Share

Introduction

Selection sort is one in which successive elements are selected in order and placed into their proper sorted positions. Initially, the first element is considered the minimum and compared with other elements. During these comparisons, if a smaller element is found, then that is considered the new minimum. After completion of one full round, the smallest element found is swapped with the first element. This process continues till all the elements are sorted.

Working of Selection Sort

  • Set the first element as minimum
  • Compare minimum with the second element. If the second element is smaller than minimum, assign the second element as a minimum. Compare minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. The process goes on until the last element.
  • After each iteration, minimum is placed in the front of the unsorted list.
  • For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until all the elements are placed at their correct positions.

Pseudo Code

SelectionSort(A)
{
for( i = 0;i < n ;i++)
{
least=A[i];
p=i;
for ( j = i + 1;j < n ;j++)
{
if (A[j] < A[i])
least= A[j]; p=j;
}
}
swap(A[i],A[p]);
}

Complexity

Best case:O(n2)

Average Case: O(n2)

Worst case: O(n2)

Read about Bubble Sort,

Share

Leave a Reply

Your email address will not be published.

%d bloggers like this: