Come ordinare in maniera efficiente uno Stack definito ricorsivamente?

Question

Come ordinare in maniera efficiente uno Stack definito ricorsivamente?

#1 da (1 voti)

2

Sto cercando di implementare uno Stack definito ricorsivamente e ordinarlo in Java. Non ho un particolare utilizzo di questo programma in mente. Ho trovato questo approccio di implementazione dello stack un po 'utile durante l'implementazione dello stack persistente. So che gli stack non sono fatti per l'ordinamento, ma si può considerare l'utilizzo di due stack per implementare una coda di pianificazione del lavoro che deve essere ordinata per quale stack utilizzato per l'implementazione della coda deve essere ordinato in base ad alcuni parametri di risorse.

Esiste un metodo efficiente oltre a copiare gli elementi da Stack in array, ordinandoli e spingendoli di nuovo sullo stack? (Conosco C / C ++, Java)

//Stack definition:
Stack
{
    E element;
    Stack topOfSubStack;
}

recursion data-structures sorting stack

posta geek 12.09.2014 - 08:17

fonte

1 risposta

Leggi altre domande sui tag recursion data-structures sorting stack

È possibile mantenere il lavoro al minimo a fini di distribuzione? Algoritmo ML foresta casuale adatto per l'HPC basato su cluster?

score 1 · Answer 1

Puoi usare un mergesort derivato

puoi afferrare blocchi della pila e ordinarli separatamente (divisione e conquista standard)

quindi puoi semplicemente unire come segue:

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;
}

Puoi dividere l'array iniziando con un incremento di 1 e poi afferrando i pezzi che li uniscono in grandi dimensioni 2 per 2, concatenandoli e raddoppiando il chunkLength ogni volta.