Sorting Algorithms in Java
Sorting is the process of putting a list, a sequence of provided items, or data collection into a specific order. In this article, we will discuss different sorting algorithms in Java such as Selection Sort, Bubble Sort, Insertion Sort, and Quick Sort.
Introduction
Sorting is the process of putting a list, a sequence of provided items, or data collection into a specific order. It comes in handy whenever we want our data to be organized. The significance of sorting resides in the fact that, if data is kept in a sorted fashion, data searches can be highly optimized. Data representation in more comprehensible formats is another use for sorting. The “dictionary” is the most typical illustration of sorting.
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Sorting Techniques
- Stable sorting: It is when a sorting algorithm sorts the items but does not alter the order in which related contents appear.
- Unstable sorting: It is when a sorting algorithm alters the order in which related items appear after sorting the data.
- In-Place Sorting: An in-place algorithm transforms the input “in-place” rather than requiring additional memory and producing the output in the same memory as the input.
- Out-Place Sorting: An algorithm that requires additional space and generates an output is known as an out-place/non-in-place sorting algorithm.
Different sorting algorithms
There is various type of sorting algorithm used by the developers, and each has its significance.
Selection sort
A straightforward sorting algorithm is a selection sort commonly referred to as an in-place comparison sort. It operates on the principle of repeatedly selecting the smallest element and assigning it to the proper location in the sorted order. The smallest element in the unsorted sublist is sought after for each iteration of the selection sort, and it is added to the end of the sorted sublist.
Steps to perform selection sort:
- Begin with the first component. The list as a whole is currently unsorted.
2. Find the smallest element in the list by iterating through it. Here you find 8, so we swap 8 with the element at the start of array 23.
3. After the first iteration you start getting your sorted part of the array. Let’s move ahead. Now you get 23 as the next smallest element so it will be swapped with the element at the second position.
4. Moving further, the next lowest element is 32, so it will be swapped by 45 so that you get the third element in your sorted sublist.
5. You have got your sorted sublist 8, 23, and 32 till now. Following the same steps at the end, you get your whole sorted array.
Below is the implementation of selection sort in Java.
Implementation:
// Java implementationclass SelectionSort{ public void selectionSort(int A[]) { int arraySize = A.length; for (int i = 0; i < arraySize - 1; i++) { //currently current minimum element index of the unsorted array is set as i int minIndex = i; //iterating unsorted array for (int j = i+1; j < arraySize; j++) //check for minimum element if (A[j] < A[minIndex]) minIndex = j; // swap the minimum element with the element at minIndex to // keep it at its position int temp = A[minIndex]; A[minIndex] = A[i]; A[i] = temp; } }}
Time and Space complexities:
The time complexity for this algorithm is:
TC: O(n^2)
SC: O(1)
Bubble Sort
The simplest sorting algorithm is bubble sort, commonly referred to as sinking sort. It operates on the principle of continually comparing the neighboring elements in a left to the right direction and exchanging them if they are out of order. The cycle of repeating continues until the list is sorted. Bubble sequentially compares each item in a list and orders them according to their values. Large data sets are not a good fit for this technique.
Steps to perform bubble sort:
- Initially, you have your unsorted array.
2. Start comparing the current element with the next element. If the current element is greater than the next, swap both the elements, else don’t swap and keep moving. Below is the representation of what our array looks like after you traverse the whole array the first time (first pass).
3. As a second pass, you will again traverse the array from start and repeat the same process of swapping the adjacent elements if they are not ordered. Below are the steps representing the second pass in the array,
4. The array has already been sorted, but our algorithm is unaware of whether the sorting is complete. To know it is sorted, the algorithm needs to complete one full pass without any swaps.
Below is the implementation of bubble sort in Java.
//Java Implementationclass Main { public void bubbleSort(int A[]) { int arraySize = A.length; //iterate over the unsorted array, this loop is for the number of passes for (int i = 0; i < arraySize - 1; i++) //iterate over the array of elements for (int j = 0; j < arraySize - i - 1; j++) // do a comparison among the adjacent array elements if (A[j] > A[j + 1]) { //swap the unsorted elements int temp = A[j]; A[j] = A[j + 1]; A[j + 1] = temp; } }}
Time and Space complexities:
The time complexity for this algorithm is:
TC: O(n^2)
SC: O(1)
Insertion sort
The principle behind insertion sort is that one element from the input elements must be consumed during each iteration to determine its correct place or position in the sorted array to which it belongs. You must insert each new element into the proper location in the sorted subarray to the left of it. Think of each new position as the new card the dealer handed you.
Steps to perform insertion sort:
- Consider the following array, currently the elements are not sorted.
2. First Pass
Compare the first two elements of the array, 25 is greater than 24 and are not arranged in ascending order. So, you swap 24 and 25.
For now, 24 is at its correct position.
3. Second Pass
Now, shift to the next two elements and compare them. 25 and 26 seem to be in ascending order, so they are in the correct position for now; hence, there is no need to swap.
4. Third Pass
Shifting forward, the next two elements are 26 and 7 which are not sorted in ascending order, so you need to swap them.
After swapping, you see that 25 and 7 are also not ordered so swap again.
Again, 24 and 7 are not in their correct order, so swap again.
5. Fourth Pass
As you can see 7, 24, and 25 are part of sorted sub-arrays. Now, considering the next two elements 26 and 8, they are not sorted in ascending, so swap them.
Similarly, to put 8 at its correct position, you need to swap 25 and 8, along with 24 and 8. After this, you get your final sorted array and that looks like this,
Below is the implementation of insertion sort in Java.
Implementation:
//Java Implementationclass Main{ public void insertionSort(int A[]){ int arraySize = A.length; for (int i = 1; i < arraySize; i++) { // Start from 1 as arr[0] is always sorted int currElement = A[i]; int j = i - 1; //Elements of arr[0..i-1] that are greater than value should be moved //one position forward from where they are currently. while (j >= 0 && A[j] > currElement) { A[j + 1] = A[j]; j = j - 1; } //placing the current element in the current position. A[j + 1] = currElement; } }}
Time and Space complexities:
The time complexity for this algorithm is:
TC: O(n^2)
SC: O(N)
Quick sort
The divide-and-conquer strategy is the foundation of quick sort. It involves selecting one member as the pivot element and dividing the array in such a way that: All the elements that are smaller than the pivot element are on the left side of the pivot. All items larger than the pivot are found on the right side.
The partition() method in quicksort is the main operation. The goal of partitions is to arrange all elements smaller than element “p” before “p” and all elements greater than “p” after “p” in a sorted array when given an array and element “p” of the array as a pivot. This should all be completed in a straight line.
Let’s first look at the partition algorithm and how it is implemented.
- Consider the following array, for which we will run our partition algorithm. Usually, the rightmost element is considered the pivot element, so here, 50 is our pivot element.
- Starting with the first element, we compare it with the pivot. We don’t make any adjustments because 60 is greater than 50 and go on to element 42.
- Once again compare with the pivot. We swap 42 and 60 because 42 is less than 50.
- We next go on to element 5, which is again less than pivot 50, replacing it with 60.
- Similarly, for the next element 25 which is less than 50, the array becomes 42, 5, 25, 60, 75, 50. Now 75 is greater than pivot 50, hence no changes.
- Finally, we swap our pivot with 60 to bring it to the proper position.
Below is the representation of the steps.
Now you have got your array where all the elements on the left side of pivot 50 are smaller than 50 and the elements present after the pivot element are greater than 50.
Moving on to the next steps,
- Take your left and right subarrays.
- Keep two-pointers low’ and ‘high’ at the extreme ends initially, along with considering your rightmost element as a pivot.
- If the element at ‘low’ is greater than the pivot, swap both the elements and increment your ‘low’.
- Else you can continue.
- These steps will be repeated until your ‘low’ does not become greater than ‘high’.
- Refer to the below representation for the above steps.
In comparison to the merge sort, quicksort is the best method for small inputs. Choose quicksort if you don’t want a steady sort and average performance is more important than worst performance.
Implementation:
class Main { // partition method public int partition(int A[], int low, int high) { // selecting the rightmost element as a pivot int pivot = A[high]; int left = low; int right = high - 1; //iterating until the left index is smaller than the right index while(left <= right){ //increment the left until its smaller than the pivot while(A[left] < pivot){ left++; } //decrement the right until it's greater than the pivot while(A[right] > pivot){ right--; } if(left < right){ //swapping the elements of the left and right index int temp = A[left]; A[left] = array[right]; A[right] = temp; } } // swapping pivot with the element where left and right meet int temp = A[left]; A[left] = A[high]; A[high] = temp; return (left); } public void quickSort(int A[], int low, int high) { if (low < high) { // pivot element is the point at which the array is // partitioned int pivotElement = partition(A, low, high); // calling the quicksort on the left subarray quickSort(A, low, pivotElement - 1); // calling the quicksort on the right subarray quickSort(A, pivotElement + 1, high); } }}
Time and Space complexities:
The time complexity for this algorithm is:
TC: O(NlogN)
SC: O(N)
Merge sort
Merge Sort makes use of the Divide and Conquer algorithm, which divides a problem into many smaller ones, solves each of those separately, and then combines the results.
Let’s have a look at an array of n unsorted integers. Sorting the array is what we’re after.
- The middle of the provided array is initially determined by applying the formula mid=start+(end-start)/2.
- Using the computed midpoint, you divide the array into subarrays. You then divide the array recursively further while continuing to calculate the calculated midway. The fact that a single array element is always sorted should be noted.
- Therefore, you want to divide each element in the array repeatedly until there are only single array items left.
- The items of the array are then put back together to create a sorted array.
- It’s time to join all of our subarrays in sorted order now that they have all been produced.
Let’s see a visual of how the merge sort works:
- In the above diagram, you can see that the array 38,27,43,3,9,82,10 is our unsorted array. As per the steps discussed above, you need to divide this array into two halves.
- Now you have two arrays: 38,27,43,3 and 9,82,10
- Next step is to further divide these two arrays through their mid. These steps will be repeated until you get single elements at the end.
- As you can see, the elements at the end of the diagram are single elements that you got by repeatedly breaking your array into two halves.
- Next step is to merge these single components. The merging is done in such a way that elements are get arranged in a sorted way.
- In the below example, 38 and 27 get merged as 27, 38 (ascending order). In the next level where you have 27, 38 and 3, 43, these elements got merged and got arranged as 3,27,38,43.
- These steps continue until you get your final array as the sorted one.
Below is the implementation of Merge Sort in Java.
//Java Implementation// Divide the array into two subarrays, sort them and merge them static void mergeSort(int sortedArray[], int start, int end) { if (start < end) { int mid = (start + end) / 2; //running merge sort from start to mid mergeSort(sortedArray, start, mid); //running merge sort from mid to end mergeSort(sortedArray, mid + 1, end); // Merging the sorted subarrays merge(sortedArray, start, mid, end); } } // Merge two subarrays arr1 and arr2 into sorted static void merge(int sortedArray[], int start, int mid, int end) { int array1 = mid - start + 1; int array2 = end - mid; int arr1[] = new int[array1]; int arr2[] = new int[array2]; for (int i = 0; i < array1; i++) arr1[i] = sortedArray[start + i]; for (int j = 0; j < array2; j++) arr2[j] = sortedArray[mid + 1 + j]; int i, j, k; i = 0; j = 0; k = start; //Choose the largest element from between arr1 and arr2 and insert it in the appropriate //spot at sorted[start until we reach the end of either arr1 or arr2 .end] while (i < array1 && j < array2) { if (arr1[i] <= arr2[j]) { sortedArray[k] = arr1[i]; i++; } else { sortedArray[k] = arr2[j]; j++; } k++; } //At last, the remaining elements are put in a sorted way. while (i < array1) { sortedArray[k] = arr1[i]; i++; k++; } while (j < array2) { sortedArray[k] = arr2[j]; j++; k++; } }
Time and Space complexities:
The time complexity for this algorithm is:
TC: O(NlogN)
SC: O(N)
Conclusion
In this article, we have briefly discussed different sorting algorithms in Java such as: Merge Sort, Insertion Sort, Quick Sort etc.
Hope you will like the article.
Keep Learning!!
Keep Sharing!!
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
Comments
(1)
r
a month ago
Report Abuse
Reply to raghavendar Kumaran