June 5, 2015 - algorithms cpp

Sorting Algorithm - Selection Sort

Xavier Geerinck

@XavierGeerinck

Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

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 CaseAverage CaseBest 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

1001.00010.000100.0001.000.000
Random Elements3.6e-050.0030020.20434719.3981-
Ascending Elements3.1e-050.0028460.19050119.1111-
Descending Elements3.5e-050.0021140.20566720.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.

Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

Xavier Geerinck © 2020

Twitter - LinkedIn