#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;
void swap(int* a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
void part(int *arr_ptr, int size_arr, int *m){
if (*m != 0){
swap (arr_ptr[0],arr_ptr[*m]);
}
int x = arr_ptr[0];
int i=0;
int j=size_arr;
while(j-i>1){
bool change = false;
if(arr_ptr[i+2] <=x){
++i;
change = true;
}
if(j-1>i && arr_ptr[j-1] >= x){
--j;
change = true;
}
if(!change){
++i;
--j;
swap(arr_ptr[i], arr_ptr[j]);
}
}
if(i > 0){
swap(arr_ptr[0], arr_ptr[i]);
}
*m = i;
}
void quicksort(int *arr_ptr, int size_arr){
if(size_arr == 1){
return;
} else if (size_arr == 2){
if (arr_ptr[0] > arr_ptr[1]){
swap(arr_ptr[0],arr_ptr[1]);
}
return;
}
int beg=0;
int k = size_arr;
//while(k>1){
int m = k/2; //mediana
part(arr_ptr + beg, k, &m);
int left = m;
int right = k-1-left;
if(left <= right){
quicksort(arr_ptr+beg, left);
beg++; //+= left;
k--; //-= left;
} else {
quicksort(arr_ptr+beg+m+1, right);
k--; //-= right+1;
}
//}
}
int main()
{
int size_arr = 10;
srand(static_cast<unsigned int>(time(NULL)));
int *sort_arr = new int [size_arr];
int k=0;
for (int i = 0; i < size_arr; ++i)
{
k++;
sort_arr[i] = rand()%100;
cout << setw(3) << sort_arr[i] << " ";
if(k%5 == 0){
cout << "\n";
}
}
cout << "\n";
quicksort(sort_arr, size_arr);
for (int i = 0; i < size_arr; ++i)
{
k++;
cout << setw(3) << sort_arr[i] << " ";
if(k%5 == 0){
cout << "\n";
}
}
cout << "\n";
delete [] sort_arr;
return 0;
}char* new = new char[1];