[Sorting] Introduction & Selection Sort

Sorting

 

Sorting is the process of converting a list of elements into ascending (or descending) order.

You may remember the importance of sorting in binary search from my previous post.

 

In the following few posts, we will be studying about the types of sorting algorithms.

 

These are some examples of (un)sorted data

(3, 9, 44, 18, 76): Not sorted

(20, 15, 10, 5, 0): Sorted into descending order

(99.87, 99.01, 67.30, 44.51): Sorted into descending order

('F', 'D', 'C', 'B', 'A',): Sorted into descending order

('chopstick', 'fork', 'knife', 'spoon'): Sorted into ascending order

('great', 'greater', 'greatest'): Sorted into ascending order

 

---

Selection Sort

 

Selection sort is a sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.

 

We will go through each index (i) starting from 0 to len(arr) - 1 and compare every indexes at the right of the index (i) to find the smallest value among the values that are smaller than arr[i] if it exists. 

Then, we swap the element at the smallest_index position and i. 

Thus, if there is no smaller element among the unsorted part, we will continue to next step without doing anything.

selection sort

selection sort gif

The implemented function in Python would be like this.

def selection_sort(arr: list[int]) -> None:
    for i in range(len(arr)):
        index_smallest = i
        
        for j in range(i + 1, len(arr)):
            if arr[index_smallest] > arr[j]: index_smallest = j
        
        arr[i], arr[index_smallest] = arr[index_smallest], arr[i]

 

We could start from the right, and sort from the right of the array.

We could also sort in descending order by looking for the largest index instead of the smallest. 

 

---

Time Complexity of Selection Sort

 

As you can guess from the fact that selection sort requires a looped traverse, it would have a comparatively large runtime complexity. 

The selection sort algorithm's runtime complexity is in fact, O(N²).

 

If the array has N elements, the outer loop (i) with execute for N - 1 times.

For each loop, there will be an average of N/2 execute of inner loop. 

So it gives N(N - 1)/2 number of comparisons, or O(N²).

 

Interpreting the fact that T(N) = O(N²), 10 times of increase of the size of the data would result in about 100 times slower operation.

 

Similar to linear search, it has relatively simple algorithm but slower execution time compared to other sorting algorithms. 

In the next post, we will look on to insertion sort algorithm.