Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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
129{
130 tests(); // run self test implementation
131 return 0;
132}
void tests()
Self-test implementations.
Definition quick_sort_iterative.cpp:94
Here is the call graph for this function:

◆ tests()

void tests ( )

Self-test implementations.

Returns
void
95{
96 //TEST 1 - Positive numbers
97 std::vector<int> case1={100,534,1000000,553,10,61,2000,238,2756,9,12,56,30};
98 std::cout<<"TEST 1\n";
99 std::cout<<"Before: \n";
100 for(auto x : case1) std::cout<<x<<",";
101 std::cout<<"\n";
103 assert(std::is_sorted(std::begin(case1),std::end(case1)));
104 std::cout<<"Test 1 succesful!\n";
105 std::cout<<"After: \n";
106 for(auto x : case1) std::cout<<x<<",";
107 std::cout<<"\n";
108
109 //TEST 2 - Negative numbers
110 std::vector<int> case2={-10,-2,-5,-2,-3746,-785,-123, -452, -32456};
111 std::cout<<"TEST 2\n";
112 std::cout<<"Before: \n";
113 for(auto x : case2) std::cout<<x<<",";
114 std::cout<<"\n";
116 assert(std::is_sorted(std::begin(case2),std::end(case2)));
117 std::cout<<"Test 2 succesful!\n";
118 std::cout<<"After: \n";
119 for(auto x : case2) std::cout<<x<<",";
120 std::cout<<"\n";
121}
T begin(T... args)
T end(T... args)
T is_sorted(T... args)
void iterativeQuickSort(std::vector< int > &arr)
The main sorting function.
Definition quick_sort_iterative.cpp:58
Here is the call graph for this function: