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