QuickSort problem

Question

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]+", ");
}

}

Answer 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

Answer 2

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

Answer 3

ok i see now . in the for loop forgot the swap you did. thank you very much again !

Answer 4

Your welcome :)

Answer 5

thank you very much ! may i ask why you swap right in the beginning the pivot with the last element ?

Answer 6

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

Answer 7

but i think ot costs too much time.. also if pivot is 0, it doesnt work 100%