Skip to content

Emmanuel Brun d'Aubignosc's site about software engineering

This is my personal blog about software and algorithms

Menu
  • About
Menu

Quick sort using modern C++

Posted on August 31, 2023August 31, 2023 by Emmanuel Brun d'Aubignosc

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <string.h>
#include <random>
#include <ctime>

using namespace std;

const int ARRAYSIZE = 1024 * 100; //1024; // * 1024;

unsigned long int itterations = 0;
int callDepth = 0;
int maxCallDepth = 0;
time_t start_time, end_time;
unsigned int duration; 

/**
 * 
 * @param aa
 */
void initRanArray(int arr[]) {

    // create source of randomness, and initialize it with non-deterministic seed
    std::random_device r;
    std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
    std::mt19937 eng{seed};

    // a distribution that takes randomness and produces values in specified range
    std::uniform_int_distribution<> dist(1, ARRAYSIZE);
    
    //// Providing a seed value
    //srand((unsigned) time(NULL));
    
    for (int i = 0; i < ARRAYSIZE; i ++) {                
	// Get a random number
	//aa[i] = rand(); 
        arr[i] = dist(eng);
    }
}

/**
 * 
 * @param bestArr
 * @param worstArr
 */
void initBestAndWorstCaseArrays(int bestArr[], int worstArr[]) {
    
    for (int i = 0; i < ARRAYSIZE; i ++) {
        
        bestArr[i] = i;
        worstArr[i] = ARRAYSIZE - i;
    }
}

/**
 * 
 * @param aa
 * @param bb
 */
void reinitArray(int tempateArray[], int destArray[]) {
    
    for (int i = 0; i < ARRAYSIZE; i ++) {
        
        destArray[i] = tempateArray[i]; 
    }
}

/**
 * 
 * @param a
 */
void printArray(int a[]) {
    
    int incr = 1;
    if (ARRAYSIZE > 200) {
        incr = ARRAYSIZE / 20;
    } 
    
    for (int i = 0; i < ARRAYSIZE; i += incr) {
        cout << i << ": " << a[i] << endl;
    }
}

/**
 * 
 * @param valArr
 * @param leftIndex
 * @param rightIndex
 */
void quickSort(int valArr[], int leftIndex = 0, int rightIndex = ARRAYSIZE - 1) {
   
    // *************************
    
    auto swap = [](int & tmp1, int & tmp2) {        
        int tmp;        
        tmp = tmp1; tmp1 = tmp2; tmp2 = tmp;
    };    
    
    // *************************
    
    auto partition = [&swap](int a[], int lindex, int rindex) {
                   
        int pivotValue = a[rindex];        
        int i = lindex - 1;        
                
        for (int j = lindex; j < rindex; j ++) {
        
            if (a[j] <= pivotValue) {                
                i ++;
                swap(a[i], a[j]);
            }
            itterations ++;
        }
        
        swap (a[i + 1], a[rindex]);
        
        return i + 1;   // return new pivot index
    };
      
    // *************************
    
    if (leftIndex < rightIndex) {
        
        int pivotIndex = partition (valArr, leftIndex, rightIndex);
        
        callDepth ++;
        if (callDepth > maxCallDepth) {
            maxCallDepth = callDepth;
        }
        quickSort(valArr, leftIndex, pivotIndex - 1);        
        quickSort(valArr, pivotIndex + 1, rightIndex);
        callDepth --;
    }    
}

/**
 * 
 * @param arr
 * @param message
 */
void sortAndPrint(int arr[], string message) {
    
    maxCallDepth = 0;
    itterations = 0;
    
    cout << "print :" << endl;
    printArray(arr);    
    cout << "start " << message << " sort" << endl;
    start_time = time(NULL);
    quickSort(arr, 0, ARRAYSIZE - 1);
    end_time = time(NULL);
    duration = end_time - start_time;
    cout << "end sort, print result" << endl;
    printArray(arr);
    cout << message << " sort duration: " << duration << endl;  
    cout << "itterations: " << itterations << endl;
    cout << "max depth: " << maxCallDepth << endl;
    cout << "*************************************" << endl;
    cout << "*************************************" << endl;
}

/*
 * 
 */
int main(int argc, char** argv) {

    cout << "main" << endl;
  
    int * randNumbers = new int[ARRAYSIZE];
    int * sortedNumbers = new int[ARRAYSIZE];
    int * invSortedNumbers = new int[ARRAYSIZE];
    
    cout << "start init" << endl;
    initRanArray(randNumbers); 
    initBestAndWorstCaseArrays(invSortedNumbers, sortedNumbers);
    
    sortAndPrint(randNumbers, "random numbers");
    sortAndPrint(invSortedNumbers, "inv sorted numbers");
    sortAndPrint(sortedNumbers, "sorted numbers");

    delete randNumbers;
    delete invSortedNumbers;
    delete sortedNumbers;
        
    return 0;
}

Related

Recent Posts

  • Leecode Valid Parentheses C++
  • Leetcode Two Sums Java
  • Leetcode Two Sums C++
  • Quick sort using modern C++

Recent Comments

No comments to show.

Archives

  • September 2023
  • August 2023

Categories

  • Leetcode
  • Uncategorized
© 2025 Emmanuel Brun d'Aubignosc's site about software engineering | Powered by Minimalist Blog WordPress Theme