25.7. Retrieving Files from Web Servers

[Page 754 ( continued )]

23.5. Quick Sort

Quick sort, developed by C. A. R. Hoare (1962), works as follows : The algorithm selects an element, called the pivot , in the array. Divide the array into two parts such that all the elements in the first part are less than or equal to the pivot and all the elements in the second part are greater than the pivot. Recursively apply the quick sort algorithm to the first part and then the second part. The algorithm is described in Listing 23.7.

Listing 23.7. Quick Sort Algorithm

 1   public static void   quickSort(   int   [] list) { 2   if   (list.length >   1   ) { 3 select a pivot; 4 partition list into list1 and list2 such that 5 all elements in list1 <= pivot and all elements 6 in list2 > pivot; 7 quickSort(list1); 8 quickSort(list2); 9 } 10 } 

Each partition places the pivot in the right place. The selection of the pivot affects the performance of the algorithm. Ideally, you should choose the pivot that divides the two parts evenly. For simplicity, assume the first element in the array is chosen as the pivot. Exercise 23.4 proposes an alternative strategy for selecting the pivot.

Figure 23.4 illustrates how to sort an array (5 2 9 3 8 4 0 1 6 7) using quick sort. Choose the first element 5 as the pivot. The array is partitioned into two parts, as shown in Figure 23.4(b). The highlighted pivot is placed in the right place in the array. Apply quick sort on two partial arrays (4 2 1 3 0) and then (8 9 6 7). The pivot 4 partitions (4 2 1 3 0) into just one partial array (0 2 1 3), as shown in Figure 23.4(c). Apply quick sort on (0 2 1 3). The pivot 0 partitions it to just one partial array (2 1 3), as shown in Figure 23.4(d). Apply quick sort on (2 1 3). The pivot 2 partitions it to (1) and (3), as shown in Figure 23.4(e). Apply quick sort on (1). Since the array contains just one element, no further partition is needed.

Figure 23.4. The quick sort algorithm is recursively applied to partial arrays.

(This item is displayed on page 755 in the print version)

Now turn attention to partition. To partition an array or a partial array, search for the first element from left forward in the array that is greater than the pivot, then search for the first element from right backward in the array that is less than or equal to the pivot. Swap these two elements. Repeat the same search and swap operations until all the elements are searched. Listing 23.8 gives a method that partitions a partial array list[first..last] . The first element in the partial array is chosen as the pivot (line 3). Initially low points to the second element in the partial array and high points to the last element in the partial array. The method returns the new index for the pivot that divides the partial array into two parts.

---

[Page 755]

Listing 23.8. Partition Method

 1  /** Partition the array list[first..last] */  2   private static int   partition(   int   [] list,   int   first,   int   last) { 3    int   pivot = list[first];  // Choose the first element as the pivot   4   int   low = first +   1   ;  // Index for forward search  5   int   high = last;  // Index for backward search  6 7    while   (high > low) {  8  // Search forward from left  9   while   (low <= high && list[low] <= pivot) 10 low++; 11 12  // Search backward from right  13   while   (low <= high && list[high] > pivot) 14 high ” ”; 15 16  // Swap two elements in the list  17   if   (high > low) { 18   int   temp = list[high]; 19 list[high] = list[low]; 20 list[low] = temp; 21 } 22 } 23 24   while   (high > first && list[high] >= pivot) 25 high ” ”; 26 27  // Swap pivot with list[high]  28   if   (pivot > list[high]) { 29 list[first] = list[high]; 30 list[high] = pivot; 31   return   high; 32 } 33   else   { 34   return   first; 35 } 36 } 

---

[Page 756]

Figure 23.5 illustrates how to partition an array (5 2 9 3 8 4 0 1 6 7). Choose the first element 5 as the pivot. Initially low is the index that points to element 2 and high points to element 7, as shown in Figure 23.5(a). Advance index low forward to search for the first element (9) that is greater than the pivot and move index high backward to search for the first element (1) that is less than or equal to the pivot, as shown in Figure 23.5(b). Swap 9 with 1, as shown in Figure 23.5(c). Continue the search and move low to point to element 8 and high to point to element 0, as shown in Figure 23.5(d). Swap element 8 with 0, as shown in Figure 23.5(e). Continue to move low until it passes high , as shown in Figure 23.5(f). Now all the elements are examined. Swap the pivot with element 4 at index high . The final partition is shown in Figure 23.5(g). The index of the pivot is returned when the method is finished.

Figure 23.5. The partition method returns the index of the pivot after it is put in the right place.

The quick sort algorithm is implemented in Listing 23.9. There are two overloaded quickSort methods in the class. The first method (line 2) is used to sort an array. The second is a helper method (line 6) that sorts a partial array with a specified range.

Listing 23.9. QuickSort.java

(This item is displayed on pages 756 - 757 in the print version)

 1   public class   QuickSort { 2   public static void   quickSort(   int   [] list) { 

---

[Page 757]

 3 quickSort(list,     , list.length -   1   ); 4 } 5 6   private static void   quickSort(   int   [] list,   int   first,   int   last) { 7   if   (last > first) { 8   int   pivotIndex = partition(list, first, last); 9 quickSort(list, first, pivotIndex -   1   ); 10 quickSort(list, pivotIndex +   1   , last); 11 } 12 } 13 14  /** Partition the array list[first..last] */  15   private static int   partition(   int   [] list,   int   first,   int   last) { 16  // Same as in Listing 23.8, so omitted  17 } 18 } 

23.5.1. Quick Sort Time

To partition an array of n elements, it takes n comparisons and n moves in the worst case. So, the time required for partition is O ( n ).

In the worst case, each time the pivot divides the array into one big subarray with the other empty. The size of the big subarray is one less than the one before divided. The algorithm requires ( n - 1) + ( n - 2) + ... + 2 + 1 = O ( n ² ) time.

In the best case, each time the pivot divides the array into two parts of about the same size. Let T ( n ) denote the time required for sorting an array of n elements using quick sort. So,

Similar to the merge sort analysis, T ( n ) = O ( n log n ).

On the average, each time the pivot will not divide the array into two parts of the same size nor one empty part. Statistically, the sizes of the two parts are very close. So the average time is O ( n log n ). The exact average-case analysis is beyond the scope of this book.

Both merge sort and quick sort employ the divide-and-conquer approach. For merge sort, the bulk of work is to merge two sublists, which takes place after the sublists are sorted. For quick sort, the bulk of work is to partition the list into two sublists, which takes place before the sublists are sorted. Merge sort is more efficient than quick sort in the worst case, but the two are equally efficient in the average case. Merge sort requires a temporary array for merging two subarrays. Quick sort does not need additional array space. So, quick sort is more space efficient than merge sort.