quicksort using a median of 3 partition

[rayb20]

In the process of doing a sorting algorithm project and having some trouble with quicksort using a median of 3 partition.

How should it be implemented? Is there a link that anyone can share that could provide some clarity?

Also I am receiving a link error:

"Error 1 error LNK1168: cannot open C:\Users\Documents\AlgoProj1\Debug\AlgoProj1.exe for writing C:\Users\Documents\AlgoProj1\AlgoProj1\LINK AlgoProj1"

Any assistance on either of these would be greatly appreciated.

#include <iostream>
#include "SortingHelper.h"
using namespace std;



template <class T>
class Sorting{

public:
	void selectionsort(T* data, int size);
	void insertionsort(T* data, int size);
	void mergesort(T* data, int size, T* temp);
	void quicksort(T* data, int size);

	void msort(T* data, T* temp, int l, int r);//merge sort helper
	void merge(T* data, T* temp, int l, int med, int r); // merge sort helper

	T* data;

};

template <class T> 
void selectionsort(T* data, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int min = i;

		for (int j = i + 1; j < size; j++)
		{
			if (data[j] < data[min])
			{
				min = j;
			}
			if (min != i)
			{
				swap(data[i], data[min]);
			}
		}
	}
}
template <class T> 
void insertionsort(T* data, int size)
{
	for (int i = 1; i < size; i++)
	{
		for (int j = i; j > 0 && data[j] < data[j - 1]; j--)
		{
			swap(data[j - 1], data[j]);
		}
	}
}
template <class T> 
void mergesort(T* data, int size, T* temp)
{}
template <class T> 
void quicksort(T* data, int size)
{
	
}

#ifndef __SORTING_HELPER_H
#define __SORTING_HELPER_H

#include <iostream>
using namespace std;

//Functions for allocating various integer arrays of length n
int* increasingArray(int n);
int* decreasingArray(int n);
int* zeroArray(int n);
int* randomArray(int n);

/**
Returns whether an array is in sorted order
Note:  the values in the array must be comparable with <; compilation will fail otherwise.

@param arr the array to test
@param n the length of the array
@return whether the array is sorted
*/
template <class T> bool isSorted(T* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
		if (arr[i + 1] < arr[i])
			return false;
	return true;
}

/**
Prints an array of size n, with spaces in between and a newline at the end

@param arr the array to print
@param n the length of the array
*/
template <class T> void printArray(T* arr, int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << ' ';
	cout << endl;
}

/**
Compares 3 values and returns which is the median
When two values are equal, one of the two will be indicated
Note:  these values must be comparable with <; compilation will fail otherwise.

@param a,b,c  3 values
@return 1, 2, or 3, depending on whether a, b, or c is the median
*/
template <class T> int medianof3(T a, T b, T c)
{
	if (a < c)
	{
		if (b < a)
			return 1;
		else if (c < b)
			return 3;
		else
			return 2;
	}
	else if (b < c)
		return 3;
	else if (a < b)
		return 1;
	else
		return 2;
}

/**
Swaps two values
Name capitalized to avoid potential naming conflicts

@param a,b  values to swap
*/
template <class T> void Swap(T& a, T& b)
{
	T t = a;
	a = b;
	b = t;
}

#endif 

#include "SortingHelper.h"
#include <stdlib.h>
#include <time.h>
using namespace std;

/**
Creates an array of integers 1 to n

@param n the size of the array
@return the array
*/
int* increasingArray(int n)
{
	int* arr = new int[n];
	for (int i = 0; i < n; i++)
		arr[i] = i + 1;
	return arr;
}

/**
Creates an array of integers n down to 1

@param n the size of the array
@return the array
*/
int* decreasingArray(int n)
{
	int* arr = new int[n];
	for (int i = 0; i < n; i++)
		arr[i] = n - i;
	return arr;
}

/**
Creates an array of n zeros

@param n the size of the array
@return the array
*/
int* zeroArray(int n)
{
	int* arr = new int[n];
	memset(arr, 0, n*sizeof(int));
	return arr;
}

/**
Creates a random permutation of the integers 1 to n

@param n the size of the array
@return the array
*/
int* randomArray(int n)
{
	srand(time(NULL));
	int* arr = increasingArray(n);
	for (int i = n; i > 1; i--)
	{
		int swap = rand() % i;
		Swap(arr[swap], arr[i - 1]);
	}

	return arr;
}

#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;

#include "Sorting.h"
#include "SortingHelper.h"

enum sort_t  { SELECTION, INSERTION, MERGE, QUICK };
enum input_t { INCREASING, DECREASING, CONSTANT, RANDOM };

#define DEFAULT_N     1000
#define DEFAULT_ALG   MERGE
#define DEFAULT_INPUT RANDOM

#define N_ARG         1
#define ALG_ARG       2
#define INPUT_ARG     3
#define MIN_ARGS      1
#define MAX_ARGS      4
#define PRINT_USAGE() cout << argv[0] << " [n] [algorithm] [input type]" << endl << endl << \
                              "n (optional):  size of array (default:  " << DEFAULT_N << ')' << endl << \
                              "algorithm (optional):  one of selectionsort, insertionsort, mergesort, or quicksort (simq, default mergesort)" << endl << \
                              "input type (optional):  one of increasing, decreasing, constant, or random (idcr, default random)" << endl;

