Selection Sort/Quick Sort

[itcsr]

Im writing a program to preform quick sort and selection sort on the same list,
and print out the result of each with the time it takes for both Sorting algorithms to sort the list (time I didnt work on yet), my issue is that the same list is printed for the quick and selection sort where as the quick sort has a pivot in the middle and numbers less than it on the left and greater than it on the right without being sorted, thats what Ive been tought ..

so base line to my issue is that, selection sort is printed in a right way,
quick sort prints the same list although the list should have been modified.

Its a pretty long code, for me perhaps, so I wasnt sure if I should include all the files or not, but I will anyway..

HEADER FILE:

#ifndef ARRAYlIST_H_INCLUDED
#define ARRAYlIST_H_INCLUDED
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

template <class elemType>
class arrayListType
{
public:

	bool isEmpty() const;
	bool isFull() const;
	int listSize()const;
	int maxListSize()const;
	int partition(int first, int last);
	void print() const;
	void insert(const elemType& insertItem);
	void insertionSort();
	void swap(int first, int second);
	void recQuickSort(int first, int last);
	void quickSort();


	arrayListType(int size = 10000);

	~arrayListType();
	

protected:
	int length;
	int maxSize;
	elemType *list;
};

template <class elemType>
bool arrayListType<elemType>::isEmpty() const
{
	return (length == 0);
}

template <class elemType>
bool arrayListType<elemType>::isFull() const
{
	return (length == maxSize);
}

template <class elemType>
arrayListType<elemType>::arrayListType(int size)
{
	if(size == 0)
	{
		cout<<"The array size must be positive" 
			"creating array of size 100."<<endl;
		maxSize = 100;
	}
	else
		maxSize = size;

	length = 0;

	list = new elemType[maxSize];
	assert(list!=NULL);
	
}

template <class elemType>
void arrayListType<elemType>::print() const 
{
	for (int i = 0; i<length; i++)
	cout<<list[i]<<" ";

	cout<<endl;
}

template <class elemType>
void arrayListType<elemType>::insert(const elemType& insertItem)
{
	if (length==maxSize)
	cout<<"Array is Full"<<endl;
	else if (length == 0)
		list[length++] = insertItem;
	else 
		list[length++] = insertItem;
		
	
}

template <class elemType>
int arrayListType<elemType>::listSize()const
{
		return length;
}

template <class elemType>
int arrayListType<elemType>::maxListSize()const
{
		return maxSize;
}

template <class elemType>
int arrayListType<elemType>::partition(int first, int last)
{
	elemType pivot;

	int index, smallIndex;

	swap(first, (first+last)/2);

	pivot = list[first];
	smallIndex = first;

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

		swap(first, smallIndex);

		return smallIndex;
}

template <class elemType>
arrayListType<elemType>::~arrayListType()
{
	delete [] list;
}

template <class elemType>
void arrayListType<elemType>::insertionSort()
{
	int firstOutOfOrder, location;
	elemType temp;

	for (firstOutOfOrder = 1; firstOutOfOrder < length;
								firstOutOfOrder++)
		if (list[firstOutOfOrder] < list[firstOutOfOrder-1])
		{
			temp = list[firstOutOfOrder];
			location = firstOutOfOrder;

			do
			{
				list[location] = list[location -1];
				location--;
			}
			while (location > 0 && list[location - 1] > temp);

			list[location]=temp;
		}
}

template <class elemType>
void arrayListType<elemType>::swap(int first, int second)
{
	elemType temp;

	temp = list[first];
	list[first] = list[second];
	list[second] = temp;
}

template <class elemType>
void arrayListType<elemType>::recQuickSort(int first, int last)
{
	int pivotLocation;

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

}

template <class elemType>
void arrayListType<elemType>::quickSort()
{
	recQuickSort(0, length -1);
}
#endif 

MAIN im using:

#include "arrayList.h"
using namespace std;

int main()
{
	arrayListType<int> a;
    int number, range;

	cout<<"Enter amount of Numbers : "<<endl;
	cin>>number;
	
	cout<<"Enter Range of Numbers : "<<endl;
	cin>>range;
	
	while(a.listSize()!=number)
	{
		a.insert(rand()%range);
	}
	
	cout<<"Size is :"<<a.listSize()<<endl;
	
	cout<<"The list before Sorting is : "<<endl;
	a.print();
	cout<<endl;

	cout<<"The list after Sorting is :"<<endl;

	for (int i=0;i<a.listSize();i++)
	{
		a.insertionSort();
		
	}

	a.print();
	cout<<endl;

	cout<<"*************Quick Sort****************"<<endl;

	
	for (int i=0;i<a.listSize();i++)
	{
		a.quickSort();
		
	}
	
	
	a.print();


	cout<<endl;

	

	return 0;

	
}

help/hints are appreciated and thanked for in advance ^^

[Pravesh Koirala]

quick sort has a pivot in the middle and numbers less than it on the left and greater than it on the right without being sorted, thats what Ive been tought ..

hmm..? As far as I know, in quicksort, you select an arbitary pivot. And then transfer all the elements less than pivot to the left and all those greater than the pivot to the right instead of selecting a pivot which already has the above mentioned configuration.

quick sort prints the same list although the list should have been modified.

What do you exactly mean by modified?

[itcsr]

Modified as in what you said,
for a list such as 2 0 6 2 "4" 3 5 9 1

my pivot will be 4 using the code I wrote above, it should resort it to :
2 0 3 1 "4" 6 5 9 ("pivot")

but wht happens when I print the list after the quicksort is:
0 1 2 2 3 4 5 6 9

[Pravesh Koirala]

You do know about quicksort, don't you?

And no, it shouldn't resort it to

2 0 3 1 "4" 6 5 9 ("pivot")

It MUST resort to

0 1 2 2 3 4 5 6 9

After all, you want to sort it don't you?