/* C++ Programming, Example answer, Exercise 4, Sheet 8  */

/* Author: Rob Miller and William Knottenbelt
   Program last changed: 30th September 2001    */

/* This program illustrates the Binary Sort algorithm. */ 

#include<iostream>
using namespace std;

const int MAX = 20;

/* Function which sorts the elements in list from 
list[left] to list[right] into ascending order */
void quick_sort(int list[MAX], int left, int right);

/* Function to swap the values of two integer variables */
void swap(int& first, int& second);

/* Function to display the contents of the array "a" up to element a[length-1] */
void display(int a[], int length);

/* Function to search for an element of 'list[]' between 'list[first]' and
'list[last]' with value 'value' */
int binary_search(int value, int list[], int first, int last);

/* START OF MAIN PROGRAM */
int main()
{
	int list[MAX];
	int count, integer, position;
	
	for (count = 0 ; count < MAX ; count++)
	{
		cout << "Enter value of element " << count << ": ";
		cin >> list[count];
	}
	
	cout << "\n\nBefore Quick Sort:\n\n";
	
	display(list,MAX);
	
	quick_sort(list, 0, MAX-1);
	
	cout << "\n\nAfter Quick Sort:\n\n";
	
	display(list,MAX);
	
	cout << "\nEnter an integer: ";
	cin >> integer;
	
	position = binary_search(integer, list, 0, MAX-1); 
	
	if (position == -1)
		cout << "The value " << integer << " is not in the list.\n";
	else
		cout << "Element 'list[" << position << "]' has the value " << integer << ".\n";
	
	return 0;
}
/* END OF MAIN PROGRAM */

/* FUNCTION DEFINITION OF quick_sort: */
void quick_sort(int list[], int left, int right)
{
	int pivot, left_arrow, right_arrow;
	
	left_arrow = left;
	right_arrow = right;
	pivot = list[(left + right)/2];
	
	do
	{
		while (list[right_arrow] > pivot)
			right_arrow--;
		while (list[left_arrow] < pivot)
			left_arrow++;
		if (left_arrow <= right_arrow)
		{
			swap(list[left_arrow], list[right_arrow]);
			left_arrow++;
			right_arrow--;
		}
	}
	while (right_arrow >= left_arrow);
	
	if (left < right_arrow)
		quick_sort(list, left, right_arrow);
	if (left_arrow < right)
		quick_sort(list, left_arrow, right);
}
/* END OF FUNCTION */

/* DEFINITION OF FUNCTION "swap" */
void swap(int& first, int& second)
{
	int temp = first;
	first = second;
	second = temp;
}
/* END OF FUNCTION DEFINITION */

/* DEFINITION OF FUNCTION "display" */
void display(int a[], int length)
{
	for (int count = 0 ; count < length ; count++)
		cout << a[count] << " ";
	cout << "\n\n";
}
/* END OF FUNCTION DEFINITION */

/* DEFINITION OF FUNCTION "binary_search" */
int binary_search(int value, int list[], int first, int last)
{
	int midpoint;

	if (first > last)
		return -1;
	else
	{
		midpoint = (first + last)/2;
		if (list[midpoint] == value)
			return midpoint;
		else if (list[midpoint] > value)
			return binary_search(value, list, first, midpoint - 1);
		else
			return binary_search(value, list, midpoint + 1, last);
	}
}
/* END OF FUNCTION DEFINITION */