quick_sort_iterative.cpp File Reference

Quick Sort without recursion. This method uses the stack instead. Both recursive and iterative implementations have O(n log n) best case and O(n^2) worst case. More...

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cassert>

Include dependency graph for quick_sort_iterative.cpp:

Namespaces
namespace	sorting
	for working with vectors

Functions
int	sorting::partition (std::vector< int > &arr, int start, int end)
	The partition function sorts the array from start to end and uses the last element as the pivot.
void	sorting::iterativeQuickSort (std::vector< int > &arr)
	The main sorting function.
void	tests ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Quick Sort without recursion. This method uses the stack instead. Both recursive and iterative implementations have O(n log n) best case and O(n^2) worst case.

https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive https://en.wikipedia.org/wiki/Quicksort https://www.geeksforgeeks.org/iterative-quick-sort/

Author

Sebe324

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

{
    tests(); // run self test implementation
    return 0;
}

Here is the call graph for this function:

tests()

void tests

(

)

Self-test implementations.

Returns

void

{
    //TEST 1 - Positive numbers
    std::vector<int> case1={100,534,1000000,553,10,61,2000,238,2756,9,12,56,30};
    std::cout<<"TEST 1\n";
    std::cout<<"Before: \n";
    for(auto x : case1) std::cout<<x<<",";
    std::cout<<"\n";
    sorting::iterativeQuickSort(case1);
    assert(std::is_sorted(std::begin(case1),std::end(case1)));
    std::cout<<"Test 1 succesful!\n";
    std::cout<<"After: \n";
    for(auto x : case1) std::cout<<x<<",";
    std::cout<<"\n";
 
    //TEST 2 - Negative numbers
    std::vector<int> case2={-10,-2,-5,-2,-3746,-785,-123, -452, -32456};
    std::cout<<"TEST 2\n";
    std::cout<<"Before: \n";
    for(auto x : case2) std::cout<<x<<",";
    std::cout<<"\n";
    sorting::iterativeQuickSort(case2);
    assert(std::is_sorted(std::begin(case2),std::end(case2)));
    std::cout<<"Test 2 succesful!\n";
    std::cout<<"After: \n";
    for(auto x : case2) std::cout<<x<<",";
    std::cout<<"\n";
}

Here is the call graph for this function: