#include <iostream>
#include <time.h>
#include <windows.h>
usingnamespace std;
template <class Type>class Stack;
template<class Type>
struct node{
int data;
node * link;
};
template<class Type>
class Stack{
private:
node<Type> * top;
public:
Stack();
Stack(const Stack&A);
Type Push(Type n);
Type Pop();
Type Seek();
bool isnotempty();
};
template<class Type>
Stack<Type> :: Stack(){
top = NULL;
}
template<class Type>
Type Stack<Type> :: Push(Type n){
node<Type> * s = top;
node<Type> * p = new node<Type>;
p -> data = n;
if(top == NULL){
s = p;
top = p;
p -> link = NULL;
return 1;
}
elseif(top != NULL){
p -> link = top;
top = p;
return 1;
}
cout << "Sorry but a new stack could not be created \n";
return 0;
}
template<class Type>
Type Stack<Type> :: Pop(){
node<Type> * s = top;
int a;
if(isnotempty()){
a = s -> data;
s = s-> link;
top = s;
return a;
}
if(s == NULL){
top = NULL;
cout << "\nStack Empty"; //If the command calling this is correct, then this shouldn't display
return 0;
}
}
template<class Type>
bool Stack<Type> :: isnotempty (){
node<Type> * s = top;
if(s == NULL){
returnfalse;
}
elseif(s != NULL){
returntrue;
}
}
template<class Type>
int quicksort(int *p, int n, Stack<Type>&C){
int i,j;
i = 0;
j = n-1;
int temp;
int left = 0;
int right = n-1;
int pivot;
int piv;
C.Push(right);
C.Push(left);
while(C.isnotempty()){
i = C.Pop();
j = C.Pop();
piv = (i + j)/2;
pivot = p[piv];
while (i <= j) { //Partition
while (p[i] < pivot)i++; //i progresses as long as it's stored value is less than the pivot
while (p[j] >= pivot)j--; //j depresses as long as it's stored value is more than the pivot
if (i <= j) { //After the two positions reach a stand still this function will run itself, it swaps them if the above criteria is still met
temp = p[i];
p[i] = p[j];
p[j] = temp;
i++;
j--;
}
}
temp = p[i];
p[i] = p[piv];
p[piv] = temp;
C.Push(right);
C.Push(piv);
C.Push(piv);
C.Push(left);
}
}
int main() {
srand(time(NULL));
int n = 18;
int a[n];
Stack<int> B;
for(int i = 0; i<n; i++) a[i] = rand()%20;
for(int i = 0; i < n; i++) cout << a[i] << " ";
quicksort(a, n, B);
cout << endl << "\nSorted array is now \n";for(int i = 0; i < n; i++) cout << a[i] << " ";
cout << "\n";
system ("PAUSE");
}