# Efficient Sorting Methods

The Bubble Sort

Implementation: Beginner

 Description The bubble sort is one of the simplest methods you can use. This method works well for simple data structures or if the data set to be sorted is more or less sorted. The bubble sort is very inefficient for a general data set. In the bubble sort algorithm, successive sweeps are made through the records to be sorted. During each sweep, the algorithm compares the key to the elements and swaps the elements if they are not in the desired order. Swapping occurs only among consecutive elements of the data structure. As a result, only one element is placed in its sorted place after each sweep. The sorted elements are not needed for comparison in successive sweeps. Pseudocode For iteration = 0 to (n-1) Begin For I = 0 to (n-1-iteration) Begin If array[I] > array[I+1] then Swap array[I] and array[I+1] End End Code void CSort::BubbleSort( void ) { for ( int iteration = 0 ; iteration < Count - 1 ; iteration++ ) { for ( int i = 0 ; i < Count - 1 - iteration ; i++ ) { if ( Array[ i ] > Array[ i + 1 ] ) Swap( i, i+1 ) ; } } } Analysis After each iteration, only one data element is placed in the proper-sorted position. Depends on the comparing and swapping of consecutive data elements. “Bubbling” the biggest element to the end. Simple implementation. The best-case scenario is when the data elements are almost sorted in the correct order. The worst-case scenario is when the data elements are in reverse order.

The Selection Sort

Implementation: Beginner

 Description The selection sort algorithm is based on using the data elements as keys for comparison such that, at the end of each scan, only one data element is placed in the desired sorted position. This algorithm is simple but very inefficient because it does not consider partial or fully sorted lists. In other words, if you have a partial or fully pre-sorted list, the selection sort does the same number of comparisons as it would on a completely random list and does not use any intelligence (unlike the bubble sort) to improve the performance. As a result the, the selection sort does not really lend itself to a best-case scenario. Pseudocode For iteration = 0 to (n-1) Begin Lowest = iteration For I = iteration+1 to (n-1) Begin If ( array[Lowest] > array[I] ) Lowest = I End Swap array[iteration] and array[lowest] End Code void CSort::SelectionSort( void ) { for ( int iteration = 0 ; iteration < Count - 1 ; iteration++ ) { int lowest = iteration ; for ( int i = iteration + 1 ; i < Count ; i++ ) { if ( Array[ i ] < Array[ lowest ] ) lowest = i ; } Swap( iteration, lowest ) ; } } Analysis After each iteration, only one data element is placed in the proper-sorted position. The selection sort only swaps once for every iteration. The selection sort has a simple implementation. The best-case scenario and the worst-case scenario is the same because the selection sort does not consider any partial sorting that might exist in the input.

The Quick Sort

Implementation: Expert

 Description The quick sort is the most efficient internal sort algorithm. Its preformance is largely influence by the choice of the pivot. The quick sort makes use of three strategies: Split the array into smaller sub arrays Sort the sub arrays Merge the sorted sub arrays A quick sort can be implemented in several ways, but the goal of each approach is to select a data element and place it in its proper position (which is referred to as the pivot) so that all the elemets on the left sided of the pivot are less than (or come before) the pivot and all the elements on the right side of the pivot are greater than (or come after) the pivot. The choice of the pivot and the method used to split the array has a big influence on the overall preformance. Pseudocode Select a data element and position it as a pivot so that it divides the array into a left sub array and a right sub array Apply a quick sort to the left sub array Apply a quick sort to the right sub array Code void CSort::QuickSort( int first, int last ) { int Lo, Hi, Mid, T; Lo = first; Hi = last; Mid = Array[(Lo+Hi)/2]; do { while (Array[Lo] < Mid) Lo++; while (Array[Hi] > Mid) Hi–; if (Lo <= Hi) { Swap(Lo, Hi); Lo++; Hi--; } } while (Lo <= Hi); if (Hi > first) QuickSort(first, Hi); if (Lo < last) QuickSort(Lo, last); } Analysis The split phase is very complex and the merge is simple In the best case, the work done is on the order of nlog2n In the worst case, the work is equal to the selectio sort, resulting in O(n2) The choice of the pivot is very important for the performance of the quick sort. The worst-case scenario is when the data elements are in reverse order.

Software comparison:

 Bubble Sort Selection Sort Quick Sort Items 39 45 30 29 63 34 10 98 165 59 60 95 59 20 149 366 92 82 99 55 30 204 633 144 135 126 81 40

Summary

The key point to remember is that the efficiency of any sorting method strongly depends on the implementation of the method and the actual data the method is sorting. The best way to choose the right sorting method for you needs is to test each method again various types of inputs. In particular, against a sample of the kind of data you intend to sort.

Tags: , ,

### 4 Responses to “Efficient Sorting Methods”

1. What a great resource!

2. bet365 says:

Good day!This was a really fabulous Topics!
I come from roma, I was fortunate to discover your Topics in wordpress
Also I obtain a lot in your blog really thanks very much i will come later

3. SunDude says:

include algorithm, then use the stl sort

4. Sorry for my bad english. Thank you so much for your good post. Your post helped me in my college assignment, If you can provide me more details please email me.