Quick Sort

Input	Array of integers (tested for 20 inputs)
Output	Sorted sequence
Complexity	Worst case : Θ(n2)

QUICKSORT(A, p, r)
[Quicksort is based on the divide-and-conquer paradigm which takes an array A to sort. Here the initial call is QUICKSORT(A, 1, length[A]) so p is the first element and r is the last element. A[i] denote the ith element of array A]

1 if p < r
2 	then q ← PARTITION(A, p, r)
3 		QUICKSORT(A, p, q - 1)
4 		QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
1 x ≤ A[r]
2 i ≤ p - 1
3 for j ≤ p to r - 1
4 	do if A[j] ≤ x
5 		then i ← i + 1
6 			exchange A[i] ↔ A[j]
7 exchange A[i + 1] ↔ A[r]
8 return i + 1

//WAP to implement Quick Sort

#include<stdio.h>
#include<conio.h>
#define  MAX 20
void quick_sort(int a[], int, int);
int main()
{
  int arr[MAX];   
  int size;       
  int count;      
  int num;        
  printf("Enter the size of array::");
  scanf("%d", &size);
  if (size > MAX)
  {
    printf("Input array size is greater than declared\n");
    exit(1);
  }
  printf("Enter %d array elements\n\n", size);
  for(count = 0; count < size; count++)
  {
    scanf("%d", &arr[count]);
  }
    quick_sort(arr, 0, size - 1);
  printf("\n\nSorted list is\n");
  for(count = 0; count < size; count++)
  {
    printf("%d\t", arr[count]);
  }
  return 0;
}

void quick_sort (int arr[], int left, int right)
{
  int ptr_left  = left;
  int ptr_right = right;
  int temp;
  int pivot     = arr[(left + right) / 2];
  while(ptr_left <= ptr_right)
  {
    while(arr[ptr_left] < pivot)
      ptr_left++;
    while(arr[ptr_right] > pivot)
      ptr_right--;
    if(ptr_left <= ptr_right)
    {
      temp           = arr[ptr_left];
      arr[ptr_left]  = arr[ptr_right];
      arr[ptr_right] = temp;
      ptr_left++;
      ptr_right--;
    }
  }
  if (left < ptr_right)
    quick_sort(arr, left, ptr_right);
  if (ptr_left < right)
    quick_sort(arr, ptr_left, right);
}

import java.io.*;
class sort
{
 
   void sortpivot(int a[],int beg,int end,int loc)
   {
     int left,right,temp;
     loc=left=beg;
     right=end;
     boolean done = false;
     while(!done)
     {
       while(a[loc]<=a[right] && (loc!=right) )
       right--;
       if(loc==right)
       done= true;
       else if(a[loc]>a[right])
       {
         temp= a[loc];
         a[loc]=a[right];
         a[right]=temp;
         loc = right;
       } 
       if(!done)
       {
         while((a[loc]>=a[left]) && (loc!=left))
         left++;
         if(loc==left)
         done = true;
         else 
         if(a[loc]>a[right])
         {
            temp=a[loc];
            a[loc]=a[left];
            a[left]=temp;
            loc=left;
         }
       } 
     } 
   } 
   void quicksort(int a[],int beg,int end)
   {
     int loc=1;
     if(beg<end)
     {
       sortpivot( a, beg, end, loc);
       quicksort(a,beg,loc-1);
       quicksort(a,loc+1,end);
     }
   }
}


class ques14a
{
      public static void main(String args[]) throws IOException
      {
         int n,i,j,k,temp;
         int a[] = new int[10];
         sort q = new sort(); 
         System.out.println("Enter the no. of elements u wanna enter:");
         BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
         n = Integer.parseInt(br.readLine());
         for(i=0;i<n;i++)
         {
              System.out.println("Enter the "+i+"th element:");
              a[i]= Integer.parseInt(br.readLine());
         }
         q.quicksort(a,0,n-1);
         System.out.println("The  list after QuickSort is:");
         for(i=0;i<n;i++)
         System.out.println(a[i]);
      }
}