Hi, I could be wrong about this but a number of years ago I came across a challenge of sorting an array in one pass by using a stack and a queue. Does anyone know the algorithm?
i.e. you get a value from the array then either push it on to the stack or enqueue in the queue until all the values are used then you pop or dequeue into an ordered array, at least that’s the gist of what I remember.
Has anyone come across this (if any of it makes sense) before?
There are a number of sorting algorithms, but I can’t think of one that would work with moving values directly from one stack/queue to another stack/queue. Are you maybe thinking of going from a stack/queue to a binary tree?
ETA: There is certainly no way of sorting an array in “one pass” ( aka “order n” or O(n)). The lowest complexity for a sorting algorithm is O(nlogn).
i don’t think so but it was such a long time ago, I could be wrong. As best as I can recall it was given a list of instructions and a starting array of random values. The values came out of the array some comparison was made resulting the value either going onto the stack or the queue the comparison may have also popped or dequeue the top of the stack or end of the queue, I’m not sure. the only parts I’m sure of is that it involved one stack and one queue and at the end of the pass it was all in order. I have not come across this since then, maybe it was a fevered dream?
You had a source array, a queue, and a stack? I haven’t done sorting that way, but I can see how it would be done. Sounds like a Towers of Hanoi sort of approach.
1 Like
Maybe, It’s not a connection I made at the time. It was an exercise in programing linked lists but at the time I was just following a sheet of instructions like a recipe for baking a cake, didn’t know the result was an ordered array until I ran the code it produced. I think the surprise result made it stay partially in my mind.