H Lecture Notes - Lecture 5: Time Complexity, Dspace, Selection Sort

• School: National Institute of Technology - NIT Manipur
• Department: Communications
• Course: H

Document Summary

The idea behind this algorithm is pretty simple. We divide the array into two parts: sorted and unsorted. The left part is sorted subarray and the right part is unsorted subarray. Initially, sorted subarray is empty and unsorted array is the complete given array. We perform the steps given below until the unsorted subarray becomes empty: Pick the minimum element from the unsorted subarray. Swap it with the leftmost element of the unsorted subarray. Now the leftmost element of unsorted subarray becomes a part (rightmost) of sorted subarray and will not be a part of unsorted subarray. This is our initial array a = [5, 2, 6, 7, 2, 1, 0, 3] We will swap a[0] and a[6] then, make a[0] part of sorted subarray. We will swap a[1] and a[5] then, make a[1] part of sorted subarray. We will swap a[2] and a[4] then, make a[2] part of sorted subarray.