SortSelection
[ Home ] [ Up ]

//selSort.cpp
//Author me
//02/12/2001

/*
Algorithm for selection sort for a[0]..a[n-1]

Input: 4, 2, 1, 3, 5, 2
output:1, 2, 2, 3, 4, 5


Version 1
---------
put the highest value at the end and ignore it
do the same thing with the remaining list until list size is 1


Version 2
---------
find the highest value
swap it with the last value
ignore the last value
do the same until list size is 1


Version 3
---------
do the following while size > 1
  find the highest value
  swap it with the last value
  decrease the size by 1
  end do


Version 4
---------
m = n
do the following while m > 1
  find the position of highest value of a[0..m-1] in maxP
  swap a[maxP] with a[m-1]
  decrease the m by 1
  end do


Version 5
---------
m = n
do the following while m > 1
  maxP=0
  do the following for i=1 to m-1
    if a[maxP] < a[i] then maxP = i
    end do
  swap a[maxP] with a[m-1]
  decrease the m by 1
  end do

*/


#include <iostream.h>

void sortSelection(int a[], int n)
  {
  int m = n, maxP, i, tempA;
  while (m > 1)
    {
    maxP=0;
    for (i=1; i<=m-1; i++)
      if (a[maxP] < a[i]) 
          maxP = i;
    //swap a[maxP] with a[m-1]
    tempA = a[maxP];
    a[maxP] = a[m-1];
    a[m-1] = tempA;

    m--;
    }
  }

void main (void)
  {
  int x[] = {4, 2, 1, 3, 5, 2};

  for (int i=0; i<6; i++)
    cout << x[i] << ' ';
  cout << endl;

  sortSelection(x, 6);
  for (i=0; i<6; i++)
    cout << x[i] << ' ';

  }