Bug dans la mise en œuvre de quicksort

Question

Je dois mettre en œuvre le quicksort. De Programming Pearls est le code ici:

public class Quick{ 
    public static void quicksort(int x[], int l, int u) 
    { 
     if (l>=u) 
      return; 
     int t = x[l]; 
     int i = l; 
     int j = u; 

     do 
     { 
      i++; 
     } while (i<=u && x[i]<t); 

     do 
     { 
      j--; 
      if (i>=j) break; 
     } while (x[j]>t); 

     swap(x, i, j); 
     swap(x, l, j); 

     quicksort(x, l , j-1); 
     quicksort(x, j+1, u ); 
    } 

    public static void main(String[]args) 
    { 
     int x[] = new int[]{55,41,59,26,53,58,97,93}; 
     quicksort(x, 0, x.length-1); 
     for (int i=0; i<x.length; i++) 
     { 
      System.out.println(x[i]); 
     } 
    } 

    public static void swap(int x[], int i, int j) 
    { 
     int s = x[i]; 
     x[i] = x[j]; 
     x[j] = s; 
    } 
} 

Il ne fonctionne pas. Voici la sortie:

59 
41 
55 
26 
53 
97 
58 
93 

Pourquoi cela ne fonctionne-t-il pas?

Answer 1

devrait être:

int t=x[l]; 
int i=l; 
-> int j=u + 1; 

En outre, vous avez traduit le pseudo code correctement: Ici, il est en C# (très similaire à C, il suffit de modifier les déclarations de tableau):

public static class Sort 
{ 
    public static void quicksort(int[] x, int l, int u) 
    { 
     if (l >= u) 
      return; 

     int t = x[l]; 
     int i = l; 
     int j = u + 1; 

     while (true) // In C, make this while(1) 
     { 
      do 
      { 
       i++; 
      } while (i <= u && x[i] < t); 

      do 
      { 
       j--; 
      } while (x[j] > t); 

      if (i >= j) 
       break; 

      swap(x, i, j); 
     } 

     swap(x, l, j); 

     quicksort(x, l, j - 1); 
     quicksort(x, j + 1, u); 
    } 


    public static void swap(int[] x, int i, int j) 
    { 
     int s = x[i]; 
     x[i] = x[j]; 
     x[j] = s; 
    } 

Calling avec ceci:

static void Main(string[] args) 
    { 
     int[] x = new int[] { 55, 41, 59, 26, 53, 58, 97, 93 }; 

     Sort.quicksort(x, 0, x.Length - 1); 
     for (int i = 0; i < x.Length; i++) 
     { 
      Console.WriteLine(x[i]); 
     } 
    } 

Produit:

26 
41 
53 
55 
58 
59 
93 
97 

Answer 2

Il semble que cela a été répondu.

Comme il est dans la balise algorithmes que je veux dire - je suis tombé sur this neat website qui montre le tri en cours.

Check it out, je suis sûr que vous apprécierez :)