TITLE:-Quick Sort Code
PROBLEM:-
Sort an array A using Quick Sort.
Line 1 : Integer n i.e. Array size
Line 2 : Array elements (separated by space)
Array elements in increasing order (separated by space)
Constraints :
1 <= n <= 10^3
6
2 6 8 5 4 3
Sample Output 1 :
2 3 4 5 6 8
5
1 5 2 7 3
Sample Output 2 :
1 2 3 5 7
SOLUTION:-
#include<iostream>
#include "Solution.h"
void quickSort(int input[], int size) {
/* Don't write main().
Don't read input, it is passed as function argument.
Change in the given array itself.
Taking input and printing output is handled automatically.
*/
if(size==0||size==1)
return;
int counter=0;
for(int i=1;i<size;i++)
if(input[i]<input[0])
counter++;
int temp=input[counter];
input[counter]=input[0];
input[0]=temp;
int i=0,j=size-1;
while(i<counter&&j>counter)
{
if(input[i]<input[counter])
i++;
else if(input[j]>=input[counter])
j--;
else{
int temp1=input[i];
input[i]=input[j];
input[j]=temp1;
i++;
j--;
}
}
quickSort(input,counter);
quickSort(input+counter+1,size-1-counter);
}
int main(){
int n;
cin >> n;
int *input = new int[n];
for(int i = 0; i < n; i++) {
cin >> input[i];
}
quickSort(input, n);
for(int i = 0; i < n; i++) {
cout << input[i] << " ";
}
delete [] input;
}