Regard sur Tris - Quicksort itératif?

Question

Je regarde toutes sortes différentes. Notez que ce n'est pas un travail à faire (je suis en pleine finale). Je cherche juste à être préparé si ce genre de chose devait apparaître. J'ai été incapable de trouver une méthode fiable pour faire un quicksort itérativement. Est-ce possible et, si oui, comment?

Answer 1

#include <stdio.h> 
#include <conio.h> 

#define MAXELT   100 
#define INFINITY  32760   // numbers in list should not exceed 
             // this. change the value to suit your 
             // needs 
#define SMALLSIZE  10   // not less than 3 
#define STACKSIZE  100   // should be ceiling(lg(MAXSIZE)+1) 

int list[MAXELT+1];     // one extra, to hold INFINITY 

struct {        // stack element. 
     int a,b; 
} stack[STACKSIZE]; 

int top=-1;       // initialise stack 

int main()       // overhead! 
{ 
    int i=-1,j,n; 
    char t[10]; 
    void quicksort(int); 

    do { 
     if (i!=-1) 
      list[i++]=n; 
     else 
      i++; 
     printf("Enter the numbers <End by #>: "); 
     fflush(stdin); 
     scanf("%[^\n]",t); 
     if (sscanf(t,"%d",&n)<1) 
     break; 
    } while (1); 

    quicksort(i-1); 

    printf("\nThe list obtained is "); 
    for (j=0;j<i;j++) 
     printf("\n %d",list[j]); 

    printf("\n\nProgram over."); 
    getch(); 
    return 0;  // successful termination. 
} 

void interchange(int *x,int *y)  // swap 
{ 
    int temp; 

    temp=*x; 
    *x=*y; 
    *y=temp; 
} 

void split(int first,int last,int *splitpoint) 
{ 
    int x,i,j,s,g; 

    // here, atleast three elements are needed 
    if (list[first]<list[(first+last)/2]) { // find median 
     s=first; 
     g=(first+last)/2; 
    } 
    else { 
     g=first; 
     s=(first+last)/2; 
    } 
    if (list[last]<=list[s]) 
     x=s; 
    else if (list[last]<=list[g]) 
     x=last; 
    else 
     x=g; 
    interchange(&list[x],&list[first]);  // swap the split-point element 
              // with the first 
    x=list[first]; 
    i=first+1;        // initialise 
    j=last+1; 
    while (i<j) { 
     do {         // find j 
      j--; 
     } while (list[j]>x); 
     do { 
      i++;        // find i 
     } while (list[i]<x); 
     interchange(&list[i],&list[j]);  // swap 
    } 
    interchange(&list[i],&list[j]);   // undo the extra swap 
    interchange(&list[first],&list[j]);  // bring the split-point 
              // element to the first 
    *splitpoint=j; 
} 

void push(int a,int b)      // push 
{ 
    top++; 
    stack[top].a=a; 
    stack[top].b=b; 
} 

void pop(int *a,int *b)      // pop 
{ 
    *a=stack[top].a; 
    *b=stack[top].b; 
    top--; 
} 

void insertion_sort(int first,int last) 
{ 
    int i,j,c; 

    for (i=first;i<=last;i++) { 
     j=list[i]; 
     c=i; 
     while ((list[c-1]>j)&&(c>first)) { 
      list[c]=list[c-1]; 
      c--; 
     } 
     list[c]=j; 
    } 
} 

void quicksort(int n) 
{ 
    int first,last,splitpoint; 

    push(0,n); 
    while (top!=-1) { 
     pop(&first,&last); 
     for (;;) { 
      if (last-first>SMALLSIZE) { 
       // find the larger sub-list 
       split(first,last,&splitpoint); 
       // push the smaller list 
       if (last-splitpoint<splitpoint-first) { 
        push(first,splitpoint-1); 
        first=splitpoint+1; 
       } 
       else { 
        push(splitpoint+1,last); 
        last=splitpoint-1; 
       } 
      } 
      else { // sort the smaller sub-lists 
        // through insertion sort 
       insertion_sort(first,last); 
       break; 
      } 
     } 
    }      // iterate for larger list 
} 

// End of code. 

pris de here

Answer 2

I was unable to find a reliable method of doing a quicksort iteratively 

Avez-vous essayé google?

Il est juste commun rapide, lorsque la récursivité est réalisée avec tableau.

Answer 3

Ceci est mon effort. Dites-moi s'il y a une amélioration possible.

Ce code est fait à partir du livre "Structures de données, Seymour Lipschutz (Page-173), Mc GrawHill, Série Outline de Schaum."

#include <stdio.h> 
#include <conio.h> 
#include <math.h> 

#define SIZE 12 

struct StackItem 
{ 
    int StartIndex; 
    int EndIndex; 
}; 
struct StackItem myStack[SIZE * SIZE]; 
int stackPointer = 0; 

int myArray[SIZE] = {44,33,11,55,77,90,40,60,99,22,88,66}; 

void Push(struct StackItem item) 
{ 
    myStack[stackPointer] = item; 
    stackPointer++; 
} 

struct StackItem Pop() 
{ 
    stackPointer--; 
    return myStack[stackPointer]; 
} 

int StackHasItem() 
{ 
    if(stackPointer>0) 
    { 
     return 1; 
    } 
    else 
    { 
     return 0; 
    } 
} 

