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

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 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:

```.wp-block-code { border: 0; padding: 0; -webkit-text-size-adjust: 100%; text-size-adjust: 100%; } .wp-block-code > span { display: block; overflow: auto; } .shcb-language { border: 0; clip: rect(1px, 1px, 1px, 1px); -webkit-clip-path: inset(50%); clip-path: inset(50%); height: 1px; margin: -1px; overflow: hidden; padding: 0; position: absolute; width: 1px; word-wrap: normal; word-break: normal; } .hljs { box-sizing: border-box; } .hljs.shcb-code-table { display: table; width: 100%; } .hljs.shcb-code-table > .shcb-loc { color: inherit; display: table-row; width: 100%; } .hljs.shcb-code-table .shcb-loc > span { display: table-cell; } .wp-block-code code.hljs:not(.shcb-wrap-lines) { white-space: pre; } .wp-block-code code.hljs.shcb-wrap-lines { white-space: pre-wrap; } .hljs.shcb-line-numbers { border-spacing: 0; counter-reset: line; } .hljs.shcb-line-numbers > .shcb-loc { counter-increment: line; } .hljs.shcb-line-numbers .shcb-loc > span { padding-left: 0.75em; } .hljs.shcb-line-numbers .shcb-loc::before { border-right: 1px solid #ddd; content: counter(line); display: table-cell; padding: 0 0.75em; text-align: right; -webkit-user-select: none; -moz-user-select: none; -ms-user-select: none; user-select: none; white-space: nowrap; width: 1%; }```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) {
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!!!

Subscribe
Notify of 1 Comment
Inline Feedbacks

### Editors' Picks

@2023 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