Implementing quick-sort into stack

This is my code, I just really don't understand what I'm missing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <time.h>
#include <windows.h>
using namespace 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;
	}
	else if(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){
		return false;
	}
	else if(s != NULL){
		return true;
	}
}

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");
}
Last edited on
Topic archived. No new replies allowed.