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:

• Selection Sort
• O(n^2) complexity. Not especially great for bigger lists.
• Bubble Sort
• O(n^2) complexity. Not especially great for bigger lists.
• One of the worst sorts there is, if not that exactly. Among sorting algorithms with O(n^2)
complexity, sorts like insertion sort are considerably more efficient.
• Quick Sort
• O(n log(n)) complexity at best.
• O(n^2) complexity in the worst case. This case is encountered when many or most elements
have the same value in the array being sorted.
• Binary tree sort variant. Is a divide and conquer sort algorithm.
• Significantly faster than other O(n log(n)) sort algorithms if the inner loop is optimized.
• On smaller arrays, say eight elements or less, sorting algorithms like insertion have been found to be faster.
• Faster implementations of this are not stable sorting algorithms, meaning that if there are
elements with equal values in a given order, the order is not guaranteed to be maintained.
• Merge Sort
• O(n log(n)) comparisons at worst. Twice as fast as that at best.
• Like quicksort, it is also a divide and conquer approach.
• Always a stable sort.
• Memory in the size of the list has to be set aside for this to work in most cases.
So there can be a memory/performance tradeoff.
• Is often what you want to use on linked lists, where quicksort and other binary sorts would not be as fast.
Merge sort would only need one extra element in this case as well.

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...)