Median of Three Quick Sort

Peter_APIIT · #1 01-Oct-2008, 10:04

Hello to all expert developer, i looking for this algorithm.

I already wrote the simplest qs which pivot is first element in list but this sort is extremely inefficient and almost same with selection sort.

Therefore, i looking for Median of Three Quick Sort.

Thanks in advance for any help.

L7Sqr · #2 01-Oct-2008, 20:21

her you go
Of course, I have not tested it or even looked at the implementation. There are comments there though...

Peter_APIIT · #3 03-Oct-2008, 04:09

I will have a look.

Thanks.

Peter_APIIT · #4 04-Oct-2008, 23:28

I have code it but seems some logic error inside.

Below is is my code:

CPP / C++ / C Code:


#ifndef MEDIAN3QUICKSORT
#define MEDIAN3QUICKSORT

#include <algorithm>

namespace mystd
{
	template <typename T>
	void Median(T* sortee, T* pivotValue, 
		int left, int right)
	{
		int middle = (left + right) / 2 ;
		if (*(sortee + left) > *(sortee + middle))
		{
			std::swap(*(sortee + left), 
				*(sortee + middle));
		}

		if (*(sortee + left) > *(sortee + right))
		{
			std::swap(*(sortee + left), 
				*(sortee + right));
		}

		if (*(sortee + middle) > *(sortee + right))
		{
			std::swap(*(sortee + middle),
				*(sortee + right));
		}

		// Put middle element in right - 1
		std::swap(*(sortee + middle), 
			*(sortee + right -1));
		*pivotValue = *(sortee + right -1);

	}

	template <typename T>
	void Partition(T* sortee, T* pivotValue, 
		int left, int right)
	{
		int leftIncrement = left;
		int rightDecrement = right;
		
		while(leftIncrement < rightDecrement)
		{
			while(*(sortee + leftIncrement) 
				< *pivotValue)
			{
				leftIncrement++;
			}

			while(*(sortee + rightDecrement)
				> *pivotValue)
			{
				rightDecrement--;
			}

			if (leftIncrement < rightDecrement)
			{
				std::swap(*(sortee + leftIncrement),
					*(sortee + rightDecrement));
			}
		}

		/* 
			leftIncrement is pivotIndex because
			stop at selt comparison
		*/
		// Restore pivot 
		std::swap(*(sortee + leftIncrement),
			*(sortee + right - 1));
	}

	template <typename T>
	int FindIndex(T* sortee, T pivotValue, 
			int right)
	{
		int pivotIndex = 0;
		for (int loop=0;loop<right;++loop)
		{
			if (*(sortee + loop) == pivotValue)
			{
				pivotIndex = loop;
			}
		}

		return pivotIndex;
	}

	template <typename T>
	void M3QuickSort(T* sortee, int left, int right)
	{
		const int CUTOFF = 0; T pivotValue = 0, pivotIndex = 0;
		if (left + CUTOFF < right)
		{
			Median(sortee, &pivotValue, left, right);
			Partition(sortee, &pivotValue, left, right);
			
			pivotIndex = FindIndex(sortee, pivotValue, right);
			
			M3QuickSort(sortee, left, pivotIndex - 1);
			M3QuickSort(sortee, pivotIndex + 1, right);
		}
		
	}

}

#endif

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <functional>

#include "Median3QuickSort.h"



using std::cin;
using std::cout;

using mystd::M3QuickSort;

// ================================================
void generate(int number [], int size);

// =================================================
int main(int argc, char *argv [])
{
	int size = 8;

	int number[8] = {
		90, 45, 67, 34, 190, 
		 1, 30, 78};;
	
	cout << "Before sort\n";
	for (int loop=0;loop< size;++loop)
	{
		cout << "Value is " << *(number + loop) << "\n";
	}
	
	M3QuickSort(number,  0, size-1);

	cout << "\n\n\n";
	cout << "After sort\n";
	for (int loop=0;loop< size;++loop)
	{
		cout << "Value is " << *(number + loop) << "\n";
	}


	cout << "\n\n\n";

	size = 5;
	char alphabet[] = {'z', 'c', 'a', 'f', 'e'};

	
	cout << "Before sort\n";
	for (int loop=0;loop< size;++loop)
	{
		cout << "Value is " << *(alphabet + loop) << "\n";
	}
	
	M3QuickSort(alphabet,  0, size-1);

	cout << "\n\n\n";
	cout << "After sort\n";
	for (int loop=0;loop< size;++loop)
	{
		cout << "Value is " << *(alphabet + loop) << "\n";
	}

	return 0;
}
// =================================================

Thanks.

L7Sqr · #5 05-Oct-2008, 10:06

What is the error. How do you think it is misbehaving - that is, what input is it not properly sorting?
You provide very little input (or any question) to guide us in which direction you wish to receive assistance. What is it you are having trouble with, specifically?

