sort.h

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <conio.h>
#ifndef SORT
#define SORT
using namespace std;
void input( int * arr, int n )
{
  srand(time(0));
	for ( int i = 0; i < n; i++ )  
	{
		arr[i] = rand()%115+1;
	}

}

void output( int * arr, int n)
{
	for ( int i = 0; i < n; i++ )
	{
		cout << arr[i] << "  ";
	}
	cout << endl;
}   

void bubbleSort (int arr [], int n)
{   int k = n;
	for (int j = 0; j < n-1; j++)
	for (int i=0; i< k-1; i++)
	{
		if (arr[i] > arr[i+1])
		{
			swap (arr[i],arr[i+1]);
		}
	}k--;
};

void shellSort( int arr [], int n)
{
	int j;
	int i = 0;
	int step = n / 2;
	while (step > 0)

	{
		j = i;
		while ((j >= 0) && (arr[j] > arr[j + step]))
		{
			swap (arr[j], arr[j+step]);
			j--; 
		}
		i++;
		if (i<n-step) continue;
		else 
		{
			step = step / 2;
			i=0;
			continue;}
	};



}

void quickSort(int *arr, int left, int right) {
	int i = left, j = right;
	int mid = arr[(left + right) / 2];

	while (i <= j) {
		while (arr[i] < mid) i++;
		while (arr[j] > mid) j--;

		if (i <= j) {
			swap(arr[i], arr[j]);
			i++;
			j--;
		}
	};

	/*cout << endl << "reference value " << mid << endl;
	cout << "left part: " << endl;
	for (int i1=left; i1<i; i1++) cout << arr[i1] << " "; cout << endl;
	cout << "right part: " << endl;
	for (int i1=j+1; i1<=right; i1++) cout << arr[i1] << " "; cout << endl;

	/* рекурсия */
	if (left < j)
		quickSort(arr, left, j);
	if (i < right)
		quickSort(arr, i, right);

}
void makeTree (int arr[], int k, int n)
{int father, baby;
father = arr[k];
while (k<=n/2)
{
	baby = 2*k;
	if (baby < n && arr[baby]<arr[baby+1]) baby ++;
	if (father >= arr[baby])
		break;
	else 
	{arr[k]=arr[baby];
	k = baby;
	arr[k] = father;}

}

};
void heapSort (int arr[], int n)
{
	int temp,i;
	for (i = ((n / 2) - 1); i >= 0; --i)
	{
		makeTree (arr, i, n-1);
	}
	for (i = n-1; i > 0; --i)
	{
		swap (arr[0],arr[i]);
		makeTree(arr, 0, i-1);
	};
} 
#endif