Visual Basic 2008 Programming: Business Applications with a Design Perspective
Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9
Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Appendix A Appendix B Appendix C Home
Loading
Last change: February 13 2016 18:48:19.

 Chapter in PDF

Table of Contents

Appendix C: Sorting and Searching
Last change: February 13 2016 18:48:22.
<<PreviousNext>>

C.4 Quick Sort

You may recall that in the bubble sort, in each round of comparisons, the algorithm attempts to identify which element in the array should be moved to a destination position. In other words, a destination is waiting for an element that qualifies. In the quick sort, the goal is inverted. The algorithm looks for the proper position for the given data element at hand. Specifically, when the sorting operation starts, the first element in the array is considered the pivotal element. The algorithm looks for the proper final position in the array to place this pivotal element. This is done by first comparing the pivotal element with the array elements backward (right to left) until the pivotal element is greater than the element in the array. The pivotal element is swapped with this element; then the pivotal element (in its new position) is compared with elements in the array forward (left to right) until it is found to be smaller than another element in the array. A swap takes place, and the comparisons go backward again.
The backward-forward sequence of comparisons/swaps continues until all elements in the array have been compared with the pivotal element. At this point, no element on the left side of the pivotal element is greater than and no element on its right is less than the pivotal element. The pivotal element has found its proper position. This process also ensures that all elements on the left side are smaller than all elements on the right side of the pivotal element; no further sorting between the two sides is necessary. The elements on each side can then be sorted separately using the same algorithm.
The following example illustrates how the pivotal element is placed in its proper position.

The first element, 38, is the pivotal element. At first, the comparisons start from right to left until the pivotal element is greater than the element in the array. This occurs immediately when 38 is compared with the fifth element, 34. A swap takes place:

Comparisons now turn forward. (Notice that 38 is the pivotal element.) The second element, 51, is compared with 38. They are out of order. Another swap takes place:

Comparisons then go backward again. 38 is compared with 56 and then with 23, where another swap takes place:

At this point, all elements have been compared with 38. The pivotal element has found its proper position. Note that all elements on its left side are smaller than 38, and all elements on its right side are greater. The sub-arrays on both sides (as depicted in the following illustration) can be sorted by the same algorithm:

Last change: February 13 2016 18:48:23.
  1. The Insert Sub Procedure
  2. The Insertion Sort Procedure
  3. Insertion Sort Versus Bubble Sort
  4. Testing Insertion Sort
  5. Binary Insertion Sort
  • C.3 Shell Sort
  • C.4 Quick Sort
    1. Header for Quick Sort
    2. Comparing Backward
    3. Comparing Forward
    4. The Outer Loop
    5. Sorting the Sub-arrays
    6. Terminating the Procedure
    7. The Better, the Worse
    8. Solving the Paradox
    9. The Stack Space Issue
    10. The Complete Code for Quick Sort
    11. <<PreviousNext>>