Sorting

Introduction:

Sorting is a fundamental computer science problem. There are a number of interesting things about to it,
like: there are often a number of ways to make a sophisticated sorting algorithm faster, there are different
ways of implementing sort algorithms, and there are a large number of different algorithms for sorting a data set
(Only a limited portion of which is discussed here.) Not only all of that, but sorting algorithms don't strictly have
to be used for sorting a collection of elements, then using the sorted collection. A sorting alg. can also be used in
one iteration at a time in order to show something actively being sorted (As you may well imagine, this has many
applications in video games.)

Of the different sorting algorithms, here are a mere few:




Below are some simple implementations of the above sorting algorithms in C++ and Python, with
instructive commenting in the C++ versions. I've written each to work only with integer arrays.
The logic in the different language versions of each sorting algorithm are the same (so no commenting:
on the non-C++ versions.) Also these implementations are not necessarily optimal and are only intended to
give the basic idea.

NOTE: Of course, to expand this functionality to sort any data type, all you would have to do is
template these methods, and implement comparison (<,<=,>,>=) and equal (=) operators.


Selection Sort:

C++
void SelectionSort( int v[], unsigned int num_elements )
{
  unsigned int smallest;	// Index to the element that is smallest of the remaining elements being sorted.

  // Iterate once for each element in the array..
  for( unsigned int left = 0; left < num_elements; ++left )
  {
    smallest = left;
    // Find the smallest element-value from the remaining elements of the 
    // array that is also smaller than the current element (if any) and store the index to it..
    for( unsigned int cur_check = (left+1); cur_check < num_elements; ++cur_check )
    {
      // If this element-value is less than the one indexed by 'left'...
      if( v[cur_check] < v[smallest] )
      {
        smallest = cur_check;   // Record this as the smallest of the remaining element-values checked so far.
      }
    }

    // If we found an element-value that was less than the one at index 'left'...
    if( smallest > left )
    {	
      Swap(v,left,smallest);  // Then Swap that element-value with the one at index 'left'.
    }
  }
}

Python
def SelectionSort( v, num_elements ):

    smallest= 0
    left = 0
    cur_check= 0;
  
    while left < num_elements:  
        smallest= left;
        cur_check= (left+1)
        while cur_check < num_elements:    
            if v[cur_check] < v[smallest]:      
                smallest= cur_check;     
            cur_check= (cur_check+1)

        if smallest > left:
            Swap(v,left,smallest);
        left= (left+1)
Bubble Sort:

C++
void BubbleSort( int v[], unsigned int num_elements )
{
  // For one less than the number of elements..
  for( unsigned int i = 0; i < (num_elements - 1); ++i )
  {
    // Go through all but the first element..
    for( unsigned int j = 1; j < num_elements; ++j )
    {
      // Check against the element previous to the one we are currently looking at.
      // If it is smaller than this one, then Swap the two, such that the smaller value
      // comes first (in terms of being at a lesser index.)
      if( v[j] < v[j-1] )
      {
        Swap(v,j,j-1);
      }
    }
  }
}
Python
def BubbleSort( v, num_elements ):
    i= 0
    j= 1

    while i < (num_elements - 1):
        while j < num_elements:
            if v[j] < v[j-1]:              
                Swap(v,j,j-1)
            j= (j+1)
        i= (i+1)
Quick Sort:

C++
void QuickSort( int v[], unsigned int left, unsigned int right )
{
  unsigned int i, pivot;

  // If the left and right element-indeces are the same or have crossed...
  if( left >= right )
  {
    return; // Then we're done sorting.
  }

  Swap(v,left,(left+right)/2);    // Swap value of 'left'-indexed element with the element 
                                  // at the index halfway between elements indexes 'left' and 'right'.
  pivot = left;                   // Set 'pivot' index to the current 'left' index.

  // From the element-index after 'left' to 'right'
  for( i = (left+1); i <= right; ++i )
  {
    // If the current element-value is less than the element-value at 'left'...
    if( v[i] < v[left] )
    {
      Swap(v,++pivot,i);          // Swap the two element values in the array.
    }
  }

  // Since the value we were comparing for the element
  // at index 'left' comes before.
  Swap(v,left,pivot);				    
  QuickSort(v,left,pivot-1);    // Recurse to sort the left side of the list.
  QuickSort(v,pivot+1,right);   // Recurse to sort the right side of the list.
}
Python
def QuickSort( v, left, right ):
    i= (left+1)
    pivot= 0

    if left >= right:
        return

    Swap(v,left,(left+right)/2)
    pivot= left
 
    while i <= right:
        if v[i] < v[left]:
            pivot= (pivot+1)
            Swap(v,pivot,i)
        i= (i+1)

    Swap(v,left,pivot)
    QuickSort(v,left,pivot-1)
    QuickSort(v,pivot+1,right)

Merge Sort: (Coming Soon...)