Different Sorting Algorithms in Java and Step by Step Implementation

Sorting algorithm is an algorithm used to rearrange any list of items either in ascending or descending order. The algorithm uses comparison operator to compare the elements in order to know that 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

Pass #2

Iteration #1

Iteration #2

Iteration #3

Iteration #4

Iteration #5

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 which 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 is no elements are in wrong order.

Time Complexity : O(N2)

Average/Worst Case

The average case time complexity can be determined by providing a list of elements which are partially sorted, likewise the worst case time complexity can be determined by providing a list of elemnts which 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 are in 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 variable, one for 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 for loops, one for different different passes and another for different iterations. The second for loop should have counter that should decrement one per pass (i.e N – i where N is number of elements and i is 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 wrong order (first element is greater than 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 into 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 in randomly in wrong order.

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

Steps #10 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.

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 correct order.

Quick Sort

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

The quick sort used to choose one element as 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 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 sub array size becomes one.

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

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 is no elements that are less than the pivot element. The right array will contains “3, 4” which are greater than the pivot element “2”.

Within the same second pass, the right sub array, the element “8” will be taken as pivot element. The left sub array will consists of “5 , 7” elements and the right sub array will consists 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 pivot element. For the forth pass, we will end up with “3” and “4” as left sub array and right sub array respectively.

Similarly the sub array “5, 7” can be split further by “5” and left sub array and “7” as right sub array with the assumption of “7” as the pivot element. The right sub array of 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 which 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 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 splits 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 which are partially sorted, likewise the worst case time complexity can be determined by providing a list of elemnts which 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 variable, one for 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 end of the pointer of the left sub arrays that holds elements smaller than the pivot element. The (i+1) index will now contains 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, other wise do nothing.

if (start < end)

{

}

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

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

Steps #12 Call the same method quicksort for two partitions (i.e from 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 different passes and another for different iterations. The second for loop should have counter that should decrement one per pass (i.e N – i where N is number of elements and i is 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 wrong order (first element is greater than 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 into 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 correct order.

Leave a reply