GameDev.netBubble Sort

{ Bubble Sort Bubble Sort is an elementary sorting algorithm. It is so inefficient that it should never be used in practice. What makes it inefficient is the excessive number of exchanges that it performs. Much time is wasted by needlessly moving data in memory. Good alternatives, when seeking a simple, easy-to-implement sorting algorithm, for a relatively small number of values, include: Selection Sort, Insertion Sort, and Shell Sort. A good way to begin thinking about sorting algorithms is to ask: How can we check whether an array, a[ ], is already sorted in increasing order? One easy way would be to scan the array, checking that adjacent pairs were in the proper order. As soon as we found a single pair out of order, we could stop, and report the error. On the other hand, if we manage to scan through the whole array and each pair was in order, then the entire array must be sorted. Here's a Pascal function that does exactly that. -----------------------------------------------------------------} function is_sorted : boolean; var ok : boolean; i : integer; begin i := 1; repeat ok := a[i+1] >= a[i] ; i := i+1; until i = N or not ok; is_sorted := ok; end; { ----------------------------------------------------------------- Verifying that an array is already sorted requires just N-1 comparisons (and fewer if we find that it isn't sorted.) With a few modifications, this function can transformed into a sorting procedure that works by interchanging any out-of-order pairs that are found. Bubble Sort works by repeatedly scanning the array, checking adjacent pairs of values to see if they are in the proper order. In the implementation below, the boolean value ok is used to indicate whether the array is "ok", meaning "in sorted order". Whenever a pair of values is found to be out of order, they are interchanged and ok is set to "false", to indicate the array must be scanned again. This procedure will eventually end when the array is scanned and all adjacent values are found to be in their proper sorted order. Here is a procedure that implements Bubble Sort, assuming a global array a[ ] with n elements, and a procedure called swap( ). -----------------------------------------------------------------} procedure bubble_sort; var ok : boolean; i : integer; begin repeat ok := true; for i := 1 to n-1 do if a[i] > a[i+1] then begin swap(a[i],a[i+1]); ok := false end until ok end; { ----------------------------------------------------------------- This implementation of Bubble Sort requires about N2 comparisons and about N2 exchanges in the worst case, which occurs when the input data are sorted in reverse order. The best case scenario for this implementation occurs when the input data are already sorted in the proper order. In this case, one pass over the array (with just N comparisons and 0 exchanges) confirms the array is sorted. The amount of work (comparisons/exchanges) done by Bubble Sort in average case is difficult to analyze, but it is quite close to the work needed in the worst case. ---------------------------------------------------------------------------}
© 1999-2011 Gamedev.net. All rights reserved. |