Peter_APIIT · #6 05-Oct-2008, 23:32

Quote:

How do you think it is misbehaving - that is, what input is it not properly sorting?

There are logic error within my program.
Yes, They can sorted about 80% of the input only.

Help is pretty appreciated by me.

L7Sqr · #7 06-Oct-2008, 09:35

An example of what is NOT sorting would be helpful (the pre-sort and post-sort items would be what is required).
None of us here has a crystal ball with which to look into your mind - details will go a long way in helping us help you with your problem.

Peter_APIIT · #8 07-Oct-2008, 03:39

Problem solved.

The problem now is when the element is less than certain CUTOFF, then i called insertionSort but also won't sort it nicely.

The insertion Sort is works in another program.

The C++ STL is intro sort which called quick sort, heap sort and insertion sort.

Below is my code

CPP / C++ / C Code:




#ifndef MEDIAN3QUICKSORT
#define MEDIAN3QUICKSORT

#include <algorithm>
#include "InsertionSort.h"

namespace mystd
{
	template <typename T>
	void Median(T* sortee, T* pivotValue, 
		int left, int right)
	{
		int middle = (left + right) / 2 ;
		
		if (*(sortee + left) > *(sortee + middle))
		{
			std::swap(*(sortee + left), 
				*(sortee + middle));
		}

		if (*(sortee + left) > *(sortee + right))
		{
			std::swap(*(sortee + left), 
				*(sortee + right));
		}

		if (*(sortee + middle) > *(sortee + right))
		{
			std::swap(*(sortee + middle),
				*(sortee + right));
		}

		// Put middle element in right - 1
		std::swap(*(sortee + middle), 
			*(sortee + right -1));
		
		*pivotValue = *(sortee + right -1);

	}

	template <typename T>
	void Partition(T* sortee, T* pivotValue, 
		int left, int right)
	{
		int leftIncrement = left;
		int rightDecrement = right - 1;
		
		while(leftIncrement < rightDecrement)
		{
			while(*(sortee + ++leftIncrement) 
				< *pivotValue)
			{
			}

			while(*(sortee + --rightDecrement)
				> *pivotValue)
			{
			}

			if (leftIncrement < rightDecrement)
			{
				std::swap(*(sortee + leftIncrement),
					*(sortee + rightDecrement));
			}
		}

		/* 
			leftIncrement is pivotIndex because
			stop at self comparison
		*/
		// Restore pivot 
		std::swap(*(sortee + leftIncrement),
			*(sortee + right - 1));

		
	}

	template <typename T>
	int FindIndex(T* sortee, T pivotValue, 
			int right)
	{
		int pivotIndex = 0;
		
		for (int loop=0;loop<right;loop++)
		{
			if (*(sortee + loop) == pivotValue)
			{
				pivotIndex = loop;
			}
		}

		return pivotIndex;
	}

	template <typename T>
	void M3QuickSort(T* sortee, int left, int right)
	{
		int size = right;
		const int CUTOFF = 10; T pivotValue = 0, pivotIndex = 0;
		
		if (left + CUTOFF < right)
		{
			Median(sortee, &pivotValue, left, right);
			Partition(sortee, &pivotValue, left, right);
			
			pivotIndex = FindIndex(sortee, pivotValue, right);
			
			M3QuickSort(sortee, left, pivotIndex - 1);
			M3QuickSort(sortee, pivotIndex + 1, right);
		}
		else
		{	
			mystd::InsertionSort(sortee, left, right);	
		}
		
	}

}

#endif






#ifndef INSERTIONSORT
#define INSERTIONSORT

namespace mystd
{

	template <typename T>
	void InsertionSort(T *sortee, int& left, int & size)
	{
		for (int loop=0;loop < size ; ++loop)
		{
			int index = loop;
			T value = *(sortee + loop);

			while(index > 0 
					&&   
					*(sortee + index - 1) > value) 
						// If left > right
			{
				// Left assign to right
				*(sortee + index) = *(sortee + index - 1); 
				--index;
			}
			*(sortee + index) = value;
		}

	}



}

#endif

Thanks for your help.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Merge sort on a linked list	Temujin_12	C++ Forum	1	06-Mar-2008 21:33
Quick sort	thagafnh	C++ Forum	0	20-Oct-2007 19:47
Quick Sort Algorithm	Peter_APIIT	C++ Forum	3	03-Oct-2007 23:45
Help quick sort template	shinx	C++ Forum	1	11-Dec-2006 15:00
SORT / ORDER BY multi columns in MySQL	misunderstood	MySQL / PHP Forum	3	01-Oct-2003 10:01

Median of Three Quick Sort

Re: Median of Three Quick Sort

Re: Median of Three Quick Sort

Re: Median of Three Quick Sort

Re: Median of Three Quick Sort

Re: Median of Three Quick Sort

Re: Median of Three Quick Sort

Re: Median of Three Quick Sort