Home DSA A Quick Glance at Sorting Algorithms Code in Java

A Quick Glance at Sorting Algorithms Code in Java

Published: Last Updated on 1 comment 1.2k views

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.

You can follow me on social media via @coderstea on TwitterLinkedinFacebook, or Instagram. We also share high-quality videos about programming on our YouTube channel. You can also publish your post on CodersTea, just share your thought on Contact Us or let us know in the comments.

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

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) { // 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!!!

You can follow me on social media via @coderstea on TwitterLinkedinFacebook, or Instagram. We also share high-quality videos about programming on our YouTube channel. You can also publish your post on CodersTea, just share your thought on Contact Us or let us know in the comments.

Subscribe
Notify of
guest
1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Newsletter

Subscribe my Newsletter for new blog posts, tips & new photos. Let's stay updated!

@2022 All Right Reserved. Designed and Developed by CodersTea

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More