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