Ich habe diese Frage im Internet gefunden.
Schreiben Sie bei gegebenem Stack S ein C-Programm, um den Stack (in aufsteigender Reihenfolge) zu sortieren. Wir dürfen keine Annahmen darüber treffen, wie der Stack implementiert ist. Die einzigen zu verwendenden Funktionen sind:
Push
Pop
Top
IsEmpty
IsFull
Ich denke, wir können Haufen bauen und sortieren. Was ist die optimale Lösung dafür?
Angenommen, die einzige hier erlaubte Datenstruktur ist der Stack, dann könnten Sie 2 Stacks verwenden.
Iterieren Sie, bis der ursprüngliche Stapel leer ist, und entfernen Sie bei jeder Iteration ein Element aus dem ursprünglichen Stapel, während das oberste Element im zweiten Stapel größer als das entfernte Element ist, entfernen Sie den zweiten Stapel und schieben Sie es auf den ursprünglichen Stapel. Jetzt können Sie das Element, das Sie ursprünglich vom ursprünglichen Stapel entfernt haben, auf den zweiten Stapel verschieben.
Die zeitliche Komplexität dieses Ansatzes beträgt O(N^2).
C-Code zur Implementierung dieses Algorithmus wäre (entschuldigen Sie meine eingerosteten C-Kenntnisse):
void SortStack(struct Stack * orig_stack)
{
struct Stack helper_stack;
while (!IsEmpty(orig_stack))
{
int element = Pop(orig_stack);
while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
{
Push(orig_stack, Pop(&helper_stack));
}
Push(&helper_stack, element);
}
while (!IsEmpty(&helper_stack))
{
Push(orig_stack, Pop(&helper_stack));
}
}
Angesichts dieser Stapeloperationen könnten Sie eine rekursive Einfügesortierung schreiben.
void sort(stack s) {
if (!IsEmpty(s)) {
int x = Pop(s);
sort(s);
insert(s, x);
}
}
void insert(stack s, int x) {
if (!IsEmpty(s)) {
int y = Top(s);
if (x < y) {
Pop(s);
insert(s, x);
Push(s, y);
} else {
Push(s, x);
}
} else {
Push(s, x);
}
}
Dies kann rekursiv mit demselben Stack erfolgen. O(n^2) Ich habe es in C++ codiert, aber die Konvertierung nach C ist trivial. Ich mag einfach Vorlagen und Sie haben Ihre Frage als C++ markiert
template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
if(element > stack.Top())
{
T top = stack.Pop();
Insert(element, stack);
stack.Push(top);
}
else
{
stack.Push(element);
}
}
template<typename T>
void StackSort(Stack<T>& stack)
{
if(!stack.IsEmpty())
{
T top = stack.Pop();
StackSort(stack);
Insert(top, stack);
}
}
Geänderter Code aus der Antwort von T33C
(vorgegeben, bevor Svante das Sprach-Tag von c++ auf c korrigierte):
stack.top()
kann nur geprüft werden, ob !stack.empty()
void insert(int element, stack<int> &stack) {
if (!stack.empty() && element > stack.top()) {
int top = stack.top();
stack.pop();
insert(element, stack);
stack.push(top);
}
else {
stack.push(element);
}
}
void sortStack(stack<int> & stack) {
if (!stack.empty()) {
int top = stack.top();
stack.pop();
sortStack(stack);
insert(top, stack);
}
}
3-Stack-Sortierung unter Verwendung von Polyphase-Merge-Sortierung
Dies sollte der schnellste Weg sein, eine 3-Stapel-Sortierung zu implementieren. Die Zeitkomplexität ist O(n log(n)). Das Ziel ist es, eine aufsteigende Sequenz zu erhalten, wenn Elemente aus einem sortierten Stapel entnommen werden. Der Ursprung für diese Methode war die Verwendung von Polyphase Merge Sort auf alten Mainframe-Bandlaufwerken, die rückwärts lesen konnten (um Rückspulzeit zu vermeiden), ähnlich wie beim Stapeln, da während des Sortierens vorwärts geschrieben und rückwärts gelesen wurde.
Wiki-Artikel für Polyphase Merge Sort (mithilfe von Arrays):
http://en.wikipedia.org/wiki/Polyphase_merge_sort
Beispiel-C++-Code für eine mehrphasige Sortierung mit 3 Stapeln unter Verwendung von Zeigern, einem Zeiger als Stapelzeiger für jeden Stapel und einem Zeiger auf das Ende jedes Laufs und das Ende jedes Stapels. Der Laufgrößenzeiger wird verwendet, um zu verfolgen, wann die Laufgröße in der Mitte des Stapels inkrementiert oder dekrementiert wird. Ein Flag für absteigende Sequenzen wird verwendet, um zu verfolgen, ob Sequenzen absteigend oder aufsteigend sind, wenn Daten zwischen Stapeln übertragen werden. Es wird am Anfang initialisiert und wechselt dann, nachdem jedes Paar von Läufen zusammengeführt wurde.
typedef unsigned int uint32_t;
static size_t fibtbl[48] =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903,2971215073};
// binary search: return index of largest fib() <= n
size_t flfib(size_t n)
{
size_t lo = 0;
size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]);
while((hi - lo) > 1){
size_t i = (lo + hi)/2;
if(n < fibtbl[i]){
hi = i;
continue;
}
if(n > fibtbl[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort array using 3 arrays as stacks, a is source
uint32_t * ppmrg3s(uint32_t a[], uint32_t b[], uint32_t c[], size_t n)
{
if(n < 2)
return a;
uint32_t *asp = a; // a stack ptr
uint32_t *aer; // a end run
uint32_t *aes = a + n; // a end
uint32_t *bsp = b + n; // b stack ptr
uint32_t *ber; // b end run
uint32_t *bes = b + n; // b end
uint32_t *csp = c + n; // c stack ptr
uint32_t *ces = c + n; // c end
uint32_t *rsp = 0; // run size change stack ptr
size_t ars = 1; // run sizes
size_t brs = 1;
size_t scv = 0-1; // size change increment / decrement
bool dsf; // == 1 if descending sequence
{ // block for local variable scope
size_t f = flfib(n); // fibtbl[f+1] > n >= fibtbl[f]
dsf = ((f%3) == 0); // init compare flag
if(fibtbl[f] == n){ // if exact fibonacci size, move to b
for(size_t i = 0; i < fibtbl[f-1]; i++)
*(--bsp) = *(asp++);
} else { // else move to b, c
// update compare flag
dsf ^= (n - fibtbl[f]) & 1;
// move excess elements to b
aer = a + n - fibtbl[f];
while (asp < aer)
*(--bsp) = *(asp++);
// move dummy count elements to c
aer = a + fibtbl[f - 1];
while (asp < aer)
*(--csp) = *(asp++);
rsp = csp; // set run size change ptr
}
} // end local variable block
while(1){ // setup to merge pair of runs
if(asp == rsp){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
rsp = csp;
}
if(bsp == rsp){
brs += scv;
scv = 0-scv;
rsp = csp;
}
aer = asp + ars; // init end run ptrs
ber = bsp + brs;
while(1){ // merging pair of runs
if(dsf ^ (*asp <= *bsp)){ // if a <= b
*(--csp) = *(asp++); // move a to c
if(asp != aer) // if not end a run
continue; // continue back to compare
do // else move rest of b run to c
*(--csp) = *(bsp++);
while (bsp < ber);
break; // and break
} else { // else a > b
*(--csp) = *(bsp++); // move b to c
if(bsp != ber) // if not end b run
continue; // continue back to compare
do // else move rest of a run to c
*(--csp) = *(asp++);
while (asp < aer);
break; // and break
}
} // end merging pair of runs
dsf ^= 1; // toggle compare flag
if(bsp == bes){ // if b empty
if(asp == aes) // if a empty, done
break;
std::swap(bsp, csp); // swap b, c
std::swap(bes, ces);
brs += ars; // update run size
} else { // else b not empty
if(asp != aes) // if a not empty
continue; // continue back to setup next merge
std::swap(asp, csp); // swap a, c
std::swap(aes, ces);
ars += brs; // update run size
}
}
return csp; // return ptr to sorted array
}
Java-Beispielcode zum Sortieren mithilfe einer benutzerdefinierten Stack-Klasse (xstack), die eine Swap-Funktion enthält.
static final int[] FIBTBL =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903};
// return index of largest fib() <= n
static int flfib(int n)
{
int lo = 0;
int hi = 47;
while((hi - lo) > 1){
int i = (lo + hi)/2;
if(n < FIBTBL[i]){
hi = i;
continue;
}
if(n > FIBTBL[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort using 3 stacks
static void ppmrg3s(xstack a, xstack b, xstack c)
{
if(a.size() < 2)
return;
int ars = 1; // init run sizes
int brs = 1;
int asc = 0; // no size change
int bsc = 0;
int csc = 0;
int scv = 0-1; // size change value
boolean dsf; // == 1 if descending sequence
{ // block for local variable scope
int f = flfib(a.size()); // FIBTBL[f+1] > size >= FIBTBL[f]
dsf = ((f%3) == 0); // init compare flag
if(FIBTBL[f] == a.size()){ // if exact fibonacci size,
for (int i = 0; i < FIBTBL[f - 1]; i++) { // move to b
b.push(a.pop());
}
} else { // else move to b, c
// update compare flag
dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1);
// i = excess run count
int i = a.size() - FIBTBL[f];
// j = dummy run count
int j = FIBTBL[f + 1] - a.size();
// move excess elements to b
do{
b.push(a.pop());
}while(0 != --i);
// move dummy count elements to c
do{
c.push(a.pop());
}while(0 != --j);
csc = c.size();
}
} // end block
while(true){ // setup to merge pair of runs
if(asc == a.size()){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
asc = 0;
csc = c.size();
}
if(bsc == b.size()){
brs += scv;
scv = 0-scv;
bsc = 0;
csc = c.size();
}
int arc = ars; // init run counters
int brc = brs;
while(true){ // merging pair of runs
if(dsf ^ (a.peek() <= b.peek())){
c.push(a.pop()); // move a to c
if(--arc != 0) // if not end a
continue; // continue back to compare
do{ // else move rest of b run to c
c.push(b.pop());
}while(0 != --brc);
break; // and break
} else {
c.push(b.pop()); // move b to c
if(0 != --brc) // if not end b
continue; // continue back to compare
do{ // else move rest of a run to c
c.push(a.pop());
}while(0 != --arc);
break; // and break
}
} // end merging pair of runs
dsf ^= true; // toggle compare flag
if(b.empty()){ // if end b
if(a.empty()) // if end a, done
break;
b.swap(c); // swap b, c
brs += ars;
if (0 == asc)
bsc = csc;
} else { // else not end b
if(!a.empty()) // if not end a
continue; // continue back to setup next merge
a.swap(c); // swap a, c
ars += brs;
if (0 == bsc)
asc = csc;
}
}
a.swap(c); // return sorted stack in a
}
Die benutzerdefinierte Java-Stack-Klasse:
class xstack{
int []ar; // array
int sz; // size
int sp; // stack pointer
public xstack(int sz){ // constructor with size
this.ar = new int[sz];
this.sz = sz;
this.sp = sz;
}
public void push(int d){
this.ar[--sp] = d;
}
public int pop(){
return this.ar[sp++];
}
public int peek(){
return this.ar[sp];
}
public boolean empty(){
return sp == sz;
}
public int size(){
return sz-sp;
}
public void swap(xstack othr){
int []tempar = othr.ar;
int tempsz = othr.sz;
int tempsp = othr.sp;
othr.ar = this.ar;
othr.sz = this.sz;
othr.sp = this.sp;
this.ar = tempar;
this.sz = tempsz;
this.sp = tempsp;
}
}
Geben Sie bitte einen Link an. Wie bereits erwähnt, könnten Sie einfach in eine beliebige andere Struktur kopieren, diese sortieren und wieder hineinkopieren. O(1) Zusätzliche Speichernutzung ist die kritische Anforderung.
– Kartoffelklatsche
28. Januar 2011 um 8:43 Uhr
O(1) zusätzlicher Speicher ist nachweislich unmöglich. Wenn die unteren beiden Elemente des Stapels ausgetauscht werden müssen, müssen alle darüber liegenden Elemente in einen zusätzlichen Speicher verschoben werden. Das ist O(N).
– MSalter
28. Januar 2011 um 8:46 Uhr
Warum zum Teufel willst du einen Stapel sortieren?
– lepi
28. Januar 2011 um 8:48 Uhr
@MSalters: Ja. Ich denke, die einzig guten Antworten auf diese Frage sind “kann nicht” und “duh”.
– Kartoffelklatsche
28. Januar 2011 um 8:49 Uhr
Für mich klingt es nach dem Problem “Der Turm von Hanoi”: en.wikipedia.org/wiki/Towers_of_Hanoi. Die Aufgabe ist etwas anders, aber ich denke, man könnte damit anfangen.
– Benutzer346034
28. Januar 2011 um 9:25 Uhr