#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectionSort(int *mas, int size);
void quickSort(int *mas1, int size);
int main()
{
	system("chcp 1251");
	int mas[20] = {4, 9, 7, 6, 2, 3, 8, 1, 5, 10, 16, 13, 11, 12, 18, 15, 17, 19, 20, 14};
	printf("Ìàññèâ äî ñîðòèðîâêè:\n");
	for(int i = 0; i < 20; i++)
		printf("%d\n", mas[i]);
	selectionSort(mas, 20);
	int mas1[20] = {40, 90, 70, 60, 20, 30, 80, 10, 50, 100, 160, 130, 110, 120, 180, 150, 170, 190, 200, 140};
	printf("\nÌàññèâ äî ñîðòèðîâêè:\n");
	for(int i = 0; i < 20; i++)
		printf("%d\n", mas1[i]);
	float start = clock();
	quickSort(mas1, 19);
	float end = clock();
	printf("Âðåìÿ ðàáîòû àëãîðèòìà: %f\n", (end-start)/1000);
	printf("Ðåçóëüòàò ðàáîòû áûñòðîé ñîðòèðîâêè:\n");
	for(int i = 0; i < 20; i++)
		printf("%d\n", mas1[i]);


	return 1;
}
int l = 0;
void quickSort(int *mas1, int size)
{
	int i = 0;
	int j = size;
	int p = mas1[size/2];
	int temp;
	do
	{
		while(mas1[i] < p)
			i++;
		while(mas1[j] > p)
			j--;
		if(i <= j)
		{
			temp = mas1[i];
			mas1[i] = mas1[j];
			mas1[j] = temp;
			i++;
			j--;
		}
	} while(i <= j);
	l++;
	printf("Òåêóùàÿ èòåðàöèÿ: %d\n", l);
	for(int k = 0; k < size+1; k++)
			printf("%d\n", mas1[k]);
	if(j > 0)
		quickSort(mas1, j);
	if(size > i)
		quickSort(mas1+i, size-i);
}

void selectionSort(int *mas, int size)
{
	int min = 0;
	int temp = 0;
	for(int i = 0; i < size; i++)
	{
		min = i;
		for(int j = i+1; j < size; j++)
		{
			if(mas[j]<mas[min])
				min = j;
		}
		temp = mas[i];
		mas[i] = mas[min];
		mas[min] = temp;
		printf("Òåêóùàÿ èòåðàöèÿ: %d\n", i+1);
		for(int k = 0; k < size; k++)
			printf("%d\n", mas[k]);
	}
	float time = clock();
	printf("Âðåìÿ ðàáîòû àëãîðèòìà: %f\n", time/1000);
}