C++ || Decrease By Half Sorting Using Bubble Sort, Quick Sort, & Optimized Bubble Sort

November 02, 2013 admin No comments

The following is another homework assignment which was presented in an Algorithm Engineering class. Using a custom timer class, the following is a program which tries to improve upon the sorting code demonstrated in the initial Empirical Analysis.

The following program will execute two approaches: (1) implementing an algorithm with better asymptotic performance, and (2) tuning an existing algorithm.

==== 1. THE OBJECTIVE ====

The purpose of implementing this program is to obtain empirical results that answer the following questions:

• Are O(n log n) expected-time sorting algorithms, such as merge sort and quick sort, significantly faster than O(n2)-time algorithms in practice? • If so, by what margin? Is implementing a faster algorithm worth the effort? • Is it possible to get a O(n2)-time algorithm to beat a O(nlogn)-time algorithm by paying attention to implementation details? • If so, how much faster? Do you get better bang-for-the-buck by switching to an asymptotically-faster algorithm, or optimizing the same algorithm?

==== 2. THE ALGORITHMS ====

This program involves implementing and analyzing three algorithms:

1. Baseline: The O(n2) sorting algorithm implemented in Project 1. 2. Decrease-by-half: An O(n log n) algorithm (Quick Sort). 3. Optimized: A tuned, optimized version of the O(n2) baseline algorithm.

==== 3. FLOW OF CONTROL ====

A test harness program is created which executes the above functions and measures the elapsed time of the code corresponding to the algorithm in question. The test program will perform the following steps:

1. Input the value of n. Your code should treat n as a variable. 2. Create an array or vector of n random integers to serve as a problem instance. 3. Use a clock function to get the current time t1 . 4. Execute one algorithm (Bubble Sort, Quick sort, or Optimized Bubble Sort), using the array of random integers as input. 5. Use a clock function to get the current time t2 . 6. Output the elapsed time, t2 − t1 .

The test harness is configured in such a way to run all of the three algorithms, using a switch statement to change between the algorithms.

==== 4. TEST HARNESS ====

Note: This program uses two external header files (Timer.h and Project1.h).
• Code for the Timer class (Timer.h) can be found here.
• Code for “Project1.h” can be found here.
• “Project3.h” is listed below.





		
		
			Decrease By Half Test Harness
			
C++
			
			// =============================================================================
//    Author: K Perkins
//    Date:   Nov 2, 2013
//    Taken From: http://programmingnotes.org/
//    File:  main.cpp
//    Description: This is the test harness program which runs the code and 
//       measures the elapsed time of the code corresponding to the algorithm 
//       in question. This program will try to improve the sorting methods
//       written in Project 1 by two approaches: 
//         (1) Implementing an algorithm with better asymptotic performance
//         (2) Tuning an existing algorithm. 
//       The sorting methods being reviewed are Bubble sort, Quick sort, and an 
//       optimized version of Bubble sort.
// =============================================================================
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "Timer.h"
#include "Project1.h"
#include "Project3.h"
using namespace std;

// typedefs for the functions to use
enum Algorithms {bubble, quick, bubbleOptim};

// number of algs being tested
int NUM_ALGS = 3;

// default arry size
const int ARRAY_SIZE = 150000;

