Selection Sort

Selection Sort is a really easy to implement sorting algorithm, due to being inefficient on large datasets this algorithm is mostly used when memory is limited.

How

Selection sort work by having a list of numbers, it then goes through the list and finds the minimum number. When we finished looping the list we swap the founder minimum number with the current index.

As an example we take the following list:

2 9 8 3 5 6 1 0 4 7

We start at index 0, and start finding the minimal element in this sub list, which results in 0. We now swap index 0 with the index of the found minimum and get that we will swap 2 and 0 resulting into:

0 9 8 3 5 6 1 2 4 7

Now we are at index 1 (value 9), we find the minimum value again which is at index 6 (value 1), so we swap those 2

0 1 8 3 5 6 9 2 4 7

And we continue doing this until we have a sorted list:

0 1 2 3 4 5 6 7 8 9

Advantages and Disadvantages

Advantages

• Uses almost no swaps! $\Theta(n)$
• No extra space required, $O(n)$

Disadvantages

• Not Stable
• $O(n^2)$ performance
• Not adaptive

Performance

The performance analysis is really easy for selection sort, it will always perform $n^2$ because we loop the list no matter what.

|Worst Case|Average Case|Best Case| |-|-|-| |O(n2)|O(n2)|O(n2)|

Implementation

Pseudo Code

for i=0, i<arraysize
  minIdx = i

  for j=i, j<arraysize
    if v[j] < v[minIdx]
      minIdx = j

  // swap
  swap(v[i], v[minIdx])

1.3.4.2 C++ Code

int minIdx;

for (int i = 0; i < v.size(); i++) {
  minIdx = i;

  for (int j = i; j < v.size(); j++) {
    if (v[j] < v[minIdx]) {
      minIdx = j;
    }
  }

  int temp = v[i];
  v[i] = v[minIdx];
  v[minIdx] = temp;
}

Benchmark

| | 100 | 1.000 | 10.000 | 100.000 | 1.000.000 |-|-|-|-|-|-| |Random Elements|3.6e-05|0.003002|0.204347|19.3981|- |Ascending Elements|3.1e-05|0.002846|0.190501|19.1111|- |Descending Elements|3.5e-05|0.002114|0.205667|20.0368|-

Conclusion

We can clearly see that selection sort is a horrible sorting algorithm, however when swaps are really expensive and the memory is limited we could consider using this algorithm.