quicksort.cpp

ssd5 op5的答案

//the author is liqinwei
//2007/12/8
#include "quicksort.h"

/*
 * You should implement this. It is the meat of the constructor
 * and is also used by the reset() method.
 *
 * It will create the QuickSort object with an "unsorted" list.
 *
 * - how_many is the number of elements in the list.
 * - workload_type is BEST_CASE, WORST_CASE, or AVG_CASE
 */


void quicksort::init (int how_many, int workload_type) {
    /*
     * Insert your code here
     *
     * IMPORTANT NOTE: You need to allocate the numbers array declared in
     * the sort class so that it can hold "how_many" numbers, and you
     * need to fill numbers (integers) into this array. The ordering
     * should be determined by the workload. 
     *
     * Since you may be using the same workload for many different sorts
     * and configurations of the same sort, you might want to use
     * helper methods. Helper methods that should be accessible to 
     * all of the sorts should be "protected (not public or private) and
     * placed in the Sort class. Helper methods used by only this sort
     * can stay in this file and be made "private".
     *
     * This method should NOT sort the array.
     */
    srand(clock() / 1000);

	int i;
	switch (workload_type)
	{
		//initialize the best case 
		case 1 :for(i = 0;i<how_many;i++){
					numbers[i] = i; 
				}break;
		//initialize the average case 
		case 2 :for(i = 0;i<how_many;i++){
					numbers[i] = rand(); 
				}break;
		//initialize the worst case
		case 3 :for(i = 0;i<how_many;i++){
					
					numbers[i] = 24000 - i; 
				}break;
	}

}


/*
 * This is the constructor. It is nothing more than a shell to
 * call init(). This allows init() to be used by both the constructor
 * and also the parent class's reset() method
 */
quicksort::quicksort (int how_many, int workload_type) {
    this->how_many = how_many;
    this->workload_type = workload_type;

    init (how_many, workload_type);
}


/*
 * This is the implementation of the quick sort algorithm that
 * extends the Sort class's abstract sortNumbers() method.
 *
 * It is really a wrapper for the private helper method, sortPartition(),
 * which does the real "divide and conquer".
 */
void quicksort::sortNumbers() {
    sortPartition (0, how_many - 1);
}


/*
 * This is a helper method called by sortNumbers(). It sorts
 * an individual partition about the pivot point.
 */
int quicksort::partition (int left, int right) {

    int pivot = numbers[left];
    int l = left + 1;
    int r = right;
    
    while (l <= r) {
        while (l <= right && numbers[l] <= pivot) {
            l++;
        }
        while (r >= left && numbers[r] > pivot) {
            r--;
        }
        if (l < r) {
            swapNumbers(l, r);
            l++;
            r--;
        }
    }
    swapNumbers(left, r); // put pivot in middle
    return r;

}


/*
 * This is a helper method called by sortNumbers(). It recursively 
 * calls itself on subpartitions to sort the numbers. The actual
 * sorting within the partition is done by sortPartition(), which
 * is iterative.
 */
void quicksort::sortPartition (int left, int right) {
    int placed = partition (left, right);

    if ((placed - left) > 1) sortPartition (left, placed - 1);
    if ((right - placed) > 1) sortPartition (placed + 1, right);
}