kaksha.dev

---

Selection Sort

Selection Sort works on the principle of iterating through the array, find the smallest element to the right of the current index and exchange it with the element at the current index. At any given moment the array at the left of the current index is already sorted. This article gives a visual representation of selection sort in action.

Psuedocode

Let A = {A₁, A₂, …., A_N} where N ∈ Z

FOR i = 0 TO N-1 do:
    minIndex = i
    FOR j = i+1 to N do:
        IF A[j] < A[min] do:
            min = j
        END IF
    END FOR
    
    temp = A[i]
    A[i] = A[minIndex]
    A[minIndex] = temp
END FOR

Complexity

On average, Selection Sort does N²/2 comparsions and N swaps. Hence, the runtime complexity of the program is of the order O(N²).

Measuring runtime efficiency

An experiment can be conducted to verify the runtime of the selection sort using the following steps:

1. Generate a large array of numbers of size N using the random generator function utilities in the language in which you are coding. For example, rand() and srand() functions in C stdlib library
2. Using the steps outlined in the article Measuring the efficiency of a program, measure the runtime of selection sort. Let’s denote it by $T(N)$
3. Again, generate a large array of numbers of size 2N using the same methodology as in step 1
4. Measure the runtime for sorting the new array. Let’s denote it by $T(2N)$
5. Divided the value obtained in step 4 and step 2. Verify that $\dfrac{T(2N)}{T(N)} \approx 4$

The ratio of two times is close to 4 as:

\(T(N) \propto N^2\)
\(T(N) = c_1 N^2\)

\(T(2N) \propto (2N)^2\)
\(T(2N) = c_2(2N)^2\)
\(T(2N) = 4c_2N^2\)

\(\dfrac{T(2N)}{T(N)} = \dfrac{4c_2N^2}{c_1 N^2}\)
\(\dfrac{T(2N)}{T(N)} = 4c\)

Assuming c to be small for large size inputs \(\dfrac{T(2N)}{T(N)} \approx 4\)

Sample code

Link

Bubble Sort

Bubble Sort is a comparison based sort in which each element in the input list is compared against every other element and exchanged if necessary. It is named as bubble sort as the largest elements bubbles to the end of the list.

PesudoCode

Let A = {A₁, A₂, …., A_N} where N ∈ Z

FOR i = N-1 TO 1 do:
    FOR j = 0 to i-1 do:
        IF A[j] > A[i] do:
            temp = A[j]
            A[j] = A[i]
            A[i] = temp
        END IF
    END FOR
END FOR

Complexity

Bubble sort is rarely used in practice because of its poor peformance. Irrespective of the input characterstics, there are \(\dfrac{N*(N-1)}{2}\)
comparisons making it a poor alternative compared to other sorts such as insertion sort.

Sample code

Link

Insertion Sort

Insertion Sort can be thought as of sorting a hand while playing cards where we pick one card at a time and place it in proper position in the cards already held in hand.

PesudoCode

Let A = {A₁, A₂, …., A_N} where N ∈ Z

FOR i = 1 to N-1 do:
    FOR j = i to 1 do:
        IF A[j] >= A[j-1]:
            break
        END IF
        temp = A[j]
        A[j-1] = A[j]
        A[j] = temp
    END FOR
END FOR

Complexity

For random arrays, insertion sort uses O(N²) compares and O(N²) exchanges. For already sorted arrays, there are O(N) compares and 0 exchanges making this algorithm ideal for nearly sorted or smaller arrays.

Sample code

Link