Quick Sort Program in Java

Question

I am trying to implement a QuickSort algorithm program in Java, but I am getting the wrong answer.

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

The above program gives me an output like: 12 23 22 33 34 33 64 34 64

Can someone tell me how I can get the result of my desire?

Answer 1

The problem is that this is actually not how quicksort works. Quicksort is a recursive algorithm that should only be called once from the outside. The idea is that at each iteration, you split the array into two halves - the left half contains all the elements smaller than the pivot point, and the right half contains all the elements larger or equal to the axis. Then you quickly sort the two halves and finally set the axis of rotation in the middle.

If the side you are doing quick sorting is less than 3 elements, you can simply swap the two elements or leave them, and this part of the array will be executed.

But this does not look like your code does this at all - you call Quicksort 6 times from your client, and inside quicksort you do no more than one swap. So this is not the case when someone can look at your code and debug it by telling you to move the swap or something like that. You need to rethink your logic.

Check out the Wikipedia diagram for a visual example of what should happen in one iteration:

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

Answer 2

Apache Harmony and Apache Mahout have open source versions for quick sorting, probably among many others. You can read them.

Answer 3

Please find the full working code for the fast sorting algorithm implemented in Java here,

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

Answer 4

Your loop is not working properly. Refer to the code that solves your problem 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); } } 

Consult 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

here is a quick sort algorithm

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

also available with a description on nathan computer knowledge with a description of [code] [/ code] ``