Programa de algoritmo Quicksort en Java

Question

Estoy tratando de implementar el programa de algoritmo QuickSort en Java, pero recibo una respuesta incorrecta.

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; 
    } 

} 

El programa anterior produce el resultado como: 12 23 22 33 34 33 64 34 64

Podría alguien por favor dígame cómo puedo obtener mi resultado el deseo?

Answer 1

El problema es que esta no es realmente la forma en que funciona el quicksort. Quicksort es un algoritmo recursivo que solo debe invocarse una vez desde fuera de sí mismo. La idea es que en cada iteración, usted particione la matriz en dos mitades: la mitad izquierda contiene todos los elementos menores que el pivote, y la mitad derecha contiene todos los elementos mayores que/iguales al pivote. Luego, ordena las dos mitades y finalmente coloca el pivote en el medio.

Si el lado que está ordenando rápidamente tiene menos de 3 elementos, puede simplemente intercambiar los dos elementos o abandonarlos, y esa parte de la matriz está lista.

Pero no parece que su código lo haga en absoluto: llama a Quicksort 6 veces desde su cliente, y dentro de la función quicksort está haciendo como máximo un intercambio. Así que este no es un caso en el que alguien pueda ver su código y depurarlo diciéndole que mueva un intercambio o algo así. Necesitas revisar tu lógica.

Salida del diagrama de Wikipedia para un ejemplo visual de lo que se supone que sucede en una sola iteración:

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

Answer 2

Hay implementaciones de código abierto de la clasificación rápida en Apache Harmony y Apache Mahout, probablemente, entre muchos otros. Puedes leerlos.

Answer 3

Por favor, encontrar el código de trabajo integral para algoritmo de ordenación rápida implementado en Java aquí,

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

Answer 4

Su bucle no está funcionando correctamente. Consulte el código que es resolver su problema sobre 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); 
    } 
} 

referirse 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

aquí es un algoritmo de ordenación rápida

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()); 
      } 
     } 
    } 

también disponible con la descripción en nathan's computer knowledge con una descripción [código ] [/ code] ``