Sorting in Java - Algorithms and Implementation

Sorting in Java, or in any programming language, refers to the process of arranging data in a certain order, usually either in ascending or descending order. There are many algorithms in Java for sorting data, such as Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, etc. Each algorithm has its own pros and cons, and can be selected based on the requirements of the task.

Sorting is important in Java for several reasons:

Efficiency: Sorted data can greatly increase the speed of data retrieval. For example, if data is sorted, binary search can be used to find elements in logarithmic time complexity as compared to linear search in unsorted data. Data Analysis: It can be easier to see patterns in data when it is sorted. For instance, finding the median value of a data set is far simpler when the set is sorted.
Aesthetics and Usability: When presenting data to users, it is often best to present it in a sorted format. This allows users to more easily understand and interpret the data. Prerequisite for certain algorithms: Some algorithms (like finding a range of values, identifying duplicates, etc.) require the input data to be sorted initially.

In Java, the Collections.sort() and Arrays.sort() methods are typically used for sorting collections and arrays, respectively, including . Java’s sorting methods use a modified version of Merge Sort, known as TimSort, which is highly efficient for many kinds of data sets.

Selection Sorting In Java

Selection sort is a simple comparison-based algorithm. It works by dividing the array into a sorted and an unsorted region. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted region and moves it to the sorted region.

Time Complexity: O(n^2)

Steps:

Find the smallest element in the array and swap it with the first element.

Let’s take an array {5, 2, 9, 1, 5, 6}
The smallest element is ‘1’, swap it with the first element. Now our array is {1, 2, 9, 5, 5, 6}

Find the second smallest element (smallest in the subarray starting from the second element) and swap it with the second element.

The smallest element in the remaining array is ‘2’, which is already in the correct position. So, no swap is needed.

Repeat the process for the rest of the array until the entire array is sorted.

Find the smallest element in the subarray from index 2 to 5. It is ‘5’, which is not in its correct position. So, we swap ‘9’ and ‘5’. Now our array is {1, 2, 5, 9, 5, 6}.
Continue the process until the array is completely sorted, i.e., {1, 2, 5, 5, 6, 9}.

Here’s an example of Selection Sort in Java:

void selectionSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        // Swap the found minimum element with the first element of unsorted part
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Insertion Sorting In Java

Insertion sort works similarly to the way people sort playing cards in their hands. It works by dividing the array into a sorted and an unsorted region. The algorithm takes one element from the unsorted region and inserts it into its correct position in the sorted region.

Time Complexity: O(n^2)

Steps:

Start with the second element (assume the first element is sorted).

Let’s take an array {5, 2, 9, 1, 5, 6}

Here, ‘5’ is considered as the sorted part.

Pick the current element ‘2’ and compare it with all elements in the sorted subarray (elements to the left of the current element).

‘2’ is less than ‘5’, so move ‘5’ to the right and insert ‘2’ at the first position.

Repeat steps 2-3 until the entire array is sorted.

Pick ‘9’, it is larger than all the elements in the sorted part, so leave it.

Pick ‘1’, it is smaller than all the elements in the sorted part, so move all the elements to the right and insert ‘1’ at the first position.

Repeat the process until the array is sorted.

Here’s an example of Insertion Sort in Java:

void insertionSort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Bubble Sorting In Java

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Time Complexity: O(n^2)

Steps:

Compare the first two elements of the array {5, 2, 9, 1, 5, 6}. If they are in the wrong order, swap them.

‘5’ is greater than ‘2’, so swap them. Now, the array becomes {2, 5, 9, 1, 5, 6}.

Move to the next pair of elements, compare them and swap if necessary.

‘5’ is less than ‘9’, no swap needed.

Continue this process for the entire array.

The array after the first pass is {2, 5, 1, 5, 6, 9}

Repeat the above steps for the array until no swaps are needed, indicating that the array is sorted.

Here’s an example of Bubble Sort in Java:

void bubbleSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                // swap arr[j+1] and arr[j]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

Merge Sorting In Java

Merge sort is a divide-and-conquer algorithm that divides the unsorted list into n sublists, each containing one element (a list of one element is considered sorted), then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining.

Time Complexity: O(n log n)

Steps:

If the array has only one element, it’s already sorted.

Let’s take an array {38, 27, 43, 3, 9, 82, 10}
The array has more than one element, so we need to divide it.

Divide the array into two halves.

{38, 27, 43, 3} and {9, 82, 10}

Recursively sort each half.

Sort the first half {38, 27, 43, 3} – this will further be divided into {38, 27} and {43, 3} and so on.
Similarly, sort the second half.

Merge the sorted halves into a sorted whole.

Once the two halves are sorted, merge them in such a way that the elements in the merged array are in order.

Here’s an example of Merge Sort in Java:

void merge(int arr[], int left, int middle, int right) {
    // Find sizes of two subarrays to be merged
    int n1 = middle - left + 1;
    int n2 = right - middle;

    /* Create temp arrays */
    int L[] = new int[n1];
    int R[] = new int[n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[left + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[middle + 1+ j];

    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarray array
    int k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Main function that sorts arr[left..right] using merge()
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // Find the middle point
        int middle = (left+right)/2;

        // Sort first and second halves
        mergeSort(arr, left, middle);
        mergeSort(arr , middle+1, right);

        // Merge the sorted halves
        merge(arr, left, middle, right);
    }
}

Array.sort() In Java

The Array.sort() function in Java utilizes a Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

Here’s an example of using Array.sort():

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] array = {9, 14, 3, 2, 43, 11, 58, 22};

    System.out.println("Before Sorting : ");
    System.out.println(Arrays.toString(array));

    Arrays.sort(array);

    System.out.println("After Sorting : ");
    System.out.println(Arrays.toString(array));
  }
}

Conclusion

Understanding sorting algorithms is crucial as sorting is a commonly used operation in programming. The algorithm used can have a significant effect on the performance of your application. In future posts, we will discuss more complex and efficient sorting algorithms and their implementation in Java. Stay tuned!.