Problem Quicksort

#1

Two test case passed but 1 test case fail can you please tell me what is wrong with my code
import java.util.*;
public class Main {
public static int partition(int arr[],int low,int high){
int temp,s,j;
int i=low-1;
int p=arr[high];
for(j=low;j<high;j++){
if(arr[j]<p){
i++;
temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
s= arr[i+1];
arr[i+1]=arr[high];
arr[high]=s;
return i+1;
}
public static void sort(int arr[],int low,int high){
if(low<high){
int pi=partition(arr,low,high);
sort(arr,low,pi-1);
sort(arr,pi+1,high);
}
}
public static void arrays(int arr[],int n){
for(int i=0;i<n;i++){
System.out.print(arr[i]+" ");
}}

public static void main(String args[]) {
	try{
	Scanner sc=new Scanner(System.in);
	int n=sc.nextInt();
    int arr[] =new int[n];
    System.out.println();
	for(int h=0;h<n;h++)
	arr[h]=sc.nextInt();
    Main ob = new Main(); 
    ob.sort(arr, 0, n-1);  
    System.out.println();
 arrays(arr,n); 
}catch(Exception e){System.out.println(e);}
 }

}

#2

HI @Sweta,
Your code is correct but there is a problem that it takes too much time and there is a iterative version of quick sort which is a bit fast and the question gives all correct for that code .
You may try yourself but if you ask i will send that code .

#3

And also there is given in the question to use randomized quick sort or else worse case will not pass . So use randomized quick sort

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like
#5

ur code is correct.
but it is showing time limit when i submitting ur code for a given test case.

actually that test case is very large.
may be ur code showing worst quick sort complexity for the given condition.

so just use the random funtion to find the pivot.

this solution is given in the solution section and this is fine.
the main difference is the way of accessing pivot element.

don’t use pivot as the last element, always try to use random pivot element
int pivotIndex = be + rand() % (end - be+1);

public static void quicksort(int[] arr, int lo, int hi) {

    if (lo >= hi) {
        return;
    }
    // partitioning
    int mid = (lo + hi) / 2;
    int pivot = arr[mid];

    int left = lo;
    int right = hi;

    while (left <= right) {

        while (arr[left] < pivot)
            left++;
        while (arr[right] > pivot)
            right--;

        if (left <= right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    quicksort(arr, lo, right);
    quicksort(arr, left, hi);
}

hope this will help u
pls rate my work so that i can imporve my work.

1 Like