Merge Sort and Quick Sort

Merge Sort

The algorithm is fairly simple and is defined recursively. If the number of items to be sorted is 0 or 1 return from sorting. Otherwise recursively sort the first and second halves of the array separately and then merge the two sorted halves into a sorted group.

public static void  callMergeSort (int[] a)
{	
  int[] tmp = new int [a.length];
  mergeSort (a, tmp, 0, a.length - 1);
}

private static void mergeSort (int[] a, int[] tmp, int left, int right)
{	
  int center;
  if (left < right)
  {	
    center = (left + right) / 2;
    mergeSort (a, tmp, left, center);
    mergeSort (a, tmp, center+1, right);
    merge (a, tmp, left, center, right);
  }
}

private static void merge (int[] a, int[] tmp, int left, int center, int right)
{	
  int first1 = left;		
  int last1 = center;
  int first2 = center + 1;	
  int last2 = right;

  int idx = first1;

  while ((first1 <= last1) && (first2 <= last2))
  {	
    if (a[first1] < a[first2])
      tmp[idx++] = a[first1++];
    else 
      tmp[idx++] = a[first2++];
  }

  while (first1 <= last1)
    tmp[idx++] = a[first1++]; 

  while (first2 <= last2)
    tmp[idx++] = a[first2++];

  for (idx = left; idx <= right; idx++)
    a[idx] = tmp[idx];
}

Quick Sort

The basic Quicksort algorithm is also defined recursively. The advantage of Quicksort over Mergesort is that the swapping of the elements are done in place and we do not have to create another array to store intermediate results. The algorithm can be stated as follows for a set of S elements:

If the number of elements in S is 0 or 1 then return from sorting.
Pick any element p in S. It is called the pivot.
Partition S - {p} ( the remaining elements in S ) into two disjoint groups: L = {x ε S - {p} | x <= p} and R = { x ε S - {p} | x > p}
Return the result of Quicksort(L) followed by p followed by Quicksort(R).

public static void qsort1 (int a[], int lo, int hi)
{	
  if (lo >= hi) return;
  int pivot = a[lo];
  int m = lo;
  for ( int i = lo + 1; i <= hi; i++ )
  {	
    if (a[i] < pivot)
    { 
      m = m + 1;  
      swap (a, m ,i); 
    }
  }
  swap (a, lo, m);
  qsort1 (a, lo, m - 1);
  qsort1 (a, m + 1, hi);
}

public static void qsort2 (int a[], int lo, int hi)
{	
  if (lo >= hi) return;
  int left = lo;    
  int right = hi;    
  int pivot = a[(lo+hi)/2];
	
  while ( left < right)
  {	
    while (a[left] < pivot) left++;
    while (pivot < a[right]) right--;
    if (left <= right)
    {  
      swap (a, left, right);   
      left++;    
      right--;
    }
  }

  qsort2 (a, lo, right);
  qsort2 (a, left, hi);
}

public static void swap (int a[], int i, int j);
{
  int tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}

Permutation


public class Permute
{
  public static void printArray (int[] a)
  {
     for (int i = 0; i <= a.length - 1; i++)
     {
       System.out.print (a[i] + " ");
     }
     System.out.println ();
  }

  public static void swap (int[] a, int i, int j)
  {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  public static void perm (int[] a, int lo, int hi)
  {
    if ( lo == hi )
      printArray (a);
    else
    {
      for (int i = lo; i <= hi; i++)
      {
        swap (a, lo, i);
	perm (a, lo+1, hi);
	swap (a, i, lo);
      }
    }
  }

  public static void main (String[] args)
  {
    int[] a = {1, 2, 3};
    perm (a, 0, a.length - 1);
  }
}

Combination


import java.util.*;

public class Combine
{ 
  public static void printArray (int[] b, int size)
  {
    for (int i = 0; i < size; i++)
      System.out.print (b[i] + " ");
    System.out.println();
  }

  public static void combine (int[] a, int[] b, int aIdx, int bIdx, int size)
  {
    int range = a.length - size + 1;
    if (bIdx == size)
    {
      printArray (b, size);
    }
    else
    {
      while (aIdx < range + bIdx)
      {
        b[bIdx++] = a[aIdx++];
	combine (a, b, aIdx, bIdx, size);
	bIdx--;
      }
    }
  }

  public static void main (String [] args)
  {
    Scanner sc = new Scanner (System.in);
    System.out.print ("Enter size of distribution: ");
    int length = sc.nextInt();
    System.out.print ("Enter size of group: ");
    int size = sc.nextInt();
    int[] a = new int[length];
    int[] b = new int[length];
    for (int i = 0; i < length; i++)
      a[i] = i + 1;
    combine (a, b, 0, 0, size);
  }
}