void ShowStack() 
{ 
    int i =0; 

    printf("\n"); 

    for(i=0; i<stackPointer ; i++) 
    { 
     printf("(%d, %d), ", myStack[i].StartIndex, myStack[i].EndIndex); 
    } 

    printf("\n"); 
} 

void ShowArray() 
{ 
    int i=0; 

    printf("\n"); 

    for(i=0 ; i<SIZE ; i++) 
    { 
     printf("%d, ", myArray[i]); 
    } 

    printf("\n"); 
} 

void Swap(int * a, int *b) 
{ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 

int Scan(int *startIndex, int *endIndex) 
{ 
    int partition = 0; 
    int i = 0; 

    if(*startIndex > *endIndex) 
    { 
     for(i=*startIndex ; i>=*endIndex ; i--) 
     { 
      //printf("%d->", myArray[i]); 
      if(myArray[i]<myArray[*endIndex]) 
      { 
       //printf("\nSwapping %d, %d", myArray[i], myArray[*endIndex]); 
       Swap(&myArray[i], &myArray[*endIndex]); 
       *startIndex = *endIndex; 
       *endIndex = i; 
       partition = i; 
       break; 
      } 
      if(i==*endIndex) 
      { 
       *startIndex = *endIndex; 
       *endIndex = i; 
       partition = i; 
      } 
     } 
    } 
    else if(*startIndex < *endIndex) 
    { 
     for(i=*startIndex ; i<=*endIndex ; i++) 
     { 
      //printf("%d->", myArray[i]); 
      if(myArray[i]>myArray[*endIndex]) 
      { 
       //printf("\nSwapping %d, %d", myArray[i], myArray[*endIndex]); 
       Swap(&myArray[i], &myArray[*endIndex]); 
       *startIndex = *endIndex; 
       *endIndex = i; 
       partition = i; 
       break; 
      } 
      if(i==*endIndex) 
      { 
       *startIndex = *endIndex; 
       *endIndex = i; 
       partition = i; 
      } 
     } 
    } 

    return partition; 
} 

int GetFinalPosition(struct StackItem item1) 
{ 
    struct StackItem item = {0}; 
    int StartIndex = item1.StartIndex ; 
    int EndIndex = item1.EndIndex; 
    int PivotIndex = -99; 

    while(StartIndex != EndIndex) 
    { 
     PivotIndex = Scan(&EndIndex, &StartIndex); 

     printf("\n"); 
    } 

    return PivotIndex; 
} 

void QuickSort() 
{ 
    int median = 0; 
    struct StackItem item; 
    struct StackItem item1={0}; 
    struct StackItem item2={0}; 

    item.StartIndex = 0; 
    item.EndIndex = SIZE-1; 

    Push(item); 

    while(StackHasItem()) 
    { 
     item = Pop(); 

     median = GetFinalPosition(item); 

     if(median>=0 && median<=(SIZE-1)) 
     { 
      if(item.StartIndex<=(median-1)) 
      { 
       item1.StartIndex = item.StartIndex; 
       item1.EndIndex = median-1; 
       Push(item1); 
      }  
      if(median+1<=(item.EndIndex)) 
      { 
       item2.StartIndex = median+1; 
       item2.EndIndex = item.EndIndex; 
       Push(item2); 
      } 
     } 

     ShowStack(); 
    } 
} 

main() 
{ 
    ShowArray(); 
    QuickSort(); 
    ShowArray(); 
} 

Answer 4

Je vais essayer de donner une réponse plus générale en plus des implémentations réelles données dans les autres publications.

Est-ce possible et, si oui, comment?

Laissez-nous tout d'abord un coup d'oeil à ce qui peut être signifié en faisant un algorithme récursif itérative.

Par exemple, nous voulons avoir une fonction sum(n) qui résume les nombres de 0 à n.

Certes, cela est

sum(n) = 
    if n = 0 
    then return 0 
    else return n + sum(n - 1) 

Comme nous essayons de calculer quelque chose comme sum(100000), nous allons bientôt voir cet algorithme récursif a ses limites - un débordement de pile se produira. Donc, en tant que solution, nous utilisons un algorithme itératif pour résoudre le même problème.

sum(n) = 
    s <- 0 
    for i in 0..n do 
    s <- s + i 
    return s 

Cependant, il est important de noter que cette implémentation est un algorithme entièrement différent de la somme récursive ci-dessus. Nous n'avons pas modifié l'original pour obtenir la version itérative, nous avons simplement trouvé un algorithme non récursif - avec des caractéristiques de performances différentes et sans doute meilleures - qui résout le même problème.

Ceci est le premier aspect de faire un algorithme itératif: Trouver un autre algorithme itératif qui résout le même problème.

Dans certains cas, il pourrait ne pas y avoir une telle version itérative.

Le deuxième est cependant applicable à chaque algorithme récursif. Vous pouvez transformer n'importe quelle récursion en itération par explicitement en introduisant la pile que la récursion utilise implicitement.Maintenant, cet algorithme aura exactement les mêmes caractéristiques que l'original - et la pile va croître avec O(n) comme dans la version récursive. Il ne débordera pas facilement car il utilise la mémoire conventionnelle au lieu de la pile d'appels, et son itératif, mais c'est toujours le même algorithme. Comme pour le tri rapide: Il n'y a pas de formulation différente qui fonctionne sans stocker les données nécessaires à la récursivité. Mais bien sûr, vous pouvez utiliser une pile explicite pour eux, comme l'a montré Ehsan. Ainsi vous pouvez - comme toujours - produire une version itérative.