What is Selection Sort in Data Structure?

Today in this article I am going to tell you about Selection Sorting Technique in Data Structure. It is another simple sorting algorithm which is best suited for small lists and is also very simple to understand. Here also like Bubble Sorting, sorting is done in multiple passes. You can also watch the video provided at the last of the page.

How Selection Sort works

Here the concept of sorting is selecting one element in each pass and move that selected element to its correct position. Pass refers to iteration though the list. So one pass indicates one iteration or scan through the list and hence ‘n’ passes indicates ‘n’ iterations through the list.




Step by Step Example

Let us suppose we have an unordered array with 7 elements and we want to sort it in ascending order (small first). Consider list A (8 6 3 1 4 5 2). Small Element is located from the list and is swapped with element at index zero and the process is repeated, repeatedly one small element is picked from the remaining unordered list and swap with next index position element. Element in bold is that small element.

Pass 1:
(8 6 3 1 4 5 2) ——————> (1 6 3 8 4 5 2), original list – from element 8 to 2, smallest element is searched and found ‘1’ . Hence swapped with element at index ‘0’, sorted list {1}

Pass 2:
(1 6 3 8 4 5 2) ——————> (1 2 3 8 4 5 6), sorted list {1 2}, next smallest element is searched from remaining unsorted list and found ‘2’, hence replaced with index ‘1’

Pass 3:
(1 2 3 8 4 5 6) ——————> (1 2 3 8 4 5 6), sorted list {1 2 3}

Pass 4:
(1 2 3 8 4 5 6) ——————> (1 2 3 4 8 5 6), sorted list {1 2 3 4}

Pass 5:
(1 2 3 4 8 5 6) ——————> (1 2 3 4 5 8 6), sorted list {1 2 3 4 5}

Pass 6:
(1 2 3 4 5 8 6) ——————> (1 2 3 4 5 6 8), sorted list {1 2 3 4 5 6}

Pass 7:
(1 2 3 4 5 6 8) ——————> (1 2 3 4 5 6 8), sorted list {1 2 3 4 5 6 8}

Performance of Selection Sort Algorithm

Its worst case , best case and average case all are equal i.e.: O(n^2)

Due to its performance complexity, it is inefficient for large lists. It is noted for its simplicity and it has performance advantages over complicated algorithms in some situations where auxiliary memory is limited.

How Selection Sort works – Watch this Video

Thank You !