Posts /

Algo #3: Selection Sort

4 mins read ●
Twitter Facebook Google+
02 Sep 2017

Selection Sort

Sorting the data is very important for indexing and searching. A lot of sorting algorithms have been developed so far to meet the current needs of speed. One such algorithm that appeared initially for addressing the sorting problem is Selection Sort.
Like Insertion Sort, Selection Sort tends to be very slow. Both have time Big-O of O(n2), where n is the number of entries to be sorted. Both of these algorithms require a lot of computation in comparisons, and in swapping.

Working

Selection Sort works on the principle of comparing and swapping for arranging the elements. Unlike Insertion Sort, which compares adjacent entries, this algorithm selects the smallest or largest values (depending on sorting order) in a subset of the list and moves it to the front of the subset. This shifting is done by swapping the smallest or largest value with that at the front. After one element is placed at the front spot, we can say that this element is sorted. So, this element is ignored for next iteration. In a nutshell, during each iteration the subset is of size N - n, where n is the number of sorted elements in the list of N elements.

Selection Sort Animation  
Visual representation of Selection Sort.

Example

In this example, I’ll be sorting data in ascending order. For this, I’ll select the smallest value and move it to the front of the subset.
Alternatively, one can select the largest value and move it to the back of the subset. In this case, the list will be sorted from right. Ultimately, both methods yield the same result.

”|”
Separates the sorted part (on left) and unsorted part (on right)

Say we have a list of 5 values: [8, 2, 3, 9, 4]; N = 5
Step 1:
n = 0
Subset = (8, 2, 3, 9, 4)
Smallest = 2
Front = 8, hence 2 and 8 are swapped

[2, | 8, 3, 9, 4]

Step 2:
n = 1
Subset = (8, 3, 9, 4)
Smallest = 3
Front = 8, hence 3 and 8 are swapped

[2, 3, | 8, 9, 4]

Step 3:
n = 2
Subset = (8, 9, 4)
Smallest = 4
Front = 8, hence 4 and 8 are swapped

[2, 3, 4, | 8, 9]

Step 4:
n = 3
Subset = (8, 9)
Smallest = 8

Front = 8, no swap

[2, 3, 4, 8, | 9]
n = 4
Now that only one element is left, we can assume it to be sorted automatically.
[2, 3, 4, 8, 9]

Code

This function takes a list of values and returns a sorted list.

def select_sort( values ):
    n = len( values ) # no of elements
    index = 0 # location of smallest value
    for i in range( n - 1): # as the last element will already be sorted
        smallest = values[i]
        for j in range(i, n):
            if values[j] < smallest:
                index = j # index of current smallest value
        # move the smallest to the front of subset i.e., swap
        values[index], values[i] = values[i], values[index]
    return values

To see the results of this function, open link. In case of any errors, open an issue in 100 Algorithms repo.


You may also like...


Twitter Facebook Google+