/* Quick Sort using Template */
#include<iostream>
using namespace std;

/* Preprocessor */
#define get_size(array) (sizeof((array))/sizeof((array[0])))

template<class t>
class sorting {
	t *list;
	public:
		sorting(t *data, int size) {
			list = data;
			quick_sort(0, size-1);
		}

		/* Sorting data using quick sort algorithm */
		void quick_sort(int start, int end) {
			int i = start;
			int j = end;
			t pivot = list[(start + end) /2];
			if(i <= j) {
				while(list[i] < pivot)
					i++;
				while(pivot < list[j])
					j--;
			}
			if(i <= j) {
				t temp = list[i];
				list[i] = list[j];
				list[j] = temp;
				i++;
				j--;
			}
			if(start < j)
				quick_sort(start,j);
			if(i < end)
				quick_sort(i,end);
		}
};

int main() {

	/* Sort integer */
	int idata[] = {9,5,1,4,0,3,7,6,2,8};
	sorting<int> isrt(idata, get_size(idata));
	cout << "\nAfter sort:" << endl;
	for(int i = 0; i < get_size(idata); i++)
		cout << idata[i] << endl;

	/* Sort float */
	float fdata[] = {9.5,5.12,1.32,4.4,0.3,3.4,7.8,6.9,2.7,8.9};
	sorting<float> fsrt(fdata, get_size(fdata));
	cout << "\nAfter sort:" << endl;
	for(int i = 0; i < get_size(fdata); i++)
		cout << fdata[i] << endl;

	/* Sort string */
	string sdata[] = {"to","be","add","java","c++","python","sorting","new","search","c"};
	sorting<string> ssrt(sdata, get_size(sdata));
	cout << "\nAfter sort:" << endl;
	for(int i = 0; i < get_size(sdata); i++)
		cout << sdata[i] << endl;

}


          /****** Output ******/
          
After sort:

0

1

2

3

4

5

6

7

8

9



After sort:

0.3

1.32

2.7

3.4

4.4

5.12

6.9

7.8

8.9

9.5



After sort:

add

be

c

c++

java

new

python

search

sorting

to