Source Code : A garbage-free randomised quicksort

Java Is Open Source Programming Language You Can Download From Java and Java Libraries From http://www.oracle.com. Click Here to download
We provide this code related to title for you to solve your developing problem easily. Libraries which is import in this program you can download from http://www.oracle.com. Click Here or search from google with Libraries Name you get jar file related it

A garbage-free randomised quicksort

  
//package com.ryanm.util;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/**
 * A garbage-free randomised quicksort
 * 
 * @author ryanm
 */
public class QuickSort {
  private static final Random rng = new Random();

  private QuickSort() {
    // no instances
  }

  /**
   * @param <T>
   * @param array
   * @param comp
   */
  public static <T> void sort(T[] array, Comparator<T> comp) {
    sort(array, comp, 0, array.length - 1);
  }

  /**
   * @param <T>
   * @param array
   * @param comp
   * @param lo
   *            lowest index to sort
   * @param hi
   *            highest index to sort
   */
  public static <T> void sort(T[] array, Comparator<T> comp, int lo, int hi) {
    if (hi > lo) {
      // choose random element to pivot on
      int pivotIndex = rng.nextInt(hi - lo) + lo;

      // swap elements till everything smaller than the pivot lies
      // before it
      pivotIndex = partition(array, comp, lo, hi, pivotIndex);

      // recurse
      sort(array, comp, lo, pivotIndex - 1);
      sort(array, comp, pivotIndex + 1, hi);
    }
  }

  /**
   * Shuffle elements around to partially-sorted low/pivot/high order
   * 
   * @param <T>
   * @param array
   * @param comp
   * @param lo
   * @param hi
   * @param pivotIndex
   *            the starting index of the pivot element
   * @return The new index of the pivot element
   */
  private static <T> int partition(T[] array, Comparator<T> comp, int lo,
      int hi, int pivotIndex) {
    T pivot = array[pivotIndex];

    // send pivot to the back
    swap(array, pivotIndex, hi);

    // index of low/high boundary
    int index = lo;

    for (int i = lo; i < hi; i++) {
      if (comp.compare(array[i], pivot) <= 0) { // element is lower or
                            // equal to the pivot
                            // swap it to the low
                            // region
        swap(array, i, index);
        index++;
      }
    }

    swap(array, hi, index);

    return index;
  }

  /**
   * Swaps elements
   * 
   * @param <T>
   * @param array
   * @param i
   * @param j
   */
  private static <T> void swap(T[] array, int i, int j) {
    T temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    Integer[] array = new Integer[15];
    Random rng = new Random();
    int split = 10;
    for (int i = 0; i < split; i++) {
      array[i] = new Integer(rng.nextInt(100));
    }
    for (int i = split; i < array.length; i++) {
      array[i] = null;
    }

    System.out.println(Arrays.toString(array));

    QuickSort.sort(array, new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
      };
    }, 0, split - 1);

    System.out.println(Arrays.toString(array));

  }
}

   
    
  

Thank with us