Thursday, October 22, 2015

SelectionSort in Java

 public static void selectionsort(int[] A) {
  for (int i = 0; i < A.length; i++) {
   int min = i;
   for (int j = i+1; j < A.length; j++) {
    if (A[j] < A[min]) {
     min = j;
    }
   }
   swap(A, i, min);
  }
 }

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


InsertionSort in Java

 public static void insertionsort(int[] A) {
  for (int i = 1; i < A.length; i++) {
   for (int j = i; j > 0 && A[j] < A[j - 1]; j--) {
    swap(A, j, j - 1);
   }
  }
 }

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


MergeSort in Java

 public static void mergesort(int[] A) {
  int[] aux = new int[A.length];
  mergesort(A, aux, 0, A.length-1);
 }
 private static void mergesort(int[] A, int[] aux, int lo, int hi) {
  if (lo >= hi) return;
  int m = (lo+hi) / 2;
  mergesort(A, aux, lo, m);
  mergesort(A, aux, m+1, hi);
  merge(A, aux, lo, m, hi);
 }
 private static void merge(int[] A, int[] aux, int lo, int m, int hi) {
  int i = lo;
  int j = m+1;
  for (int k=lo; k <= hi; k++) {
   if (i > m) {
    aux[k] = A[j];
    j++;
   } else if (j > hi) {
    aux[k] = A[i];
    i++;
   } else if (A[j] < A[i]) {
    aux[k] = A[j];
    j++;
   } else {
    aux[k] = A[i];
    i++;
   }
  }
  for (int k=lo; k <= hi; k++) {
   A[k] = aux[k];
  }
 }


QuickSort in Java

 public static void quicksort(int[] A) {
  quicksort(A, 0, A.length-1);
 }
 
 private static void quicksort(int[] A, int lo, int hi) {
  if (lo >= hi) return;
  int p = partition(A, lo,hi);
  quicksort(A, lo, p-1);
  quicksort(A, p+1, hi);
 }
 
 private static int partition(int[] A, int lo, int hi) {
  int i = lo+1;
  int j = hi;
  while (i <= j) {
   while (A[i] < A[lo]) {
    i++;
    if (i > hi) break;
   }
   while (A[j] > A[lo]) {
    j--;
   }
   if (i <= j) {
    swap(A, i, j); 
    i++;
    j--;
   }
  }
  swap(A, lo, j); 
  return j;
 }

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