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 the 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.

I would be happy to connect with you guys on social media. It’s @coderstea on Twitter, Linkedin, Facebook, Instagram, and YouTube.

Please Subscribe to the newsletter to know about the latest posts from CodersTea.

You can see the whole Data Structure and Algorithms project on 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 void sort(int[] arr) {
  for (int i = 0; i < arr.length; i++) {

    // inner loop upto 2nd last element
    for (int j = 0; j < arr.length - 1; j++) {
      // if current element is greater than the next one, swap them
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
}Code language: JavaScript (javascript)

Insertion Sort

public void sort(int[] arr) {
  // start with 2nd element assuming the 0th element is sorted
  for (int i = 1; i < arr.length; i++) {
    // copy the current element
    int curr = arr[i];
    int j = i - 1; // traverse the left side excluding current

    // shift element to right until
    // the element is greater than the 'curr'
    // or you reach the start of the array
    while (j >= 0 && arr[j] > curr) {
      arr[j + 1] = arr[j]; // shift the element to right
      j--; // move pointer to one index left
    }
    // INSERT the current element resulting the left side as sorted
    arr[j + 1] = curr;
  }
}Code language: JavaScript (javascript)

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 void sort(int[] arr) {
  // Select the minimum on the right side
  // and swap it with the current value

  for (int i = 0; i < arr.length; i++) {
    int minValIndex = i;
    // traverse right side of the array from curr element
    for (int j = i + 1; j < arr.length; j++) {
      // if the current index value is less than min value
      // make current index as min value index
      if (arr[j] < arr[minValIndex]) {
        minValIndex = j;
      }
    }
    // swap the current value with minValIndex value
    swap(arr, i, minValIndex);
  }
}Code language: JavaScript (javascript)

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:

QuickSort Code:

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

public void quickSort(int[] arr, int left, int right) {
  // in case it has one or zero elements don't do anything
  if (left >= right) return;

  // partition i.e. sort the array and get partitioned index
  int partitionedIndex = partition(arr, left, right);

  // repeat the process for right side
  quickSort(arr, left, partitionedIndex - 1); // important to use -1

  // repeat the process for left side
  quickSort(arr, partitionedIndex, right);
}


Code language: JavaScript (javascript)

Quick Sort Partitioning Code:

private int partition(int[] arr, int left, int right) {
  // it's best to use middle as pivot index
  int pivotIndex = left + (right - left) / 2;
  int pivotValue = arr[pivotIndex];

  // sort the array from pivot such that
  // left side is less than pivot and right side is greater than pivot
  while (left <= right) {
    // move left pointer to right until its left value is smaller
    while (arr[left] < pivotValue) left++;

    // move right pointer to left until its right value is greater
    while (arr[right] > pivotValue) right--;

    // swap the values of left and right in case
    // left index is equal to or less than right index
    if (left <= right) {
      swap(arr, left, right);
      // move the pointer to skip the processed index
      left++;
      right--;
    }
  }
  // return the left index as partition Index
  return left;
}Code language: PHP (php)

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:

MergeSort:

public void sort(int[] arr) {
  int[] tempArr = new int[arr.length];
  mergeSort(arr, tempArr, 0, arr.length - 1);
}

public void mergeSort(int[] arr, int[] tempArr, int left, int right) {
  // in case of one or zero element do nothing
  if (left >= right) return;

  int mid = left + (right - left) / 2; // or (right + left) /2

  // sort left side
  mergeSort(arr, tempArr, left, mid);

  // sort right side
  mergeSort(arr, tempArr, mid + 1, right);

  // merge the sorted array
  mergeSortedArray(arr, tempArr, left, right);
}Code language: JavaScript (javascript)

Merge Sorted Array Code:

private void mergeSortedArray(int[] arr, int[] tempArr, int left, int right) {
  int leftStart = left;
  int rightEnd = right;
  int leftEnd = leftStart + (rightEnd - leftStart) / 2; // simply middle index
  int rightStart = leftEnd + 1;

  int sortedIndex = leftStart;
  //  traverse until one of the start index reaches corresponding end index
  while (leftStart <= leftEnd && rightStart <= rightEnd) {
    // if left value is smaller or equal than the right side,
    // use it and increment left pointer
    if (arr[leftStart] <= arr[rightStart]) {
      tempArr[sortedIndex] = arr[leftStart];
      leftStart++;
    } else { // else use right index and increment right index
      tempArr[sortedIndex] = arr[rightStart];
      rightStart++;
    }
    sortedIndex++; // increment it anyway
  }

  // in case one of the array reaches the end first, we need to
  // make sure remaining values are copied.

  /** I used arraycopy but for simplicity you can use while loop also */

  // copy left array if remaining
  // (leftEnd - leftStart + 1) will give zero if nothing remaining
  System.arraycopy(arr, leftStart, tempArr, sortedIndex, leftEnd - leftStart + 1);

  // copy right array if remaining
  // (rightEnd - rightStart + 1) will give zero if nothing remaining
  System.arraycopy(arr, rightStart, tempArr, sortedIndex, rightEnd - rightStart + 1);

  // copy the full temp array from left to right
  System.arraycopy(tempArr, left, arr, left, right - left + 1);
}Code language: PHP (php)

Testing

I have added a test in the GitHub repo so that you can play around and check if it’s working or not.

Here is the Test code Link.

Conclusion

I will be updating this as I write more algorithms and explanations. I will try to include a table of content as well for 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 the next post. HAKUNA MATATA!!!

I would be happy to connect with you guys on social media. It’s @coderstea on Twitter, Linkedin, Facebook, Instagram, and YouTube.

Please Subscribe to the newsletter to know about the latest posts from CodersTea.