int main()
{
	// declare variables
	srand(time(NULL));
	int* arry = new int[ARRAY_SIZE];
	int seed = rand(); // generate a random seed to use for array on all algorithms
	Timer timer;
	Project1 proj1;
	Project3 proj3;
	
	// display the array size	
	cerr<<"nArray Size = "<<ARRAY_SIZE<<endl;	

	// loop to automatically execute the proj1 being tested
	for(int x=0; x < NUM_ALGS; ++x)
	{
	    cout<<"n----- STARTING ALGORITHM #"<<x+1<<" ----- nn";
	    	
		timer.Reset();
		
		// place data in the array
		proj1.Generate(arry, ARRAY_SIZE, seed);
		
		// display data in array if its within range		
		if(ARRAY_SIZE <= 25)
		{
			proj1.Display(arry, ARRAY_SIZE);
			cout<<endl;
		}

		// start the timer
		timer.Start();
		
		// determine which alg to execute
		switch(x)
		{
			case bubble:
				proj1.BubbleSort(arry, ARRAY_SIZE);
				break;
			case quick:
				proj3.QuickSort(arry, ARRAY_SIZE);
				break;
			case bubbleOptim:
				proj3.BubbleSort(arry, ARRAY_SIZE);
				break;
			default:
				cout<<"nThat option doesnt exist...n";
				exit(1);
				break;
		}
		
		// stop the timer
		timer.Stop();
		
		// display data in array if its within range
		if(ARRAY_SIZE <= 25)
		{
			cout<<endl;
			proj1.Display(arry, ARRAY_SIZE);
			cout<<endl;
		}
		
		// display time
		cout<<endl<<"It took "<<timer.Elapsed()*1000
			<<" clicks ("<<timer.Elapsed()<<" seconds)"<<endl;
		cout<<"n----- ALGORITHM #"<<x+1<<" DONE! ----- nn";
	}

	delete[] arry;
	return 0;
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
				
						// =============================================================================
//    Author: K Perkins
//    Date:   Nov 2, 2013
//    Taken From: http://programmingnotes.org/
//    File:  main.cpp
//    Description: This is the test harness program which runs the code and 
//       measures the elapsed time of the code corresponding to the algorithm 
//       in question. This program will try to improve the sorting methods
//       written in Project 1 by two approaches: 
//         (1) Implementing an algorithm with better asymptotic performance
//         (2) Tuning an existing algorithm. 
//       The sorting methods being reviewed are Bubble sort, Quick sort, and an 
//       optimized version of Bubble sort.
// =============================================================================
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "Timer.h"
#include "Project1.h"
#include "Project3.h"
using namespace std;
 
// typedefs for the functions to use
enum Algorithms {bubble, quick, bubbleOptim};
 
// number of algs being tested
int NUM_ALGS = 3;
 
// default arry size
const int ARRAY_SIZE = 150000;
 
int main()
{
	// declare variables
	srand(time(NULL));
	int* arry = new int[ARRAY_SIZE];
	int seed = rand(); // generate a random seed to use for array on all algorithms
	Timer timer;
	Project1 proj1;
	Project3 proj3;
	
	// display the array size	
	cerr<<"nArray Size = "<<ARRAY_SIZE<<endl;	
 
	// loop to automatically execute the proj1 being tested
	for(int x=0; x < NUM_ALGS; ++x)
	{
	    cout<<"n----- STARTING ALGORITHM #"<<x+1<<" ----- nn";
	    	
		timer.Reset();
		
		// place data in the array
		proj1.Generate(arry, ARRAY_SIZE, seed);
		
		// display data in array if its within range		
		if(ARRAY_SIZE <= 25)
		{
			proj1.Display(arry, ARRAY_SIZE);
			cout<<endl;
		}
 
		// start the timer
		timer.Start();
		
		// determine which alg to execute
		switch(x)
		{
			case bubble:
				proj1.BubbleSort(arry, ARRAY_SIZE);
				break;
			case quick:
				proj3.QuickSort(arry, ARRAY_SIZE);
				break;
			case bubbleOptim:
				proj3.BubbleSort(arry, ARRAY_SIZE);
				break;
			default:
				cout<<"nThat option doesnt exist...n";
				exit(1);
				break;
		}
		
		// stop the timer
		timer.Stop();
		
		// display data in array if its within range
		if(ARRAY_SIZE <= 25)
		{
			cout<<endl;
			proj1.Display(arry, ARRAY_SIZE);
			cout<<endl;
		}
		
		// display time
		cout<<endl<<"It took "<<timer.Elapsed()*1000
			<<" clicks ("<<timer.Elapsed()<<" seconds)"<<endl;
		cout<<"n----- ALGORITHM #"<<x+1<<" DONE! ----- nn";
	}
 
	delete[] arry;
	return 0;
}// http://programmingnotes.org/

==== 5. THE ALGORITHMS – “include Project3.h” ====





		
		
			Bubble Sort, Quick Sort, & Optimized Bubble Sort
			
C++
			
			// =============================================================================
//    Author: K Perkins
//    Date:   Nov 2, 2013
//    Taken From: http://programmingnotes.org/
//    File:  Project3.h
//    Description: This is a simple class which holds the functions for 
//       project 3
// =============================================================================
#ifndef PROJECT3_H
#define PROJECT3_H

#include <cstdlib>
#include <algorithm>

class Project3
{
public:
	Project3(){}
	// exchange unsorted elements with the last element
	// not the adjacent element
	void BubbleSort(int arry[], int size)
	{
		int last = size-1;
		do{
			for(int current=0; current < last; ++current) 
			{
				if(arry[current] > arry[last]) 
				{
					std::swap(arry[current], arry[last]);
				}
			}
			--last;
		}while(last >= 0);
	}// end of BubbleSort

	void QuickSort(int arry[], int size) 
	{
		if(size > 1) 
		{
			// choose pivot
			int pivotIndex = rand()%(size-1); 
			// partition the arry and get the new pivot position
			int newPiviotIndex = Partition(arry, size, pivotIndex); 
			// quick sort the first part
			QuickSort(arry, newPiviotIndex); 
			// quick sort the second part
			QuickSort(arry+newPiviotIndex+1, size-newPiviotIndex-1); 
		}
	}// end of QuickSort

	int Partition(int arry[], int size, int pivotIndex) 
	{
		int pivotValue = arry[pivotIndex];
		arry[pivotIndex] = arry[size-1]; // swap pivot with last element
		arry[size-1] = pivotValue;
		int left = 0; // left index
		int right = size-2; // right index
	
		while(left < right) 
		{ // ( < pivot ), pivot, ( >= pivot)
			while((arry[left] < pivotValue) && (left < right))
			{
				++left;
			}
			while((arry[right] >= pivotValue) && (left < right))
			{
				--right;
			}
			if(left < right) 
			{
				std::swap(arry[left], arry[right]);
				++left;
				--right;
			}
		}
		if(left == right)
		{
			if(arry[left] < pivotValue)
			{
				++left;
			}
		}
		arry[size-1] = arry[left]; // move pivot to its final place
		arry[left] = pivotValue;
		return left; // return the position of the pivot
	}// end of Partition
	
	~Project3(){}
};
#endif // http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
				
						// =============================================================================
//    Author: K Perkins
//    Date:   Nov 2, 2013
//    Taken From: http://programmingnotes.org/
//    File:  Project3.h
//    Description: This is a simple class which holds the functions for 
//       project 3
// =============================================================================
#ifndef PROJECT3_H
#define PROJECT3_H
 
#include <cstdlib>
#include <algorithm>
 
class Project3
{
public:
	Project3(){}
	// exchange unsorted elements with the last element
	// not the adjacent element
	void BubbleSort(int arry[], int size)
	{
		int last = size-1;
		do{
			for(int current=0; current < last; ++current) 
			{
				if(arry[current] > arry[last]) 
				{
					std::swap(arry[current], arry[last]);
				}
			}
			--last;
		}while(last >= 0);
	}// end of BubbleSort
 
	void QuickSort(int arry[], int size) 
	{
		if(size > 1) 
		{
			// choose pivot
			int pivotIndex = rand()%(size-1); 
			// partition the arry and get the new pivot position
			int newPiviotIndex = Partition(arry, size, pivotIndex); 
			// quick sort the first part
			QuickSort(arry, newPiviotIndex); 
			// quick sort the second part
			QuickSort(arry+newPiviotIndex+1, size-newPiviotIndex-1); 
		}
	}// end of QuickSort
 
	int Partition(int arry[], int size, int pivotIndex) 
	{
		int pivotValue = arry[pivotIndex];
		arry[pivotIndex] = arry[size-1]; // swap pivot with last element
		arry[size-1] = pivotValue;
		int left = 0; // left index
		int right = size-2; // right index
	
		while(left < right) 
		{ // ( < pivot ), pivot, ( >= pivot)
			while((arry[left] < pivotValue) && (left < right))
			{
				++left;
			}
			while((arry[right] >= pivotValue) && (left < right))
			{
				--right;
			}
			if(left < right) 
			{
				std::swap(arry[left], arry[right]);
				++left;
				--right;
			}
		}
		if(left == right)
		{
			if(arry[left] < pivotValue)
			{
				++left;
			}
		}
		arry[size-1] = arry[left]; // move pivot to its final place
		arry[left] = pivotValue;
		return left; // return the position of the pivot
	}// end of Partition
	
	~Project3(){}
};
#endif // http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Note: This page presents sample code for the above problem, but scatter plots will not be provided.

The following is sample output:

Array Size = 150000
----- STARTING ALGORITHM #1 ----- It took 248290 clicks (248.29 seconds) ----- ALGORITHM #1 DONE! ----- ----- STARTING ALGORITHM #2 ----- It took 50 clicks (0.05 seconds) ----- ALGORITHM #2 DONE! ----- ----- STARTING ALGORITHM #3 ----- It took 164300 clicks (164.3 seconds)
----- ALGORITHM #3 DONE! -----

Was this article helpful?

👍 YesNo

Posted in: Advanced, C++ Tags: bubble sort, cpsc 335, decrease by half, empirical analysis, quick sort

C++ || Decrease By Half Sorting Using Bubble Sort, Quick Sort, & Optimized Bubble Sort

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories