Different Sorting Algorithms in Java and Step by Step Implementation

A sorting algorithm is an algorithm used to rearrange any list of items either in ascending or descending order. The algorithm uses a comparison operator to compare the elements in order to know which element is lesser or greater.

For eg,

Input : 5 3 8 4 2 7

Output : 2 3 4 5 7 8

Sorting algorithms are categorized into various types based on their time complexity.

The most popular types of sorting algorithms are,

  1. Bubble Sort
  2. Selection Sort
  3. Insertion Sort
  4. Quick Sort
  5. Merge Sort, etc

Normally sorting algorithms uses different types of approaches.

Sorting Boxes

Brute Force Approach

The most common and easy approach is Brute force technique. The Brute force approach uses straight forward pattern which will not be bothering about the time complexity at all. The algorithm will simply iterates through all the elements and compare to their adjacent element. If the algorithm finds that the elements adjacent to each other are in wrong order, then it will swap it.

Example : Bubble sort, insertion sort, selection sort, etc.

Divide and Conquer Approach

The approach used to split the bigger problem into multiple smaller problems and solve them as a smaller one. Then merges back to the original problem. The approach will finishes the sorting in a time efficient way (i.e) the time complexity of these algorithms will be lesser comparing to the Brute force approach. The disadvantage of this approach would be very tedious to implement such algorithm and also space complexity would be higher than the other approach. The algorithm will requires additional space to solve the problem instead of solving it inline (i.e) within the allocated space for the problem already.

Example : Quick sort, merge sort, etc

Bubble Sort

Bubble sort is the easiest and simplest sorting algorithm which iterates through each element and swaps with its adjesent element if they were in wrong order. Bubble sort uses the Brute force approach to sort the elements.

The iterating of elements will happen for multiple passes with each time ends with one element less (i.e 1st pass ends with nth element and 2nd pass will ends with (n-1)th element and so on).

The algorithm will move the bigger elements towards the last of the list, where the other brute force algorithms will pull the smallest number towards starting of the array. There are many types of sorting algorithms which performs the sorting in same time complexity as the Bubble sort but among them, the Bubble sort algorithm will be very much easy to implement.

For example,

Consider the input,

Pass #1

Iteration #1

Iteration #2

Iteration #3

Iteration #4

Iteration #5

word image 57303 1 - GeeksProgramming

Pass #2

Iteration #1

Iteration #2

Iteration #3

Iteration #4

Iteration #5

word image 57303 2 - GeeksProgramming

Similarly, the algorithm will loop until 5 Passes irrespective of whether the array is already sorted or not.

Time complexity

Best Case

The best case time complexity can be determined by providing a list of elements that are already sorted.

Eg: 1,2,3,4,5

The algorithm will take N x N number of iterations with zero swapping operation as there are no elements in the wrong order.

Time Complexity: O(N2)

Average/Worst Case

The average case time complexity can be determined by providing a list of elements that are partially sorted, likewise the worst case time complexity can be determined by providing a list of elements that are exactly in reverse order.

The algorithm will take N x N number of iterations with at least N swapping operation as there are possibly N elements in the wrong order.

Time Complexity: O(N2)

Algorithm

import java.io.*;

class BubbleSortSample

{

public static void bubbleSort(int arr[])

{

int temp, n = arr.length;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n - i; j++)

{

if (arr[j] > arr[j + 1])

{

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

}

public static void main(String args[])

{

int arr[] = { 5, 3, 4, 8, 7, 6, 9 };

bubbleSort(arr);

for (i = 0; i < arr.length; i++) {

System.out.print(arr[i] + " ");

}

}

}

Output:

3, 4, 5, 6, 7, 8, 9

Implementation

Steps #1 Download and install the latest version of the JDK from the following link which provides the development environment to develop the Java code.

https://www.oracle.com/java/technologies/downloads/

Steps #2 Create a new java file with any preferred name with the extension *.java.

Steps #3 Create a class with the same name as the file name using the following syntax.

class BubbleSortSample

{

}

Steps #4 Create a sorting method that takes one argument with an integer array

public static void bubbleSort(int arr[])

{

}

Steps #5 Initialize two integer variables, one for a temporary variable which will be used while swapping and the other variable that holds the length of the array.

int temp, n = arr.length;

Steps #6 Create two loops, one for different passes and another for different iterations. The second loop should have a counter that should decrement one per pass (i.e N – I where N is a number of elements and i is the first loops counter variable.

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n - i; j++)

