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:

Go to the source code of this file.

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

Definition in file quick_sort_iterative.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 128 of file quick_sort_iterative.cpp.

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

tests()

void tests

(

)

Self-test implementations.

Returns

void

Definition at line 94 of file quick_sort_iterative.cpp.

{
    //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";
}