Algorithme de partition QuickSort

Question

J'essaie de programmer l'algorithme quicksort de Cormen Algorithm Textbook. Voici mon code.

class Quicksort 
{ 
    public void qSort(int[] a, int p, int r) 
    { 
     if(p<r) 
     { 
      int q = Partition(a, p,r); 
      qSort(a, p, q-1); 
      qSort(a, q+1, r); 
     } 
    } 

    private int Partition(int[] a, int p, int r) 
    { 
     int x = a[r]; 

     int i = p-1; 
     int temp=0; 

     for(int j=p; j<r-1; j++) 
     { 
      if(a[j]<=x) 
      { 
       i++; 
       temp = a[i]; 
       a[i] = a[j]; 
       a[j] = temp; 
      } 
     } 

     temp = a[i+1]; 
     a[i+1] = a[r]; 
     a[r] = temp; 
     return (i+1); 
    } 
} 

public class QuickSortTest 
{ 
    public static void main(String[] args) 
    { 
     Quicksort qsort = new Quicksort(); 
     int[] array = {5, 4, 7, 2, 1, 9, 3, 6, 10, 8}; 

     System.out.print("Original Array : "); 
     for(int i=0; i<array.length;i++) 
     { 
      System.out.print(array[i] + " "); 
     } 

     int length = array.length; 

     qsort.qSort(array, 0, length-1); 

     System.out.print("Sorted Array : "); 
     for(int i=0; i<array.length;i++) 
     { 
      System.out.print(array[i] + " "); 
     } 
    } 
} 

Mais, je reçois une mauvaise sortie lorsque j'exécute ce code.

Original Array : 5 4 7 2 1 9 3 6 10 8 
Sorted Array : 1 4 5 2 6 7 3 8 9 10 

Quelqu'un peut-il s'il vous plaît expliquer ce qui ne va pas. J'ai implémenté ce code exactement comme indiqué dans le livre "Introduction aux algorithmes". Je vous remercie.

Answer 1

Non, vous n'avez pas copié directement :) Je l'ai ici ...

for(int j=p; j<r-1; j++) 

devrait être

for(int j=p; j<r; j++) 

ou

for(int j=p; j <= r-1; j++) 

Le livre écrit:

for j = p to r - 1 

qui inclut r - 1. Et souvenez-vous que le livre a des tableaux qui partent de 1 et non de 0. Donc généralement les algorithmes du livre devraient être "copiés" avec beaucoup de soin ou avec des tableaux qui vont de 1.

Éditer: Informations sur l'algorithme pour un commentaire L'algorithme du livre prend le dernier élément comme pivot. Cela en fera donc un algorithme terrible pour les tableaux déjà triés. Il finira dans O (n^2), donc personne ne devrait utiliser cet algorithme en production (sauf si vous savez ce que vous faites et ce que vous faites) car les tableaux ont tendance à être quelque peu triés. L'algorithme de compilation de Java est plus intelligent et vous pouvez lire à ce sujet dans le Javadoc

Answer 2

Si vous voulez des références sur la façon d'implémenter le tri rapide, vous pouvez essayer de vérifier le code source réel de Arrays.sort (*) dans jdk, qui est une version modifiée du tri rapide. (http://www.oracle.com/technetwork/java/javase/downloads/index.html pour télécharger si vous n'avez pas déjà src.zip dans votre installation jdk).

Answer 3

Fournir une implémentation supplémentaire dans Java. Il est également basé sur le même algorithme et prend également en charge les éléments dupliqués dans le tableau.

public void sort(int[] inputArray, int lo, int high){ 
      int pivotIndex = partition(inputArray,lo,high); 
     System. out .println("Got PivotIndex as " + pivotIndex); 
      if (lo < pivotIndex -1) 
       sort(inputArray,lo,pivotIndex - 1); 
      if (pivotIndex+1 < high) 
       sort(inputArray,pivotIndex+1,high); 
      return ; 
    } 

    private int partition(int[] inputArray, int leftPtr,int rightPtr) 
    { 
     printArray(inputArray); 
      int pivot = inputArray[leftPtr]; 
      while (leftPtr<rightPtr){ 
       while (inputArray[leftPtr]<pivot) 
         leftPtr++; 
       while (inputArray[rightPtr]>pivot) 
         rightPtr--; 
       if (leftPtr<rightPtr) 
       { 
         exchange(inputArray,leftPtr,rightPtr); 

          //Cases which have repeated numbers... 
         if (inputArray[leftPtr] == inputArray[rightPtr]) 
          leftPtr++; 
       } 
     } 
      return leftPtr;//return any one 
    }