We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
static int partition(int ar[], int minpos, int maxpos)
{
int p = ar[minpos];
ArrayList<Integer> leftlist = new ArrayList<Integer>();
ArrayList<Integer> rightlist = new ArrayList<Integer>();
for(int i = minpos+1 ; i <= maxpos; i++)
{
if(ar[i] > p)
rightlist.add(ar[i]);
else
leftlist.add(ar[i]);
}
copy(leftlist,ar,minpos);
int ppos = leftlist.size()+minpos;
ar[ppos] = p;
copy(rightlist,ar,ppos+1);
return minpos + leftlist.size();
}
static void copy(ArrayList<Integer> list, int ar[], int startIdx)
{
for(int num : list)
{
ar[startIdx++] = num;
}
}
static void quickSort(int ar[], int minpos, int maxpos)
{
if(minpos >= maxpos)
return;
int pos = partition (ar,minpos,maxpos);
quickSort(ar,minpos,pos-1);
quickSort(ar,pos+1,maxpos);
printArray(ar,minpos, maxpos);
}
static void quickSort(int[] ar)
{
quickSort(ar,0,ar.length-1);
}
static void printArray(int[] ar,int start, int end)
{
for(int i = start; i <= end;i++)
{
System.out.print(ar[i]+" ");
}
System.out.println("");
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] ar = new int[n];
for(int i=0;i<n;i++){
ar[i]=in.nextInt();
}
quickSort(ar);
}
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Quicksort 2 - Sorting
You are viewing a single comment's thread. Return to all comments →
Solution in JAVA :- public class Solution {
static void printArray(int[] ar,int start, int end) { for(int i = start; i <= end;i++) { System.out.print(ar[i]+" "); } System.out.println(""); }
}