Programma algoritmo Quicksort in Java

Question

Sto cercando di implementare il programma algoritmo QuickSort in Java, ma sto ricevendo risposta errata.

public class QuickSort { 

    public static void main(String[] args){ 
     int arr[]={12,34,22,64,34,33,23,64,33}; 
     int i=0; 
     int j=arr.length; 
     while(i<j){ 
      i=quickSort(arr,i,i+1,j-1); 

     } 
     for(i=0;i<arr.length;i++) 
      System.out.print(arr[i]+" "); 
    } 

    public static int quickSort(int arr[],int pivot,int i,int j){ 

     if(i>j) {   
      swap(arr,pivot,j); 
      return i; 
     } 

     while(i<arr.length&&arr[i]<=arr[pivot]) { 
      i++; 
     } 

     while(j>=1&&arr[j]>=arr[pivot]) {   
      j--; 
     } 
     if(i<j) 
      swap(arr,i,j); 

     return quickSort(arr,pivot,i,j); 

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

} 

Il programma sopra di me dando l'uscita come: 12 23 22 33 34 33 64 34 64

Qualcuno potrebbe dirmi come posso ottenere il mio risultato desiderio?

Answer 1

Il problema è che questo non è esattamente come funziona quicksort. Quicksort è un algoritmo ricorsivo che dovrebbe essere chiamato una sola volta da fuori di sé. L'idea è che a ogni iterazione, si partiziona l'array in due parti: la metà sinistra contiene tutti gli elementi inferiori al pivot e la metà destra contiene tutti gli elementi più grandi o uguali al pivot. Quindi fai un quicksort delle due metà e infine metti il ​​perno nel mezzo.

Se il lato di cui si esegue il quicksorting è lungo meno di 3 elementi, è possibile scambiare i due elementi o lasciarli e quella parte dell'array è completata.

Ma non sembra che il tuo codice lo stia facendo - chiami Quicksort 6 volte dal tuo client, e all'interno della funzione quicksort che stai facendo al massimo uno scambio. Quindi questo non è il caso in cui qualcuno sarà in grado di guardare il tuo codice e fare il debug dicendoti di spostare uno swap o qualcosa del genere. Hai bisogno di rivisitare la tua logica.

Partenza il diagramma di Wikipedia per un esempio visivo di quello che dovrebbe accadere in una singola iterazione:

http://en.wikipedia.org/wiki/File:Partition_example.svg

Answer 2

ci sono implementazioni open source di quicksort in Apache Harmony e Apache Mahout, probabilmente tra molti altri. Puoi leggerli.

Answer 3

Si prega di trovare il codice di lavoro completo per l'algoritmo di ordinamento rapido implementata in Java qui,

http://tech.bragboy.com/2010/01/quick-sort-in-java.html

Answer 4

Il tuo ciclo non funziona correttamente. Consultare il codice che è risolvere il problema circa Quick Sort

static void quickSort (int[] numbers, int low, int high) 
{ 
    int i=low; 
    int j=high; 
    int temp; 
    int middle=numbers[(low+high)/2]; 

    while (i<j) { 

     while (numbers[i]<middle) { 
      i++; 
     } 

     while (numbers[j]>middle) { 
      j--; 
     } 

     if (i<=j) { 
      temp=numbers[i]; 
      numbers[i]=numbers[j]; 
      numbers[j]=temp; 
      i++; 
      j--; 
     } 
    } 

    if (low<j) { 
     quickSort(numbers, low, j); 
    } 

    if (i<high) { 
     quickSort(numbers, i, high); 
    } 
} 

consultare Quick sort.

Answer 5

public static int partition(int[] a, int p, int r){ 

     int i=p,j=r,pivot=a[r]; 

     while(i<j){ 

      while(i<r && a[i] <= pivot){ 
       i++; 
      } 

      while(j>p && a[j]>pivot){ 
       j--; 
      } 

      if(i<j){ 
       swap(a, i, j); 
      }   
     } 
     return j; 
    } 

    public static void quickSort(int[] a, int p, int r){ 
     if(p<r){ 
      int q=partition(a, p, r); 

      if(p==q){ 
       quickSort(a, p+1, r); 
      }else if(q==r){ 
       quickSort(a, p, r-1); 
      }else { 
       quickSort(a, p, q); 
       quickSort(a, q+1, r); 
      } 

     } 
    } 

    public static void swap(int[] a, int p1, int p2){ 
     int temp=a[p1]; 
     a[p1]=a[p2]; 
     a[p2]=temp; 
    } 

Answer 6

ecco un algoritmo di quicksort

package drawFramePackage; 
    import java.awt.geom.AffineTransform; 
    import java.util.ArrayList; 
    import java.util.ListIterator; 
    import java.util.Random; 
    public class QuicksortAlgorithm { 
     ArrayList<AffineTransform> affs; 
     ListIterator<AffineTransform> li; 
     Integer count, count2; 
     /** 
     * @param args 
     */ 
     public static void main(String[] args) { 
      new QuicksortAlgorithm(); 
     } 
     public QuicksortAlgorithm(){ 
      count = new Integer(0); 
      count2 = new Integer(1); 
      affs = new ArrayList<AffineTransform>(); 
      for (int i = 0; i <= 128; i++){ 
       affs.add(new AffineTransform(1, 0, 0, 1, new Random().nextInt(1024), 0)); 
      } 
      affs = arrangeNumbers(affs); 
      printNumbers(); 
     } 
     public ArrayList<AffineTransform> arrangeNumbers(ArrayList<AffineTransform> list){ 
      while (list.size() > 1 && count != list.size() - 1){ 
       if (list.get(count2).getTranslateX() > list.get(count).getTranslateX()){ 
        list.add(count, list.get(count2)); 
        list.remove(count2 + 1); 
       } 
       if (count2 == list.size() - 1){ 
        count++; 
        count2 = count + 1; 
       } 
       else{ 
       count2++; 
       } 
      } 
      return list; 
     } 
     public void printNumbers(){ 
      li = affs.listIterator(); 
      while (li.hasNext()){ 
       System.out.println(li.next()); 
      } 
     } 
    } 

disponibile anche con la descrizione in nathan's computer knowledge con una descrizione [code ] [/ code] ``