A Quick Glance at Sorting Algorithms Code in Java

Hey! tea lover! This post is not a tutorial, just code samples of different sorting algorithms you can see before going to interview. I have written the algorithms in Java. There is little to no explanation, just pure simple code for you to quickly glance through it. The purpose of making this is to put all the sorting algorithms Java code in one place only.

You can see the whole Data Structure and Algorithms project on the GitHub.

Bubble Sort

Time Complexity:

  • Best Case: O(n)
  • Avg Case: O(n^2)
  • Worst Case: O(n^2)

Space Complexity: O(1)

Java Code:

public int[] sort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

Insertion Sort

Time Complexity:

  • Best Case: O(n)
  • Avg Case: O(n^2)
  • Worst Case: O(n^2)

Space Complexity: O(1)

Java Code:

public int[] sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int currValue = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > currValue) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = currValue;
    }
    return arr;
}

Selection Sort

Time Complexity:

  • Best Case: O(n^2)
  • Avg Case: O(n^2)
  • Worst Case: O(n^2)

Space Complexity: O(1)

Java Code:

public int[] sort(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) {
        int minValueIndex = i;
        for (int j = i + 1; j < arr.length; j++)
            if (arr[minValueIndex] > arr[j])
                minValueIndex = j;

        //swap min value with first index of sub array
        int temp = arr[minValueIndex];
        arr[minValueIndex] = arr[i];
        arr[i] = temp;
    }

    return arr;
}

Quick Sort

Time Complexity:

  • Best Case: O(n log n)
  • Avg Case: O(n log n)
  • Worst Case: O(n^2)

Space Complexity: O(n)

Java Code:

public int[] sort(int[] arr) {

    quickSort(arr, 0, arr.length - 1);
    return arr;
}

void quickSort(int[] arr, int low, int high) {
    int i = low;
    int j = high;
    int pivot = arr[low];

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

        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;

            i++;
            j--;
        }
    }

    if (low < j) {
        quickSort(arr, low, j);
    }
    if (high > i) {
        quickSort(arr, i, high);
    }
}

Merge Sort

Time Complexity:

  • Best Case: O(n log n)
  • Avg Case: O(n log n)
  • Worst Case: O(n log n)

Space Complexity: O(n)

Java Code:

public int[] sort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
    return arr;
}

void mergeSort(int[] arr, int low, int high) {
    if (low < high) {
        int middle = low + (high - low) / 2;
        mergeSort(arr, low, middle);
        mergeSort(arr, middle + 1, high);
        mergeParts(arr, low, middle, high);
    }
}

void mergeParts(int[] arr, int low, int middle, int high) {

    int leftArrSize = middle - low + 1;
    int rightArrSize = high - middle;

    int[] leftArr = new int[leftArrSize];
    int[] rightArr = new int[rightArrSize];

    System.arraycopy(arr, low, leftArr, 0, leftArrSize);
    System.arraycopy(arr, middle + 1, rightArr, 0, rightArrSize);

    int i = 0, j = 0, k = low;

    while (i < leftArrSize && j < rightArrSize) {
        if (leftArr[i] < rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    while (j < rightArrSize) {
        arr[k++] = rightArr[j++];
    }
    while (i < leftArrSize) {
        arr[k++] = leftArr[i++];
    }
}

I will be updating this as I write more algorithms and explanations. I will try to include table of content as well to better navigation. Please feel free to give any feedback as I am trying to write more and more and need some motivation as well.

You can check out other posts of me in Java, Spring, or Best Practices in the programming world.

See you in next post.

Leave a Reply

Your email address will not be published. Required fields are marked *