current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.
up vote 1 down vote favorite

I am trying to implement a recursively defined Stack and sort it in Java. I don't have a particular usage of this program in mind. I found this approach of stack implementation a bit useful while implementing persistent stack. I know Stacks are not made for sorting but one can consider using two stacks to implement a job scheduling queue which needs to be sorted for which stacks used for queue implementation must be sorted based on some resource parameters.

Is there any efficient method apart from copying the elements from Stack in array, sorting them and again pushing them on stack? (I know C/C++, Java)

//Stack definition:
Stack
{
    E element;
    Stack topOfSubStack;
}
share|improve this question
1  
Hello, it appears you are new to our site - please check out the purpose of this site. It appears you are asking a homework question, which is off-topic, so I have downvoted your question. –  J Trana Sep 12 '14 at 6:23
    
Its not a homework question I was just trying to implement a recursively defined Stack? question is purely out of curiosity. –  geek Sep 12 '14 at 6:30
2  
I'm a newbie. I'll improve :) –  geek Sep 12 '14 at 6:57
3  
What's the overall goal? Do you have a particular usage in mind? Typically, stacks aren't sortable, because you only care about what's on top of the stack. If you care about data order and performance, a balanced tree with stack operations (push/pop and shift/unshift) might be a more appropriate option. –  outis Sep 12 '14 at 8:51
1  
@geek Then, the only way I see to empty the stack to an efficiently sortable data structure, sort and then to push the sorted data back on the stack. Stacks are not made for sorting. –  Peter G. Sep 12 '14 at 9:26

1 Answer 1

up vote 1 down vote

You can use a derived mergesort

you can grab chunks of the stack and sort them separately (standard divide and conquer)

then you can simply merge as follows:

struct node{
int element;
node* next;
}

node* merge(node* begin1, node* end1, node* begin2, node* end2){

    node* head;
    node* tail;
    if(begin1==end1)return begin2;
    if(begin2==end2)return begin1;

    if(begin1->element < begin2->element){
       head = tail = begin1;
       begin1=begin1->next;
    }else{
       head = tail = begin1;
       begin2=begin2->next;
    }
    while(begin1!=end1 && begin2!=end2){

        if(begin1->element < begin2->element){
           tail->next = begin1;
           tail=tail.next;
           begin1=begin1->next;
        }else{
           tail->next = begin2;
           tail=tail.next;
           begin2=begin2->next;
        }

    }
    if(begin1==end1)tail->next=begin2;
    if(begin2==end2)tail->next=begin1;
    return head;
}

You can split the array by starting at an increment of 1 and then grabbing chunks that large merging them 2 by 2, concatenating them and doubling the chunkLength each time.

share|improve this answer
    
Can you provide the time and space complexity of your code? –  geek Sep 12 '14 at 11:04
    
@geek O(n log n) time and O(1) space (as good as you can get with a comparison sort) –  ratchet freak Sep 12 '14 at 11:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.