Quick sort and merge sort together using both vectors and arrays.

[ItecKid]

So basically, my assignment was to write quick sort and merge sort using both vectors and arrays, and time how long it takes to sort the the arrays and vectors of various sizes. However, the code is producing inconsistent results. Sometimes it seg faults, other times it produces unfriendly messages about memory corruption.

Code is as follows:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <time.h>
using namespace std;

//function parameters
vector <int> merge (const vector <int> &left, const vector <int> &right);
vector <int> merge_sort (const vector <int> &list);
void q_sort(int list[], int left, int right);
void m_sort(int list[], int temp[], int left, int right);
void merge(int list[], int temp[], int left, int mid, int right);
void q_sort(vector <int> &list, int left, int right);

//merge sort with vectors
vector <int> merge_sort (const vector <int> &list)
{
	vector <int> left;
	vector <int> right;
	vector <int> result;

	if (list.size() <= 1) {           //returns the list if it is only 1 or less numbers
		return list;
	}

	int middle = (list.size() / 2);   //creates a pivot point

	for (unsigned int i = 0; i < middle; i++) {        //places all the numbers below the mid-point into a vector
		left.push_back(list.at(i));
	}

	for (unsigned int i = middle; i < list.size(); i++) {      //places all the numbers above the mid-point into a vector
		right.push_back(list.at(i));
	}

	left = merge_sort(left);
	right = merge_sort(right);
	result = merge(left, right);

	return result;
}

vector <int> merge (const vector <int> &left, const vector <int> &right)
{
	vector <int> result;

	const int left_size = left.size(), right_size = right.size();   //creates indices for the vectors
	int left_index = 0, right_index = 0;

	while (left_index < left_size && right_index < right_size) {
		if (left[left_index] < right[right_index]) {
			result.push_back(left[left_index]);             //append left index to result when while statements are true
			left_index++;
		} 
		else {
			result.push_back(right[right_index]);           //append right index to result when while statements are false
			right_index++;
		}
	}

	if (left_index == left_size) {
		while (right_index < right_size) {
			result.push_back(right[right_index]);
			right_index++;
		}
	} 
	else {
		while (left_index < left_size) {
			result.push_back(left[left_index]);
			left_index++;
		}
	}
	return result;
}
//end merge sort with vectors

//merge sort with arrays
void mergeSort(int list[], int size)
{
	int *temp = NULL;             //usuage of dynamic array to avoid segmentation fault
	temp = new int [ size / 2 ];
	m_sort(list, temp, 0, size - 1);
}


void m_sort(int list[], int temp[], int left, int right)
{
	int mid;

	if (right > left) {
		mid = (right + left) / 2;
		m_sort(list, temp, left, mid);
		m_sort(list, temp, mid+1, right);

		merge(list, temp, left, mid+1, right);
	}
}

void merge(int list[], int temp[], int left, int mid, int right)
{
	int left_end, num_elements, temp_pos;

	left_end = mid - 1;
	temp_pos = left;
	num_elements = right - left + 1;

	while ((left <= left_end) && (mid <= right)) {
		if (list <= list[mid]) {
			temp[temp_pos] = list;
			temp_pos = temp_pos + 1;
			left = left + 1;
		}
		else {
			temp[temp_pos] = list[mid];
			temp_pos = temp_pos + 1;
			mid = mid + 1;
		}
	}

	while (left <= left_end) {
		temp[temp_pos] = list;
		left = left + 1;
		temp_pos = temp_pos + 1;
	}
	while (mid <= right) {
		temp[temp_pos] = list[mid];
		mid = mid + 1;
		temp_pos = temp_pos + 1;
	}

	for (int i=0; i <= num_elements; i++) {
		list = temp;
		right = right - 1;
	}
}
//end merge sort with arrays

//quick sort with vectors
void quick_sort(vector <int> &list)
{
  q_sort(list, 0, list.size() - 1);
}


void q_sort(vector <int> &list, int left, int right)
{
	int pivot, l_hold, r_hold;
	l_hold = left;
	r_hold = right;
	pivot = list;

	while (left < right) {
		while ((list >= pivot) && (left < right)) {
			right--;
		}

		if (left != right) {
			list = list;
			left++;
		}

		while ((list <= pivot) && (left < right)) {
			left++;
		}

		if (left != right) {
			list = list;
			right--;
		}
	}

	list = pivot;
	pivot = left;
	left = l_hold;
	right = r_hold;

	if (left < pivot) {
		q_sort(list, left, pivot - 1);
	}

	if (right > pivot) {
		q_sort(list, pivot+1, right);
	}
}
//end quick sort with vectors

//quick sort with arrays
void quicksort(int list[], int size)
{
  q_sort(list, 0, size - 1);
}


void q_sort(int list[], int left, int right)
{
	int pivot, l_hold, r_hold;
	l_hold = left;
	r_hold = right;
	pivot = list;

	while (left < right) {
		while ((list >= pivot) && (left < right)) {
			right--;
		}

		if (left != right) {
			list = list;
			left++;
		}

		while ((list <= pivot) && (left < right)) {
			left++;
		}

		if (left != right) {
			list = list;
			right--;
		}
	}

	list = pivot;
	pivot = left;
	left = l_hold;
	right = r_hold;

	if (left < pivot) {
		q_sort(list, left, pivot-1);
	}

	if (right > pivot) {
		q_sort(list, pivot+1, right);
	}
}
//end quick sort with arrays

