9.txt

Q Implement Quick Sort
Pivot element is the first element of array  [Hoare Method]
{
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
int partition (int arr[], int low, int high);
/* The main function that implements QuickSort
 arr[] --> Array to be sorted, low  --> Starting index, high  --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now at right place */
        int pi = partition(arr, low, high);
        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("
");
}
// Driver program to test above functions
int main()
{
    int arr[1000],n,T,i;
    scanf("%d",&T);
    while(T--){
    scanf("%d",&n);
    for(i=0;i<n;i++)
      scanf("%d",&arr[i]);
    quickSort(arr, 0, n-1);
    printArray(arr, n);
    }
    return 0;
}
}
/*This is a function problem.You only need to complete the function given below*/
/* The main function that implements QuickSort
 arr[] --> Array to be sorted,    low  --> Starting index,   high  --> Ending index
void quickSort(int arr[], int low, int high) {
    if (low < high)     {
        // pi is partitioning index, arr[p] is now  at right place
        int pi = partition(arr, low, high);
        // Separately sort elements before / partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}*/
/* This function takes last element as pivot, places  the pivot element 
   at its correct position in sorted  array, and places all smaller (smaller
   than pivot) to the left of pivot and all greater elements to right  of pivot */
int partition (int arr[], int low, int high)
{
    int i=low;
    int j=high;
    while(i<j)
    {
        while( arr[i]<=arr[low]&&i<high)
         i++;// i is pointing to the first element from left that is greater than pivot
        while(arr[j]>arr[low])//arr[low]is taken as pivot
         j--;// j jis pointing to first element from right less than or equal to pivot
        if(i<j)
        {
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }// swapped the value of ith and jth element(lesser element will be on left and higher element will be on right)
    }
    //by this loop lesser element will be on left but of arr[j] and higher element will be on right
    int temp=arr[low];
    arr[low]=arr[j];
    arr[j]=temp;
    return j;// we swap the values of arr[j] and pivot, to correctly place the pivot element
   // Your code here
}