{

}

}

Steps #7 Check if the current element (i.e second for loop counter position) and the immediate next element. If they are in the wrong order (the first element is greater than the second element) then we should swap those elements.

if (arr[j] > arr[j + 1])

{

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

Steps #8 The swapping of the element involves copying the first element into the temporary variable that we have created during Step #5 and the assign the second element to the first element. Then copy the temporary variable back into the second element.

Steps #9 Next step is to test the sorting method that we have implemented. Initialize an array of elements with some numbers randomly in the wrong order.

int arr[] = { 5, 3, 4, 8, 7, 6, 9 };

Steps #10 Call the bubble sort method with the array we created as a parameter. The method doesn`t need the sorted elements instead it will modify the array that we sent itself.

bubbleSort(arr);

Steps #10 Iterate the elements and print the sorted elements.

for (i = 0; i < arr.length; i++) {

System.out.print(arr[i] + " ");

}

The output of the program will print the array of elements in the correct order.

Quick Sort

The quick sort algorithm is one of the fastest algorithms which uses the Divide and Conquer algorithm. The approach divides the full list into smaller lists and sorts each and then merges them back into the same bigger list.

The quick sort used to choose one element as the pivot element and divide the array into two sub-arrays and sort all the elements that are less than the pivot element will be copied into the left sub-array and the elements that are greater than the pivot element will be copied into the right sub-array. Then these two arrays will be recursively sorted using the same approach until the subarray size becomes one.

word image 57303 3 - GeeksProgramming

In the first pass, take the element “8” as the pivot element and divide a left sub array with all elements less than “8”. The left array will consist of “3, 4, 2” elements. Similarly, we should divide a right sub-array with all elements greater than “8” and also includes “8” into the right array.

In the second pass, the left array and right arrays are processed individually with the same approach. For the left array, the element “2” will be taken as the pivot element and split a left sub-array with just “2” because there are no elements that are less than the pivot element. The right array will contain “3, 4” which are greater than the pivot element “2”.

Within the same second pass, in the right subarray, the element “8” will be taken as the pivot element. The left sub-array will consist of “5, 7” elements and the right sub-array will consist of only “8”.

Now during the third pass, “2” cannot be split further, so the sub-array “3, 4” will be split by considering element “4” as the pivot element. For the fourth pass, we will end up with “3” and “4” as left subarray and right subarray respectively.

Similarly, the sub-array “5, 7” can be split further by “5” and left subarray and “7” as the right subarray with the assumption of “7” as the pivot element. The right subarray of the third pass “8” cannot be split further.

Now the algorithm will now rearrange all the sub-arrays into one big array. Now the algorithm will not need to compare the elements as they are already sorted properly.

 

Best Java Homework Help service – Hire Java Expert online to help with your Java Assignments.

Time complexity

Best Case

The best case time complexity can be determined by providing a list of elements that are already sorted.

Eg: 1,2,3,4,5

The algorithm will take 5 as the pivot element and create a left sub-array with “1,2,3,4” and a right sub-array with “5”. The right sub-array cannot be split further. The second pass will take “4” as the pivot element and create a left sub-array with “1, 2, 3” and the right sub-array with “4”. The algorithm will similarly split the left sub array further until the first element. So the algorithm will not need to do any swapping operations but loops through N times the logarithmic of N.

Time Complexity: O(N log (N) )

Worst Case

The average case time complexity can be determined by providing a list of elements that are partially sorted, likewise the worst case time complexity can be determined by providing a list of elements that are exactly in reverse order.

The algorithm will take N number of passes with N times splitting the sub-arrays.

Time Complexity: O(N2)

Algorithm

import java.io.*;

class QuickSortAlgorithm{

public static int partition(int[] arr, int start, int end)

{

int temp, pivot = arr[end];

for(int j = start, i = start - 1; j < end; j++)

{

if (arr[j] < pivot)

{

i++;

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

temp = arr[i + 1];

arr[i + 1] = arr[end];

arr[end] = temp;

return (i + 1);

}

public static void quickSort(int[] arr, int start, int end)

{

if (start < end)

{

int pivot = partition(arr, start, end);

quickSort(arr, start, pivot - 1);

quickSort(arr, pivot + 1, end);

}

}

public static void main(String args[])

{

int arr[] = { 5, 3, 4, 8, 7, 6, 9 };

quickSort (arr, 0, arr.length);

for (i = 0; i < arr.length; i++) {

System.out.print(arr[i] + " ");

}

}

}

The output will be “3, 4, 5, 6, 7, 8, 9”.

Implementation

Steps #1 Download and install the latest version of the JDK from the following link which provides the development environment to develop the Java code.

https://www.oracle.com/java/technologies/downloads/

Steps #2 Create a new java file with any preferred name with the extension *.java.

Steps #3 Create a class with the same name as the file name using the following syntax.

class QuickSortAlgorithm

{

}

Steps #4 Create a partitioning method that takes three arguments with an integer array, starting and ending index of the array.

public static int partition(int[] arr, int start, int end)

{

}

Steps #5 Initialize two integer variables, one for a temporary variable which will be used while swapping and the other variable that holds the pivot element of the array.

int temp, pivot = arr[end];

Steps #6 Create a for loop with two counter variables one pointing to the start element and the other pointing to the left sub-array index.

for(int j = start, i = start - 1; j < end; j++)

Steps #7 Check if the element pointing at the index j is smaller than the pivot element, then increment the second pointer by one and swap both the element pointing at index i and index j.

if (arr[j] < pivot)

{

i++;

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

Steps #7 Once the loop exits, swap the elements pointing (i+1) index that is the end of the pointer of the left sub-arrays that holds elements smaller than the pivot element. The (i+1) index will now contain the pivot element.

temp = arr[i + 1];

arr[i + 1] = arr[end];

arr[end] = temp;

Steps #8 The method should return the pivot element index (i.e) “i + 1”.

return (i + 1);

Steps #9 Create a partitioning method that takes three arguments with an integer array, starting and ending index of the array.

public static void quickSort(int[] arr, int start, int end)

{

}

Steps #10 Check if the start index is less than the end index, otherwise do nothing.

if (start < end)

{

}

Steps #11 Initialize an integer variable that points toward the pivot element index which is been returning from the partition method that we have created in step #4.

int pivot = partition(arr, start, end);

Steps #12 Call the same method quicksort for two partitions (i.e from a start index to one element before pivot as left sub-array and starting from one element next to pivot element to end element as right sub-array.

quickSort(arr, start, pivot - 1);

quickSort(arr, pivot + 1, end);

Steps #13 Create two for loops, one for different passes and another for different iterations. The second for loop should have a counter that should decrement one per pass (i.e N – i where N is a number of elements and i is the first loops counter variable.

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n - i; j++)

{

}

}

Steps #14 Check if the current element (i.e second for loop counter position) and the immediate next element. If they are in the wrong order (the first element is greater than the second element) then we should swap those elements.

if (arr[j] > arr[j + 1])

{

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

Steps #15 The swapping of the element involves copying the first element into the temporary variable that we have created during Step #5 and the assign the second element to first element. Then copy the temporary variable back into the second element.

Steps #16 Next step is to test the sorting method that we have implemented. Initialize an array of elements with some numbers in randomly in wrong order.

int arr[] = { 5, 3, 4, 8, 7, 6, 9 };

Steps #17 Call the bubble sort method with the array we created as parameter. The method don`t need to the sorted elements instead it will modify the array that we sent itself.

quickSort(arr);

Steps #18 Iterate the elements and print the sorted elements.

for (i = 0; i < arr.length; i++) {

System.out.print(arr[i] + " ");

}

The output of the program will print the array of elements in the correct order.

Coding algorithms can be fun and all but sometimes it may get tricky. In case you need help with algorithms or java homework help, contact us now and our team of expert java programmers will assist you.

Leave a Comment

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

Scroll to Top