// Sorting.cpp : 

#include <iostream.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10

class myNumbers {

private:
	int numbers[SIZE];
	int temp[SIZE];
	
public:
	
	myNumbers();

	void bubbleSort(void);

	void insertionSort(void);

	void selectionSort(void);

	void shellSort(void);

	void heapSort();
	void siftDown(int,int);

	void mergeSort();
	void m_sort(int left, int right);
	void merge(int left, int mid, int right);

	void quickSort();
	void q_sort(int,int);

	void displayNumbers(void);
	void displayTempNumbers(void);
	
};

myNumbers :: myNumbers(){
	int i;
	srand( (unsigned)time( NULL ) );

	for (i=0;i<SIZE;++i){
		numbers[i]=rand ();
	}
	
}
void myNumbers::bubbleSort (void){
	int i, j, temp;

	for (i = (SIZE - 1); i >= 0; i--){
		for (j = 1; j <= i; j++){
			if (numbers[j-1] > numbers[j]){
				temp = numbers[j-1];
				numbers[j-1] = numbers[j];
				numbers[j] = temp;
			}
		}
	}
}

void myNumbers::insertionSort(){
	int i, j, index;

	for (i=1; i < SIZE; i++){
		index = numbers[i];
		j = i;
		while ((j > 0) && (numbers[j-1] > index)){
			numbers[j] = numbers[j-1];
			j = j - 1;
		}
		numbers[j] = index;
	}
}

void myNumbers::selectionSort(){

	int i, j;
	int min, temp;

	for (i = 0; i < SIZE-1; i++){
		min = i;
		for (j = i+1; j < SIZE; j++){
			if (numbers[j] < numbers[min])
				min = j;
		}
		temp = numbers[i];
		numbers[i] = numbers[min];
		numbers[min] = temp;
	}
}

void myNumbers::shellSort()
{
	int i, j, increment, temp;

	increment = 3;
	while (increment > 0){
		for (i=0; i < SIZE; i++){
			j = i;
			temp = numbers[i];
			while ((j >= increment) && (numbers[j-increment] > temp)){
				numbers[j] = numbers[j - increment];
				j = j - increment;
			}
			numbers[j] = temp;
		}
		if (increment/2 != 0)
			increment = increment/2;
		else if (increment == 1)
			increment = 0;
		else
			increment = 1;
	 }
}

void myNumbers::heapSort()
{
  int i, temp;

  for (i = (SIZE / 2)-1; i >= 0; i--)
    siftDown(i,SIZE);

  for (i = SIZE-1; i >= 1; i--)
  {
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(0, i-1);
  }
}


void myNumbers:: siftDown(int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2 <= bottom) && (!done))
  {
    if (root*2 == bottom)
      maxChild = root * 2;
    else if (numbers[root * 2] > numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])
    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }
}


void myNumbers::displayNumbers(void){
	int i;
	for (i=0; i<SIZE;++i){
		cout<<"\n"<<numbers[i];
	}
}

void myNumbers::displayTempNumbers(void){
	int i;
	for (i=0; i<SIZE;++i){
		cout<<"\n"<<temp[i];
	}
}

void myNumbers::mergeSort()
{
  m_sort(0, SIZE - 1);
}


void myNumbers::m_sort(int left, int right)
{
  int mid;

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

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

void myNumbers::merge(int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

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

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

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

  for (i=0; i <= num_elements; i++)
  {
    numbers[right] = temp[right];
    right = right - 1;
  }
}

void myNumbers::quickSort()
{
  q_sort(0, SIZE - 1);
}


void myNumbers::q_sort(int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(left, pivot-1);
  if (right > pivot)
    q_sort(pivot+1, right);
}

int main(int argc, char* argv[])
{
	myNumbers m;

	cout<<"Before Sorting \n";
	m.displayNumbers();

	cout<<"\n\nAfter Sorting \n";

	// Call your sorting algorithm here
	m.quickSort();

	m.displayNumbers();
	cout<<endl;

	return 0;
}