int main (void)
{
	srand (time(NULL));

	clock_t start;
	clock_t end;

	//create a series of 20 random integers, then add them to the vector
	vector <int> random_list1;
	for (int i = 0; i < 20; i++) {
		random_list1.push_back(rand());
	}

	for (int i = 0; i < random_list1.size(); i++) {
		cout << random_list1.at(i) << "\n" << flush;
	}

	cout << "\n" << flush;

	vector <int> sort1;
	sort1 = merge_sort (random_list1);

	for (unsigned int i = 0; i < sort1.size(); i++) {
		cout << sort1.at(i) << "\n" << flush;
	}

	cout << "\n" << flush;

	vector <int> random_lista;
	for (unsigned int i = 0; i < 20; i++) {
		random_lista.push_back(rand());
	}

	for (unsigned int i = 0; i < random_lista.size(); i++) {
		cout << random_lista.at(i) << "\n" << flush;
	}

	cout << "\n" << flush;

	quick_sort(random_lista);
	
	for (unsigned int i = 0; i < random_lista.size(); i++) {
		cout << random_lista.at(i) << "\n" << flush;
	}

	int random1[20];

	for (int i = 0; i < 20; i++) {
		random1[i] = rand();
		cout << random1[i] << "\n" << flush;
	}
	cout << "\n" << flush;

	mergeSort(random1, 20);

	for (int i = 0; i < 20; i++) {
		cout << random1[i] << "\n" << flush;
	}

	int randoma[20];
	for (int i = 0; i < 20; i++) {
		randoma[i] = rand();
		cout << randoma[i] << "\n" << flush;
	}
	cout << "\n";
	quicksort(randoma, 20);

	for (int i = 0; i < 20; i++) {
		cout << randoma[i] << "\n" << flush;
	}

	/* end of testing, begin time */

	vector <int> random_list2;
	for (int i = 0; i < 32000; i++) {
		random_list2.push_back(rand());
	}

	vector <int> sort2;
	start = clock ();
	sort2 = merge_sort(random_list2);
	end = clock ();

	cout << "Merge Sort (vector, 32,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	vector <int> random_listb;
	for (int i = 0; i < 32000; i++) {
		random_listb.push_back(rand());
	}

	start = clock ();
	quick_sort(random_listb);
	end = clock ();

	cout << "Quick Sort (vector, 32,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	vector <int> random_list3;
	for (int i = 0; i < 64000; i++) {
		random_list3.push_back(rand());
	}

	vector <int> sort3;
	start = clock ();
	sort3 = merge_sort(random_list3);
	end = clock ();

	cout << "Merge Sort (vector, 64,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	vector <int> random_listc;
	for (int i = 0; i < 64000; i++) {
		random_listc.push_back(rand());
	}

	start = clock ();
	quick_sort(random_listc);
	end = clock ();

	cout << "Quick Sort (vector, 64,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	vector <int> random_list4;
	for (int i = 0; i < 128000; i++) {
		random_list4.push_back(rand());
	}

	vector <int> sort4;
	start = clock ();
	sort4 = merge_sort(random_list4);
	end = clock ();

	cout << "Merge Sort (vector, 128,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	vector <int> random_listd;
	for (int i = 0; i < 128000; i++) {
		random_listd.push_back(rand());
	}

	start = clock ();
	quick_sort(random_listd);
	end = clock ();

	cout << "Quick Sort (vector, 128,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	cout << "\n" << flush;

	int random2[32000];
	for (int i = 0; i < 32000; i++) {
		random2[i] = rand();
	}

	start = clock ();
	mergeSort(random2, 32000);
	end = clock ();

	cout << "Merge Sort (arrays, 32,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	int randomb[32000];
	for (int i = 0; i < 32000; i++) {
		randomb[i] = rand();
	}

	start = clock ();
	quicksort(randomb, 32000);
	end = clock ();

	cout << "Quick Sort (arrays, 32,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;
/*********/
	int random3[64000];
	for (int i = 0; i < 64000; i++) {
		random3[i] = rand();
	}

	start = clock ();
	mergeSort(random3, 64000);
	end = clock ();

	cout << "Merge Sort (arrays, 64,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	int randomc[64000];
	for (int i = 0; i < 64000; i++) {
		randomc[i] = rand();
	}

	start = clock ();
	quicksort(randomc, 64000);
	end = clock ();

	cout << "Quick Sort (arrays, 64,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	int random4[128000];
	for (int i = 0; i < 128000; i++) {
		random4[i] = rand();
	}

	start = clock ();
	mergeSort(random4, 128000);
	end = clock ();

	cout << "Merge Sort (arrays, 128,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;

	int randomd[128000];
	for (int i = 0; i < 128000; i++) {
		randomd[i] = rand();
	}

	start = clock ();
	quicksort(randomd, 128000);
	end = clock ();

	cout << "Quick Sort (arrays, 128,000 elements) " << (float) (end - start) / CLOCKS_PER_SEC << " seconds \n" << flush;
	

	return 0;
}

[ArkM]

Irrespective of hidden errors in your code (I'll see them later) some remarks:
1. An std::vector object data area IS an array. An address of the 1st vector element points to the start of the vector data array. So your comparative studies are aimless ones: you may sort a vector as an array and no need in special std::vector sorting codes.
For example, suppose we have an array of double and a vector<double> objects with size n and a function sort(array,size):

const size_t n = 10000;
void sort(double* array, size_t size);
double a[n];
vector<double> v(n);
// initialize a and v with identical data
// Now you can process both a and v with sort:
sort(a,sizeof a/sizeof *a);
sort(&v[0],v.size());

It's an absolutely standard-conformant approach.

2. Suppose you want to test std::vector::operator[](size_t) overheads. It's the only sensible subject though it's a well-known fact that no such overheads in good STL implementations. In that case the simplest method is to define sorting argorithm as a template. Better debug a single generic function code than have troubles with two essentially identical ones;)