Selection Sort

Selection sort is a relatively simple sorting algorithm. It can be used to sort the data elements within an array. To explain the algorithm I will refer to an array called array A, which contains n number of elements of a particular data type. To make the example easier to explain assume that it contains unsorted integer numbers. In order to get the array in the correct order you need to find the index of the largest element within the array. Once that number has been located it can then be swapped with the last index within the array. The algorithm then will run through the array again taking the next largest integer and swapping it into the index of [n-2]. This process will continue until the index of A[0] is reached. Below I have provided a trace of the selection sort algorithm.

Original Array: 29 10 14 37 13

After 1st swap: 29 10 14 13 37
After 2nd swap: 1310 14 29 37
After 3rd swap: 13 10 14 29 37
After 4th swap: 10 13 14 29 37

The selection sort algorithm is a simple algorithm to implement, but at times can have a relatively large time complexity. It also is an internal sorting algorithm which requires it to all be able to fit in primary memory.