Quick Sort
//g++-12 -std=c++17 -o sort.out sort.cpp && ./sort.out
#include <iostream>
#include <random>
#include <time.h>
using std::mt19937,
std::cerr;
template <class T> void swap (T* a, T* b){
T c;
c = *a;
*a = *b;
*b = c;
}
template <class T> int partition(T arr[], int low, int high){
T pivot = arr[high];
T i = (low - 1);
for(int j = low; j <= high; j++){
if(arr[j] < pivot){
i++;
swap( &arr[i], &arr[j]);
}
}
swap( &arr[i+1], &arr[high]);
return ( i + 1);
}
template <class T> void quickSort(T arr[],int low,int high){
if(low < high){
T pi=partition(arr,low,high);
quickSort(arr,low,pi-1);
quickSort(arr,pi+1,high);
}
}
int main(){
mt19937 rnd(time(NULL));
const int size = 15;
int a[size];
for(int i = 0; i < size; ++i){
a[i] = rnd() % 49 + 1;
cerr << "a[" << i << "]: " << a[i];
if(i < (size - 1)){
cerr << ", ";
}
}
cerr << "\n";
quickSort<int>(a, 0, size - 1);
for( int x = 0; x < size; ++x){
cerr << "a[" << x << "]: " << a[x];
if(x < (size - 1)){
cerr << ", ";
}
}
cerr << "\n";
return 0;
}
home