QuickSort

QuickSort

Java version

int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      return i;
}

void quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

c++/c

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

My C++

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;

void printVector(vector<int> v)
{
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<",";
    }
    cout<<endl;
}

int partition(vector<int> &v,int i,int j)
{
    int left = i;
    int right = j;
    int pivot = v[(i+j)/2];    

    while(i <= j)
    {
        while(v[i] < pivot)
            i++;
        while(v[j] > pivot)
            j--;
        if(i <= j)
        {
            int temp = v[i];
            v[i] = v[j];
            v[j] = temp;

            i++;
            j--;
        }
    }

    return i-1;
}

void quickSort(vector<int> &v,int left,int right)
{
    int k = partition(v,left,right);    
    printVector(v);
    if(k > left)
        quickSort(v,left,k);
    if(right > k + 1)
        quickSort(v,k+1,right);
}

int main()
{
    vector<int> v;
    for(int i=0;i<20;i++)
        v.push_back(rand() % 100);    
    printVector(v);

    quickSort(v,0,v.size()-1);

    printVector(v);
    return 0;
}