Skip to content

Instantly share code, notes, and snippets.

@tranvanthuc

tranvanthuc/sortAlgir

Created October 27, 2016 03:46
Show Gist options
  • Save tranvanthuc/96dd731fc6eef64483d9c428d7a25f28 to your computer and use it in GitHub Desktop.
Save tranvanthuc/96dd731fc6eef64483d9c428d7a25f28 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tranvanthuc created this gist Oct 27, 2016.
    314 changes: 314 additions & 0 deletions sortAlgir
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,314 @@
    package src;

    public class SortingAlgorithms {

    public static double[] bubbleSort(double[] myArray) {
    double[] arr = new double[myArray.length];
    System.arraycopy(myArray, 0, arr, 0, myArray.length);
    for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - i - 1; j++) {
    if (arr[j] > arr[j + 1]) {
    swap(arr, j, j + 1);
    }
    }
    }
    return arr;
    }

    public static double[] selectionSort(double[] myArray) {
    int min;
    double[] arr = new double[myArray.length];
    System.arraycopy(myArray, 0, arr, 0, myArray.length);
    for (int i = 0; i < arr.length - 1; i++) {
    min = i;
    for (int j = i + 1; j < arr.length; j++)
    if (arr[j] < arr[min])
    min = j;
    swap(arr, min, i);
    }
    return arr;
    }

    public static double[] insertionSort(double[] myArray) {
    double[] arr = new double[myArray.length];
    System.arraycopy(myArray, 0, arr, 0, myArray.length);
    for (int i = 1; i < arr.length; i++) {
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
    swap(arr, j, j - 1);
    j = j - 1;
    }
    }
    return arr;
    }

    // Array A[] has the items to sort; array B[] is a work array.
    public static double[] topDownMergeSort(double[] myArray, double[] B) {
    double[] arr = new double[myArray.length];
    System.arraycopy(myArray, 0, arr, 0, myArray.length);
    CopyArray(arr, 0, arr.length, B); // duplicate array A[] into B[]
    TopDownSplitMerge(B, 0, arr.length, arr); // sort data from B[] into A[]
    // displayArr(A);
    return arr;
    }

    public static double[] heapSort(double[] myArray) {
    double[] arr = new double[myArray.length];
    System.arraycopy(myArray, 0, arr, 0, myArray.length);
    buildheap(arr);
    for (int i = arr.length - 1; i >= 1; i--) {
    double temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
    }
    // displayArr(a);
    return arr;
    }

    public static double[] quickSort(double[] myArray) {
    double[] arr = new double[myArray.length];
    System.arraycopy(myArray, 0, arr, 0, myArray.length);
    recursiveQuickSort(arr, 0, arr.length - 1);
    return arr;
    }

    public static double[] shellSort(double[] myArray) {
    double[] arr = new double[myArray.length];
    System.arraycopy(myArray, 0, arr, 0, myArray.length);
    int inner, outer;
    double temp;

    int h = 1;
    while (h <= arr.length / 3) {
    h = h * 3 + 1;
    }
    while (h > 0) {
    for (outer = h; outer < arr.length; outer++) {
    temp = arr[outer];
    inner = outer;
    while (inner > h - 1 && arr[inner - h] >= temp) {
    arr[inner] = arr[inner - h];
    inner -= h;
    }
    arr[inner] = temp;
    }
    h = (h - 1) / 3;
    }
    return arr;
    }

    public static double[] combSort(double[] myArray) {
    double[] arr = new double[myArray.length];
    System.arraycopy(myArray, 0, arr, 0, myArray.length);
    /*
    * This function sorts a list in-place using CombSort11. It works
    * exactly like BubbleSort except that instead of looking at i and i+1
    * when iterating, it looks at i and i+gap. This helps reposition small
    * values stuck at the end of the array.
    */

    int gap = arr.length; // The distance between elements being compared
    boolean swapped = true;
    int i; // Our index

    // keep looping until you make
    // a complete pass without swapping
    while (gap > 1 || swapped) {

    // 1.3 is the shrink factor.
    // I found it to be the fastest.
    // A gap can not be smaller than 1,
    // hence the "if (gap > 1)"
    if (gap > 1) {
    gap = (int) (gap / 1.3);
    }

    // This is why it is CombSort11
    // instead of CombSort. I find
    // doing this increases the speed
    // by a few milliseconds.
    if (gap == 9 || gap == 10) {
    gap = 11;
    }

    i = 0;
    swapped = false;

    // Loop through comparing numbers a gap-length apart.
    // If the first number is bigger than the second, swap them.
    while (i + gap < arr.length) {
    if (arr[i] > arr[i + gap]) {
    swap(arr, i, i + gap);
    swapped = true;
    }
    i++;
    }
    }
    return arr;
    }

    //compare array
    public static boolean compareArray(double[] arr1, double[]arr2){
    if(arr1.length != arr2.length)
    return false;
    else {
    for(int i=0 ; i<arr1.length; i++){
    if(arr1[i] != arr2[i])
    return false;
    }
    }
    return true;
    }

    //display array
    public static void displayArr(double[] arr) {
    System.out.println("Array: ");
    for (int i = 0; i < arr.length; i++) {
    System.out.print(arr[i] + " ");
    }
    System.out.println();
    }

    public static String toStringArray(double[] arr) {
    String result= "";
    for (int i = 0; i < arr.length; i++) {
    result += arr[i] + " ";
    }
    return result;
    }




    // Sort the given run of array A[] using array B[] as a source.
    // iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).

    /**
    * Recursive quicksort logic
    *
    * @param array input array
    * @param startIdx start index of the array
    * @param endIdx end index of the array
    */
    public static void recursiveQuickSort(double[] array, int startIdx, int endIdx) {

    int idx = partition(array, startIdx, endIdx);

    // Recursively call quicksort with left part of the partitioned array
    if (startIdx < idx - 1) {
    recursiveQuickSort(array, startIdx, idx - 1);
    }

    // Recursively call quick sort with right part of the partitioned array
    if (endIdx > idx) {
    recursiveQuickSort(array, idx, endIdx);
    }
    }

    /**
    * Divides array from pivot, left side contains elements less than
    * Pivot while right side contains elements greater than pivot.
    *
    * @param array array to partitioned
    * @param left lower bound of the array
    * @param right upper bound of the array
    * @return the partition index
    */
    public static int partition(double[] array, int left, int right) {
    double pivot = array[left]; // taking first element as pivot

    while (left <= right) {
    //searching number which is greater than pivot, bottom up
    while (array[left] < pivot) {
    left++;
    }
    //searching number which is less than pivot, top down
    while (array[right] > pivot) {
    right--;
    }

    // swap the values
    if (left <= right) {
    double tmp = array[left];
    array[left] = array[right];
    array[right] = tmp;

    //increment left index and decrement right index
    left++;
    right--;
    }
    }
    return left;
    }



    private static void TopDownSplitMerge(double[] B, int iBegin, int iEnd, double[] A) {
    if (iEnd - iBegin < 2) // if run size == 1
    return; // consider it sorted
    // split the run longer than 1 item into halves
    int iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
    TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
    }

    // Left source half is A[ iBegin:iMiddle-1].
    // Right source half is A[iMiddle:iEnd-1 ].
    // Result is B[ iBegin:iEnd-1 ].
    private static void TopDownMerge(double[] A, int iBegin, int iMiddle, int iEnd, double[] B) {
    int i = iBegin, j = iMiddle;

    // While there are elements in the left or right runs...
    for (int k = iBegin; k < iEnd; k++) {
    // If left run head exists and is <= existing right run head.
    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
    B[k] = A[i];
    i = i + 1;
    } else {
    B[k] = A[j];
    j = j + 1;
    }
    }
    }

    private static void CopyArray(double[] A, int iBegin, int iEnd, double[] B) {
    for (int k = iBegin; k < iEnd; k++)
    B[k] = A[k];
    }

    private static void heapify(double a[], int n, int i) {
    int max, child;
    child = 2 * i + 1;
    max = i;
    if (child < n)
    if (a[child] > a[max])
    max = child;
    if (child + 1 < n)
    if (a[child + 1] > a[max])
    max = child + 1;
    if (max != i) {
    double temp = a[i];
    a[i] = a[max];
    a[max] = temp;
    heapify(a, n, max);
    }
    }

    private static void buildheap(double a[]) {
    for (int i = a.length / 2 - 1; i >= 0; i--)
    heapify(a, a.length, i);
    }


    private static void swap(double[] arr, int index1, int index2) {
    double tempNum = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tempNum;
    }


    }