Introduction

Sorting algorithms are fundamental algorithms used to reorder elements in a list or array into a specific order (ascending or descending). In this tutorial, we will implement three popular sorting algorithms in Java:

• Bubble Sort
• Quick Sort
• Merge Sort

The objective of this tutorial is to understand the working of these sorting algorithms and compare their efficiency based on time complexity, performance, and ease of implementation.

Java Code: Sorting Algorithms

        public class SortingAlgorithms {

            // Bubble Sort Implementation
            public static 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] and arr[j+1]
                            int temp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = temp;
                        }
                    }
                }
            }

            // Quick Sort Implementation
            public static void quickSort(int[] arr, int low, int high) {
                if (low < high) {
                    // Partition the array
                    int pi = partition(arr, low, high);
                    quickSort(arr, low, pi - 1);
                    quickSort(arr, pi + 1, high);
                }
            }

            private static int partition(int[] arr, int low, int high) {
                int pivot = arr[high];
                int i = low - 1;
                for (int j = low; j < high; j++) {
                    if (arr[j] <= pivot) {
                        i++;
                        // Swap arr[i] and arr[j]
                        int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
                // Swap arr[i+1] and arr[high] (pivot)
                int temp = arr[i + 1];
                arr[i + 1] = arr[high];
                arr[high] = temp;
                return i + 1;
            }

            // Merge Sort Implementation
            public static void mergeSort(int[] arr, int left, int right) {
                if (left < right) {
                    int middle = (left + right) / 2;
                    mergeSort(arr, left, middle);
                    mergeSort(arr, middle + 1, right);
                    merge(arr, left, middle, right);
                }
            }

            private static void merge(int[] arr, int left, int middle, int right) {
                int n1 = middle - left + 1;
                int n2 = right - middle;

                int[] L = new int[n1];
                int[] R = new int[n2];

                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];

                int i = 0, j = 0;
                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++;
                }

                while (i < n1) {
                    arr[k] = L[i];
                    i++;
                    k++;
                }

                while (j < n2) {
                    arr[k] = R[j];
                    j++;
                    k++;
                }
            }

            // Main Method for Testing Sorting Algorithms
            public static void main(String[] args) {
                int[] arrBubble = {64, 34, 25, 12, 22, 11, 90};
                System.out.println("Original Array (Bubble Sort):");
                printArray(arrBubble);
                bubbleSort(arrBubble);
                System.out.println("Sorted Array (Bubble Sort):");
                printArray(arrBubble);

                int[] arrQuick = {64, 34, 25, 12, 22, 11, 90};
                System.out.println("\nOriginal Array (Quick Sort):");
                printArray(arrQuick);
                quickSort(arrQuick, 0, arrQuick.length - 1);
                System.out.println("Sorted Array (Quick Sort):");
                printArray(arrQuick);

                int[] arrMerge = {64, 34, 25, 12, 22, 11, 90};
                System.out.println("\nOriginal Array (Merge Sort):");
                printArray(arrMerge);
                mergeSort(arrMerge, 0, arrMerge.length - 1);
                System.out.println("Sorted Array (Merge Sort):");
                printArray(arrMerge);
            }

            // Utility Method to Print Arrays
            public static void printArray(int[] arr) {
                for (int i : arr) {
                    System.out.print(i + " ");
                }
                System.out.println();
            }
        }
        

Explanation of the Program

The program implements three sorting algorithms: Bubble Sort, Quick Sort, and Merge Sort.

• Bubble Sort: This algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order. It continues the process for every element in the list until the list is sorted.
• Quick Sort: This algorithm selects a ‘pivot’ element and partitions the list around the pivot. It then recursively sorts the sublists on either side of the pivot.
• Merge Sort: This algorithm divides the array into two halves, recursively sorts each half, and then merges the sorted halves together.

The main() method tests these sorting algorithms on a sample array and prints the sorted arrays to the console.

How to Run the Program

1. Ensure you have the latest version of Java installed on your system. You can download it from here.
2. Save the code to a file named SortingAlgorithms.java.
3. Open your terminal or command prompt and navigate to the directory where the file is saved.
4. Compile the Java code by running the following command:

   javac SortingAlgorithms.java

5. Run the compiled Java program using the following command:

   java SortingAlgorithms

6. The program will output the original and sorted arrays for each algorithm to the console.