1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 11-2.
6: /** Sorts the items in an array into ascending order.
7: @pre None.
8: @post theArray is sorted into ascending order; n is unchanged.
9: @param theArray The given array.
10: @param n The size of theArray. */
11: template <class ItemType>
12: void bubbleSort(ItemType theArray[], int n)
13: {
14: bool sorted = false; // False when swaps occur
15: int pass = 1;
16: while (!sorted && (pass < n))
17: {
18: // At this point, theArray[n+1-pass..n−1] is sorted
19: // and all of its entries are > the entries in theArray[0..n–pass]
20: sorted = true; // Assume sorted
21: for (int index = 0; index < n − pass; index++)
22: {
23: // At this point, all entries in theArray[0..index–1]
24: // are <= theArray[index]
25: int nextIndex = index + 1;
26: if (theArray[index] > theArray[nextIndex])
27: {
28: // Exchange entries
29: std::swap(theArray[index], theArray[nextIndex]);
30: sorted = false; // Signal exchange
31: } // end if
32: } // end for
33: // Assertion: theArray[0..n–pass–1] < theArray[n–pass]
34:
35: pass++;
36: } // end while
37: } // end bubbleSort