Sep
29

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:

  1. Split the array into smaller sub arrays
  2. Sort the sub arrays
  3. 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
  1. 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
  2. Apply a quick sort to the left sub array
  3. 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.

Downloads

Download the following code to test the sorting methods:

Download the code - 4.65 Kb

Tags: , ,

Posted by admin C++ FAQs Subscribe to RSS feed

4 Responses to “Efficient Sorting Methods”

  1. veterinary technician says:
    August 30, 2023 at 2:07 pm

    What a great resource!

  2. bet365 says:
    August 30, 2023 at 2:36 pm

    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:
    September 9, 2023 at 1:39 pm

    include algorithm, then use the stl sort :D

  4. Debt Consolidation says:
    September 24, 2023 at 4:19 am

    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.

Leave a Reply

You must be logged in to post a comment.