#include <iostream>
#include <vector>
#include <time.h>
#include <stdlib.h>
using namespace std;

struct info {
	int seq;
	int num;
};

vector <info> vecinfo;

int parttion(int p, int r)
{
	int i = p - 1;
	
	for (int j = p; j < r ; j++)
	{
		if (vecinfo[j].num <= vecinfo[r].num)
		{
			i++;
			
			info temp = vecinfo[i];
			vecinfo[i] = vecinfo[j];
			vecinfo[j] = temp;
		}
	}

	info temp = vecinfo[i + 1];
	vecinfo[i + 1] = vecinfo[r];
	vecinfo[r] = temp;
	
	return i + 1;
}

void quicksort(int p, int r)
{
	if (p < r)
	{
		int q = parttion(p, r);
		quicksort(p, q - 1);
		quicksort(q + 1, r);
	}
}

void main()
{
	srand(time(NULL));

	for (int i = 0; i < 10000; i++)
	{
		info structinfo;
		structinfo.seq = i + 1;
		structinfo.num = rand();
		vecinfo.push_back(structinfo);
	}
	
	cout << "befroe sort: " << endl;
//	for (vector <info>::iterator iter = vecinfo.begin(); 
//	iter != vecinfo.end();
//	iter++)
//	{
//		cout << (*iter).seq << ":\t" << (*iter).num << endl;
//	}

	cout << endl;

	for (int j = 0; j < vecinfo.size(); j++)
	{
		cout << vecinfo[j].seq << ":\t" << vecinfo[j].num << endl;
	}

	quicksort(0, vecinfo.size() - 1);

	cout << "after sort: " << endl;
//	for (vector <info>::iterator iter2 = vecinfo.begin(); 
//	iter2 != vecinfo.end();
//	iter2++)
//	{
//		cout << (*iter2).seq << ":\t" << (*iter2).num << endl;
//	}

	cout << endl;
	
	for (int k = 0; k < vecinfo.size(); k++)
	{
		cout << vecinfo[k].seq << ":\t" << vecinfo[k].num << endl;
	}
}