Good ol sorting stuff from school

gistfile1.cpp

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;


class ArraySort {
public:
	ArraySort(int size);
	~ArraySort();
	virtual void sort() = 0;
	void display();
protected:
	
	int *arr;  //the array of integers
	int size; //how many elements in the array
    
};

ArraySort::ArraySort(int size) {
	arr = new int[size];
	this->size = size;
    
	//Give it some random number
	srand ( time(NULL) );
	for (int i = 0; i < size; i++) {
        arr[i] = (rand() << 16) + rand();
	}
}

ArraySort::~ArraySort() {
	delete[] arr;
}

void ArraySort::display() { 
	for (int i = 0; i < size; i++) {
		cout << arr[i] << " ";
	}
	cout << endl << endl;
}


class SelectionSort : public ArraySort {
public:
	SelectionSort(int size) : ArraySort(size) {}
	void sort();
};

void SelectionSort::sort() {
    
    // start at first!!
    // first = 0
    // last = size 
	int smallestIndex = 0;
	for (int pass = 0; pass < size - 1; pass++) { 
		smallestIndex = pass;
		for (int i = pass + 1; i < size; i++) {
			//find the smallest
			if (arr[i] < arr[smallestIndex]) {
				smallestIndex = i;
			}
		}
		//smallestIndex has the index for the next
		//smallest value we need to work with
		int temp = arr[pass];
		arr[pass] = arr[smallestIndex];
		arr[smallestIndex] = temp;
	}
}
//////////////////////////////////
//// A
/////////////////////
class QuickSort : public ArraySort {
public:
	QuickSort(int size) : ArraySort(size) {}
	void sort();
private:
	int partition(int first, int last);
	void swap(int first, int second);
	void recQuickSort(int first, int last);

};

void QuickSort::sort() {
	recQuickSort(0, size-1);
}


void QuickSort::recQuickSort(int first, int last) {
	int pivotLocation;
    
    // if last minus first is < 20 
    //do selection sort. 
	if (first < last) {
		pivotLocation = partition(first,last);
		recQuickSort(first, pivotLocation - 1);
		recQuickSort(pivotLocation + 1, last);
     
	}
}
     
int QuickSort::partition(int first, int last) {
 
	int pivot;
	int index, smallIndex;
	//swap the pivot as needed
	swap(first, (first + last) /2);
    
	pivot = arr[first];
	smallIndex = first;
    
	for (index = first + 1; index <= last; index++){
		if (arr[index] < pivot) {
			smallIndex++;
			swap(smallIndex, index);
		}
	}
    
	swap(first, smallIndex);
    
	return smallIndex;
}

void QuickSort::swap(int first, int second) {
	int temp;
	temp = arr[first];
	arr[first] = arr[second];
	arr[second] = temp;
}

/////////////////////////
///// END A
////////////////////////

/////////////////////////////
///// B
////////////////////////////
class QuickSortB : public ArraySort {
public:
	QuickSortB(int size) : ArraySort(size) {}
	void sort();
private:
	int partition(int first, int last);
	void swap(int first, int second);
	void recQuickSort(int first, int last);

};

void QuickSortB::sort() {
	recQuickSort(0, size-1);
}


void QuickSortB::recQuickSort(int first, int last) {
	int pivotLocation;
    
    // if last minus first is < 20 
    //do selection sort. 
	if (first < last) {
		pivotLocation = partition(first,last);
		recQuickSort(first, pivotLocation - 1);
		recQuickSort(pivotLocation + 1, last);
        
	}
}

