0

Which sorting algorithms would be good to sort a Stack for space efficiency? I need to sort a stack 'in place.' Also my understanding of 'in place' algorithms was that they don't use any additional data structures - is this correct?

I know this is similar to this question but I'm wondering if it would be different for stacks? I know stacks can just be a type of linkedlist, but does the fact that you can only access the top change how you would do it?

Community
  • 1
  • 1
user146303
  • 437
  • 1
  • 7
  • 20
  • Do none of [these results](https://www.google.com/search#q=sort+stack+in+place) answer your question? – dimo414 Jul 16 '16 at 18:27
  • If you're restricted to use functions of stack, like push and pop, you will certainly need some space to sort it. But if you're allowed to touch the stack implementation we can do that space efficiently. (If the stack is made using a linked list, we can use the functions of linked list to sort) – pahan Jul 16 '16 at 19:40
  • By the way, when you sort a stack in place, it will no longer be a stack. Therefore if you're in a situation with a need to sort a stack, you sure will need another data structure to store the sorted values in order to preserve the stack. – pahan Jul 16 '16 at 19:46

2 Answers2

1

You will have to omit the "in-place" qualifier if your intent is to sort the stack using only stack operations (you will have to have another stack). An in-place algorithm is an algorithm which transforms its input using no other data structures. However, a small amount of extra storage space is allowed for intermediary/temporary variables.

If you omit the "in-place" qualifier you can find your answer here: How to sort a stack using only stack operations? (sorts a stack using an additional helper stack)

If you retain the qualifier then sorting the stack is only possible on the implementation level, and not by using stack operations.

Community
  • 1
  • 1
Filip Allberg
  • 3,941
  • 3
  • 20
  • 37
0

There's an alternate definition for in-place sort that just means the sorted data ends back up in the same container (in this case a stack) that the unsorted data was originally stored in.

Getting back to the original question, the only way to access and/or change the last element of a stack is to pop off all the other elements, which requires O(n-1) space elsewhere, the simplest being an array.

If the stack is implemented as a linked list, then a linked list type sort could be used, but this would be list oriented sort, using operations other than the standard stack operations peek, pop, and push.

rcgldr
  • 27,407
  • 3
  • 36
  • 61