int main(int argc, char** argv)
{
	int n = DEFAULT_N;
	sort_t alg = DEFAULT_ALG;
	input_t intype = DEFAULT_INPUT;
	int* data = nullptr;
	int* temp;
	clock_t start;
	clock_t timing[3];

	

	//Parse input arguments
	if (argc < MIN_ARGS || argc > MAX_ARGS)
	{
		PRINT_USAGE();
		return -1;
	}

	if (argc > N_ARG)
		n = atoi(argv[N_ARG]);

	temp = zeroArray(n);
	if (argc > ALG_ARG)
	{
		switch (argv[ALG_ARG][0])
		{
		case 's':
		case 'S':
			alg = SELECTION;
			break;
		case 'i':
		case 'I':
			alg = INSERTION;
			break;
		case 'm':
		case 'M':
			alg = MERGE;
			break;
		case 'q':
		case 'Q':
			alg = QUICK;
			break;
		default:
			cout << "Sorting algorithm not recognized\n";
		}
	}

	if (argc > INPUT_ARG)
	{
		switch (argv[INPUT_ARG][0])
		{
		case 'i': //increasing
		case 'I':
		case 'a': //ascending
		case 'A':
			intype = INCREASING;
			break;
		case 'd':  //decreasing, descending
		case 'D':
			intype = DECREASING;
			break;
		case 'c':  //constant
		case 'C':
		case 'z':  //zero
		case 'Z':
			intype = CONSTANT;
			break;
		case 'r':  //random
		case 'R':
			intype = RANDOM;
			break;
		default:
			cout << "Input array type not recognized\n";
		}
	}

	//Run sorting algorithm 3 times
	for (int i = 0; i < 3; i++)
	{
		// Initialize data
		switch (intype)
		{
		case INCREASING:
			data = increasingArray(n);
			break;
		case DECREASING:
			data = decreasingArray(n);
			break;
		case CONSTANT:
			data = zeroArray(n);
			break;
		case RANDOM:
			data = randomArray(n);
		}

		//Sort data
		//printArray(arr, n);
		start = clock();
		switch (alg)
		{
		case SELECTION:
			selectionsort(data, n);
			break;
		case INSERTION:
			insertionsort(data, n);
			break;
		case MERGE:
			mergesort(data, n, temp);
			break;
		case QUICK:
			quicksort(data, n);
		}
		timing[i] = clock() - start;
		//printArray(arr, n);

		//Verify data is sorted
		if (isSorted(data, n))
			cout << "Array successfully sorted.\n";
		else
		{
			cout << "Array incorrectly sorted.\n";
			//Time to debug...
			return -1;
		}
	}

	//Output timing results
	for (int i = 0; i < 3; i++)
		cout << "Attempt " << i + 1 << ":  " << setw(8) << (int)(timing[i] * 1000.0 / CLOCKS_PER_SEC) << " ms\n";
	cout << "Median time:     " << setw(8) << (int)(timing[medianof3(timing[0], timing[1], timing[2]) - 1] * 1000.0 / CLOCKS_PER_SEC) << " ms" << endl;

	free(data);
	free(temp);

	//Windows:  pause so window doesn't vanish
	char c;
	cout << "Type 'q' to quit:  ";
	cin >> c;
	return 0;
}

[helios]

The link errors means that the linker can't write to the file to generate the executable. The most likely cause is that there's already an instance of the program running in the background, but it can also happen if you set the output directory to a read-only device.

[rayb20]

@helios I was able to fix that, it was running in the background thank you!


Any assistance on the quicksort portion? this is what I have so far:

void quicksort(T* data, int size)
{
	if (size = 1)
	{
		return data;
	}
	int mid = (size + 1) / 2;
	int pivot = medianof3(data[0], data[mid], data[size - 1]);

	Swap(data[pivot], data[0]);

	int left = 0;
	int right = size - 1;
	do
	{
		do
		{
			left = left + 1;
		} while ((left<right) && (data[left]<=data[0]));
		do
		{
			right = right - 1;
		} while ((left<right) && (data[left] <= data[0]));
		Swap(data[left], data[right]);
	} while (left<=right);

	if (data[left] > data[0])
	{
		left = left - 1;
	}
	Swap(data[0], data[left]);

	quicksort(data,size-(left - 1));
	quicksort(data, left + 1);
}

[cire]

I'm almost certain your medianof3 does not return an index into data, since it doesn't receive any information about data, so line 8 looks wrong to me.

Line 23 looks an awful lot like a copy and paste of line 19, and it probably shouldn't be.

[Edit: On closer inspection I see that you supply the code for medianof3 in an earlier post. It definitely does not return an index into data, so line 8 is definitely wrong.]

[Duthomhas]

Median of three should sort the three elements and always return the middle element.

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/#pivot-median-of-three

I can't examine your code ATM. (I'll give it a look tomorrow.)
Hope this helps.