Programme d'algorithme Quicksort en Java
J'essaie d'implémenter le programme d'algorithme QuickSort en Java, mais je reçois une réponse incorrecte.
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;
}
}
Le programme ci-dessus me donnant la sortie comme: 12 23 22 33 34 33 64 34 64
Quelqu'un pourrait-il me dire comment puis-je obtenir le résultat de mon désir?
6 answers
Le problème est que ce n'est pas vraiment comment quicksort œuvres. Quicksort est un algorithme récursif qui ne doit être appelé qu'une seule fois de l'extérieur de lui-même. L'idée est qu'à chaque itération, vous partitionnez le tableau en deux moitiés - la moitié gauche contient tous les éléments inférieurs au pivot, et la moitié droite contient tous les éléments supérieurs / égaux au pivot. Ensuite, vous quicksort les deux moitiés, et enfin mettre le pivot au milieu.
Si le côté que vous êtes quicksorting est inférieur à 3 éléments de long, vous pouvez simplement échanger les deux éléments ou les laisser, et cette partie du tableau est terminée.
Mais il ne semble pas que votre code le fasse du tout - vous appelez Quicksort 6 fois depuis votre client, et dans la fonction quicksort vous effectuez au plus un échange. Ce n'est donc pas un cas où quelqu'un va pouvoir regarder votre code et le déboguer en vous disant de déplacer un swap ou quelque chose. Vous devez revoir votre logique.
Découvrez le Diagramme Wikipedia pour un exemple visuel de ce qui est censé se passer en une seule itération:
Il existe des implémentations open source de quicksort dans Apache Harmony et Apache Mahout, probablement parmi beaucoup d'autres. Vous pouvez les lire.
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;
}
Voici un algorithme 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());
}
}
}
Également disponible avec description à connaissances informatiques de nathan avec une description [code] [/code] ``
Votre boucle ne fonctionne pas correctement. Référez-vous au code qui résout votre problème à propos de 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);
}
}
Référez-vous à Tri rapide.
Veuillez trouver un code de travail complet pour l'algorithme de tri rapide implémenté en Java ici,