int QuickSortB::partition(int first, int last) {
    
	int pivot;
	int index, smallIndex;
//    int large;
//    int small; 
//
//    if(arr[first] > arr[last]){
//        small = arr[last]; 
//        large = arr[first]; 
//
//    }else{
//        large = arr[last]; 
//        small = arr[first]; 
//
//    }
//               
//    if(arr[(first+last)/2] > large){
//        
//        pivot = arr[large]; 
//        swap(first, large); 
//    }else{
//        if(arr[(first+last)/2] < small){
//            pivot = arr[small]; 
//            	swap(first, small);
//        }else{
//            pivot = arr[(first+last)/2]; 
//            swap(first, (first+last)/2); 
//        }
//        
//    }
    if(arr[first] >= arr[(first + last)/2] && arr[first] <= arr[last])
        pivot = arr[first];
    else if(arr[(first + last)/2] >= arr[first] && arr[(first + last)/2] <= arr[last])
    {
        pivot = arr[(first + last)/2];
        swap(first,(first + last)/2);
    }
    else
    {
        pivot = arr[last];
        swap(first,last);
    }
   
   
    
                
    
	//swap the pivot as needed

    
	//pivot = arr[first];
	smallIndex = first;
    
	for (index = first + 1; index <= last; index++){
		if (arr[index] < pivot) {
			smallIndex++;
			swap(smallIndex, index);
		}
	}
    
	swap(first, smallIndex);
    
	return smallIndex;
}

void QuickSortB::swap(int first, int second) {
	int temp;
	temp = arr[first];
	arr[first] = arr[second];
	arr[second] = temp;
}


/////////////////////////////
///// END B
////////////////////////////

/////////////////////////////
///// C
////////////////////////////
class QuickSortC : public ArraySort {
public:
	QuickSortC(int size) : ArraySort(size) {}
	void sort();
private:
	int partition(int first, int last);
	void swap(int first, int second);
	void recQuickSort(int first, int last);
};

void QuickSortC::sort() {
	recQuickSort(0, size-1);
}


void QuickSortC::recQuickSort(int first, int last) {
	int pivotLocation;
    
    // if last minus first is < 20 
    //do selection sort. 
	if (first < last) {
		pivotLocation = partition(first,last);
		recQuickSort(first, pivotLocation - 1);
		recQuickSort(pivotLocation + 1, last);
        
	}
}

int QuickSortC::partition(int first, int last) {
    
    if((last - first) > 20) {
        int pivot;
        int index, smallIndex;
        //swap the pivot as needed
        swap(first, (first + last) /2);
        
        pivot = arr[first];
        smallIndex = first;
        
        for (index = first + 1; index <= last; index++){
            if (arr[index] < pivot) {
                smallIndex++;
                swap(smallIndex, index);
            }
        }
        
        swap(first, smallIndex);
        
        
         return smallIndex;
    }else{
		int smallestIndex = first;
        for (int pass = first; pass < last - 1; pass++) { 
            smallestIndex = pass;
            for (int i = pass + 1; i < last; i++) {
                //find the smallest
                if (arr[i] < arr[smallestIndex]) {
                    smallestIndex = i;
                }
            }
            //smallestIndex has the index for the next
            //smallest value we need to work with
            int temp = arr[pass];
            arr[pass] = arr[smallestIndex];
            arr[smallestIndex] = temp;
        }
    
	
    }
   
}

void QuickSortC::swap(int first, int second) {
	int temp;
	temp = this->arr[first];
	this->arr[first] = this->arr[second];
	this->arr[second] = temp;
}


/////////////////////////////
///// END C
////////////////////////////

/////////////////////////////
///// D
////////////////////////////
class QuickSortD : public ArraySort {
public:
    QuickSortD(int size) : ArraySort(size) {}
    void sort();
private:
    int partition(int first, int last);
    void swap(int first, int second);
    void recQuickSort(int first, int last);
};

void QuickSortD::sort() {
    recQuickSort(0, size-1);
}

void QuickSortD::recQuickSort(int first, int last) {
    int pivotLocation;
    if (first < last) {
        pivotLocation = partition(first,last);
        recQuickSort(first, pivotLocation - 1);
        recQuickSort(pivotLocation + 1, last);
    }
}

