Selection sort

Selection sort is a simple sorting algorithm with asymptotic complexity $O(n^{2})$ . In comparison with other quadratic sorting algorithms it almost always outperforms bubble sort, but it is usually slower than insertion sort. The advantage of selection sort over algorithms with $O(n \\cdot \\log{n})$ (quicksort, heapsort, merge sort) asymptotic complexity is it's constant memory complexity.

Description

The idea of selection sort is, that if we sort the array from largest to smallest element, than the first element of the sorted array will be the one with the largest value. Second will be the largest element of the rest of the array. Third will be the largest element of the new rest of the array (initial array without the two already sorted elements)...

So we can iteratively select the largest element of the (reduced) array, swap it with the first element and than reduce the problem size by 1 (sort only the rest of the array). When there remains only one element to sort, the algorithm terminates.

Visualization

Example

(3 2 8 7 6) // initial array, sort the elements in descending order
(3 2 8 7 6) // 8 is the largest value, swap it with 3 at index 0
(8 2 3 7 6) // 7 is the largest value, swap it with 2 at index 1
(8 7 3 2 6) // 6 is the largest value, swap it with 3 at index 2
(8 7 6 2 3) // 3 is the largest value, swap it with 2 at index 3
(8 7 6 3 2) // sorted

Selection sort - visualization

Code

function selectionSort(array a)
    for i in 0 -> a.length - 2 do
        maxIndex = i
        for j in (i + 1) -> (a.length - 1) do
            if a[j] > a[maxIndex]
                maxIndex = j
        swap(a[i], a[maxIndex])

/**
 * Selection sort (descending order)
 * @param array array to be sorted
 */
 public static void selectionSort(int[] array) {
     for (int i = 0; i < array.length - 1; i++) {
         int maxIndex = i;
         for (int j = i + 1; j < array.length; j++) {
             if (array[j] > array[maxIndex]) maxIndex = j;
         }
         int tmp = array[i];
         array[i] = array[maxIndex];
         array[maxIndex] = tmp;
     } 
 }

/**
 * Selection sort (descending order)
 * @param array array to be sorted
 * @param size size of the array
 */
void selectionSort(int array[], int size) {
     for (int i = 0; i < size - 1; i++) {
         int maxIndex = i;
         for (int j = i + 1; j < size; j++) {
             if (array[j] > array[maxIndex]) maxIndex = j;
         }
         int tmp = array[i];
         array[i] = array[maxIndex];
         array[maxIndex] = tmp;
     } 
 }

/**
 * Selection sort (descending order)
 * @param array array to be sorted
 */
 public static void SelectionSort(int[] array)
 {
     for (int i = 0; i < array.Length - 1; i++)
     {
         int maxIndex = i;
         for (int j = i + 1; j < array.Length; j++)
         {
             if (array[j] > array[maxIndex]) maxIndex = j;
         }
         int tmp = array[i];
         array[i] = array[maxIndex];
         array[maxIndex] = tmp;
     }
 }

procedure SelectSort(var X : ArrayType; N : integer);
var
  I,
  J,
  K,
  Y : integer;
begin
  for I := 1 to N - 1 do
    begin
      K := I;
      Y := X[I];
      for J := (I + 1) to N do
        if (X[J] < Y) then
          begin
            K := J;
            Y := X[J]
          end;
      X[K] := X[J];
      X[I] := Y;
    end
end;

Description

Visualization

Example

Code

Place for your banner