0

# QuickSort problem

Hello everybody! I’m trying to implement the Quicksort algorithm but somehow I got stuck in an infinite loop and I don’t see why. Can somebody help me ? That’s the code: public class QuickSort { static void sort(int[]arr,int low, int high){ int l=low; int h=high; int q=0; if (l<h){ q=partition(arr,l,h); sort(arr,l,q); sort(arr,q+1,h); } } static int partition(int[]arr,int low, int high){ int pivot=(low+high)/2; int i=low; int j=high; while(i<=j){ while(arr[i]<pivot){ i++; } while(arr[j]>arr[pivot]){ j--; } if(i<j){ int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; i++; j--; } } return i; } public static void main(String[] args) { int []arr={4,1,25,77,0,80,2,7,4,3}; sort(arr,0,arr.length-1); for(int i=0; i<arr.length; i++) System.out.print(arr[i]+", "); } }

21st Jan 2020, 1:07 PM
Georgi
+ 1
I am not sure if the partition method works correct. But your sort method, which is recursive, has no end condition. If you want you can have a look into my code: https://code.sololearn.com/cSmqb1Do0nvM/?ref=app
21st Jan 2020, 4:04 PM
Denise Roßberg
+ 1
Georgi I swap pivot and right, to take the pivot element out of the list. End condition of for loop: i < right An example: 8 1 5 3 4 left = 0 right = 4 pivot = 2 -> 5 is the pivot element swap(pivot, right) -> 8 1 4 3 5 pivotIndex = 0 inside for loop: compare each element with the pivot element (which is on right index) i = 0 8 <= 5 -> false i = 1 1 <= 5 -> swap(0,1) -> 1 8 4 3 5 pivotIndex = 1 i = 2 4 <= 5 -> swap(1,2) -> 1 4 8 3 5 pivotIndex = 2 i = 3 3 <= 5 -> swap(2,3) -> 1 4 3 8 5 pivotIndex = 3 end loop (comparing pivot element with itself would make no sense) Now swap back the pivot element from right index to the position of pivotIndex: swap(3,4) -> 1 4 3 5 8 return pivotIndex //3 As you can see: all elements <= 5 are on the left side. And all elements > 5 are on the right side After that you only need to sort the left side: 1 4 3 And the right side: 8
22nd Jan 2020, 2:52 PM
Denise Roßberg
+ 1
ok i see now . in the for loop forgot the swap you did. thank you very much again !
22nd Jan 2020, 3:27 PM
Georgi
+ 1
22nd Jan 2020, 3:56 PM
Denise Roßberg
0
thank you very much ! may i ask why you swap right in the beginning the pivot with the last element ?
22nd Jan 2020, 10:12 AM
Georgi
0
i redid the partition method it looks like this now: static int partition(int[]arr,int low, int high){ int pivot=(low+high)/2; for (int i=low; i<pivot; i++){ for(int j=high; j>pivot;j--){ if(arr[i]>arr[j]) swap(arr,i,j); if(arr[i]>arr[pivot]) swap(arr,i,pivot); if(arr[j]<arr[pivot]) swap(arr,j,pivot); } } return pivot; }
22nd Jan 2020, 12:44 PM
Georgi
0
but i think ot costs too much time.. also if pivot is 0, it doesnt work 100%
22nd Jan 2020, 12:44 PM
Georgi