int QuickSortD::partition(int first, int last) {
    if(last - first > 20)
    {
        int pivot;
        int index, smallIndex;
        
        if(arr[first] >= arr[(first + last)/2] && arr[first] <= arr[last])
            pivot = arr[first];
        else if(arr[(first + last)/2] >= arr[first] && arr[(first + last)/2] <= arr[last])
        {
            pivot = arr[(first + last)/2];
            swap(first,(first + last)/2);
        }
        else
        {
            pivot = arr[last];
            swap(first,last);
        }
        
        
        
        //swap the pivot as needed
        //swap(first, pivot);
        smallIndex = first;
        
        for (index = first + 1; index <= last; index++){
            if (arr[index] < pivot) {
                smallIndex++;
                swap(smallIndex, index);
            }
        }
        
        swap(first, smallIndex);
        
        return smallIndex;
    }else{
        
        int smallestIndex = first;
        for (int pass = first; pass < last - 1; pass++) { 
            smallestIndex = pass;
            for (int i = pass + 1; i < last; i++) {
                //find the smallest
                if (arr[i] < arr[smallestIndex]) {
                    smallestIndex = i;
                }
            }
            //smallestIndex has the index for the next
            //smallest value we need to work with
            int temp = arr[pass];
            arr[pass] = arr[smallestIndex];
            arr[smallestIndex] = temp;
        }
        
    }
}

void QuickSortD::swap(int first, int second) {
    int temp;
    temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
}

/////////////////////////////
///// END D
////////////////////////////

/////////////////////////////
///// F
////////////////////////////
class QuickSortF : public ArraySort {
public:
	QuickSortF(int size) : ArraySort(size) {}
	void sort();
private:
	int partition(int first, int last);
	void swap(int first, int second);
	void recQuickSort(int first, int last);
};

void QuickSortF::sort() {
	recQuickSort(0, size-1);
}


void QuickSortF::recQuickSort(int first, int last) {
	int pivotLocation;
    
    // if last minus first is < 20 
    //do selection sort. 
	if (first < last) {
		pivotLocation = partition(first,last);
		recQuickSort(first, pivotLocation - 1);
		recQuickSort(pivotLocation + 1, last);
        
	}
}

int QuickSortF::partition(int first, int last) {
    
	int pivot;
	int index, smallIndex;
	//swap the pivot as needed
	swap(first, (first + last) /2);
    
	pivot = arr[first];
	smallIndex = first;
    
	for (index = first + 1; index <= last; index++){
		if (arr[index] < pivot) {
			smallIndex++;
			swap(smallIndex, index);
		}
	}
    
	swap(first, smallIndex);
    
	return smallIndex;
}

void QuickSortF::swap(int first, int second) {
	int temp;
	temp = arr[first];
	arr[first] = arr[second];
	arr[second] = temp;
}

/////////////////////////////
///// END F
////////////////////////////
void runSortStuff(ArraySort *obj) {
	//obj->display();
	cout << "Starting the sort..." << endl;
	obj->sort();
	cout << "Sorted!" << endl;
	//obj->display();
	delete obj;
    
}
int main() {
	
	//runSortStuff(new BubbleSort(40000));
	//runSortStuff(new SelectionSort(40000));
	clock_t t1, t2;
    
    t1 = clock();
    runSortStuff(new QuickSort(50000));     
    t2 = clock(); 
    
    float diff = ((float)t2 - (float)t1)/1000000.0F;  
    cout << "Part A complete. Took "; 
    cout << diff << endl; 
    
    
    t1 = clock();
    runSortStuff(new QuickSortB(50000));     
    t2 = clock(); 
    
     diff = ((float)t2 - (float)t1)/1000000.0F;  
    cout << "Part B complete. Took "; 
    cout << diff << endl; 
    
    
    
    t1 = clock();
    runSortStuff(new QuickSortC(50000));     
    t2 = clock(); 
    
    diff = ((float)t2 - (float)t1)/1000000.0F;  
    cout << "Part C complete. Took "; 
    cout << diff << endl; 
    
    
    
    
    
    
   	return 0;
}