Algorithms: Selection Sort

The cutest of all sorting algorithms (or at least tied with bubble sort). Has O(N^2) due to N^2/2 compares. Data movement is minimal. The running time does not depend on the input data, in the sense that it will always take the same amount of time to run, as it compares each index to all indices to the right. So a random array will take the same amount of time to run through selection sort as a sorted array. Start with index 0, search the array to find the smallest element (might be at index 0), and replace with index 0. Move to index 1, rinse & repeat…

#include <iostream>

using namespace std;

template < typename T >
  void selectionSort(T arr[], int arrSize) {

    for (int i = 0; i < arrSize; i++) {
      int nextMin = i;
      for (int j = i + 1; j < arrSize; j++) {
        if (arr[j] < arr[nextMin])
          nextMin = j;
      }
      T swap = arr[nextMin];
      arr[nextMin] = arr[i];
      arr[i] = swap;
    }
  }

template < typename T >
  void printData(T data[], int size) {

    for (int i = 0; i < size; i++) {
      cout << data[i] << " ";
    }

    cout << endl;

  }

int main(int argc, char * argv[]) {

  int testData[] = {4, 5, 6, 7, 2, 9, 1, 3, 8};
  int size = sizeof(testData) / sizeof(testData[0]);

  cout << "testData before sort:" << endl;
  printData(testData, size);
  l
  selectionSort(testData, size);

  cout << "testData after sort:" << endl;
  printData(testData, size);

  return 0;
}