C++

Forum

 
Selection Sort two stacks without arrays

Stuni (2)
Hello guys i have a course work where i have to sort two stacks with Selection Sort, but it's forbidden to use arrays.I have already thought an algorithm but it seems not to work properly if i have two same numbers.However the main stack is sorted it has just one of these two numbers.Can you please help me with that problem or at least am i working on the right direction?

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
 
void SelectionSort(stack<int> &mainStack){
	stack<int> secondaryStack = stack<int>();
	int countSortedNumbers = 0 ,countUnsortedNumbers;
	int stackLenght = mainStack.size();
	int minValue;
	while (countSortedNumbers < stackLenght) {
		minValue = mainStack.top();
		countSortedNumbers = 0;
		countUnsortedNumbers = 0;
		while (countUnsortedNumbers < stackLenght) {
			if (minValue > mainStack.top()) {
				minValue = mainStack.top();
				secondaryStack.push(mainStack.top());
				mainStack.pop();
			}
			else
			{
				secondaryStack.push(mainStack.top());
				mainStack.pop();
			}
			countUnsortedNumbers++;
		}
		mainStack.push(minValue);
		countSortedNumbers++;
		while (!secondaryStack.empty())
		{
			if (minValue == secondaryStack.top()) {
				secondaryStack.pop();
				continue;
			}
			else {
				mainStack.push(secondaryStack.top());
				secondaryStack.pop();
			}
		}
		stackLenght--;
	}
Last edited on
ne555 (10692)
> am i working on the right direction?
explain your approach
comment your code
modularize
Stuni (2)
At the beginning i take the top element from the main stack
minValue = mainStack.top();
and compare it with every element which is on the top of that stack.While i go through every top element in the main stack i push it in the second stack.
1
2
3
4
5
6
7
8
9
 
if (minValue > mainStack.top()) {
	        minValue = mainStack.top();
		secondaryStack.push(mainStack.top());
		mainStack.pop();
}
else{
		secondaryStack.push(mainStack.top());
		mainStack.pop();
}


When i find the lowest number i put in in the main stack and take back all the elements from the secondary stack and decrease the number of stackLenght so that in the next iteration that minValue doesn't take part in the comparing.
1
2
3
4
5
6
7
8
9
10
11
12
13
 
mainStack.push(minValue);
countSortedNumbers++;
while (!secondaryStack.empty()){
		if (minValue == secondaryStack.top()) {
			secondaryStack.pop();
			continue;
		}
		else {
			mainStack.push(secondaryStack.top());
			secondaryStack.pop();
		}
	}
stackLenght--;

And i repeat that as long as i sort the whole stack.
I think my problem comes from these lines 
1
2
3
4
 
if (minValue == secondaryStack.top()) {
		secondaryStack.pop();
		continue;
}

but i still cannot find the solution.
ne555 (10692)
You may count the frequency of the minValue, then push it that many times.
and when copy the rest of the stack, just ignore it like how you're doing now.


Or you could make an special case for the first time that you encounter it, setting a `found' flag or similar, so you ignore only if the flag is not set.

> i have to sort two stacks with Selection Sort, but it's forbidden to use arrays.
¿may you use 3 (or more) stacks?
Topic archived. No new replies allowed.