Sorting

Introduction

Sorting is another very common operation performed by computers on vector type structures. 

• Visually pleasing to have data in alphabetical order. 
• Information can be gained when data is presented in sorted order. 
• Processing (algorithms) can be simplified if the data is in sorted order.

Sorting is also one of the more expensive operations to carry out.

Sorts can be done in ascending order (the next value is equal or larger than the next one)
or in descending order (the next value is equal or smaller than the next one)

The Selection Sort

There are dozens of sorting algorithms.  Some much better than others.  The selection sort is easy to understand and implement.

For an ascending sort, the idea is to repeatedly search for the minimum value in the vector of values that remain. 

Swap the minimum value with the first value in the vector.

Repeat the process on the vector with one fewer elements.  The vector shrinks towards the end of the original vector.

  0  1  2  3  4  5  6  7  8  9 10 11

Example Program

#include <iostream>

#include <vector> // For the vector<CLASS> class

using namespace std;



typedef int vectorElementType;



void init(vector <vectorElementType> & x, int & n)

{ // post: x becomes a new vector precisely the size needed

  n = 5;

  x.resize(n);

  x[0] = 76;

  x[1] = 74;

  x[2] = 100;

  x[3] = 62;

  x[4] = 89;

}



void display(const vector <vectorElementType> & x, int & n)

{ // post: Show all elements

  int j;



  cout << "The vector: " << endl;

  for(j = 0; j < n; j++){

    cout.width(2);

    cout << j << ". ";

    cout.width(5);

    cout << x[j] << endl;

  }

}



void swap(vectorElementType & a, vectorElementType & b)

{ // post: Exchange values of a and b

  vectorElementType temp;

  

  temp = a; // Hold on to a's value so a can get changed

  a = b;

  b = temp;

}



void sort(vector < vectorElementType > & data, int n)

{ // post: Data elements are in descending order

  int j, top, subscriptOfLargest;

  subscriptOfLargest = 0;

  for(top = 0; top < n - 1; top++){

    subscriptOfLargest = top;



    for(j = top + 1; j < n; j++){

      if(data[j] > data[subscriptOfLargest])

      subscriptOfLargest = j;

    }

  swap(data[subscriptOfLargest], data[top]);

  }

}



int main()

{

  vector<int> test; // Default vector capacity is 0

  

  int n;

  init(test, n);

  sort(test, n);

  display(test, n);



  return 0;

}