Implementing Various Sorting Algorithms

Sorting is a fundamental operation in computer science that involves arranging a collection of elements in a specific order. There are several sorting algorithms available, each with its own advantages and disadvantages. In this article, we will explore the implementation of various sorting algorithms using Java.

Selection Sort

Selection sort is a simple comparison-based sorting algorithm. It works by dividing the input array into two parts: the sorted part at the left end and the unsorted part at the right end. In each iteration, the smallest element from the unsorted part is selected and swapped with the leftmost element of the unsorted part.

public static 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;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Insertion Sort

Insertion sort is another simple comparison-based sorting algorithm. It works by building a sorted portion of the array, one element at a time. In each iteration, an element from the unsorted portion is picked and inserted into its correct position in the sorted portion.

public static 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--;
        }
        arr[j + 1] = key;
    }
}

Merge Sort

Merge sort is a divide-and-conquer sorting algorithm. It works by recursively dividing the input array into two halves, sorting them, and then merging them back together. It achieves good performance by taking advantage of the efficiency of merging two sorted arrays.

public static void mergeSort(int[] arr, int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

public static void merge(int[] arr, int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;

    int[] left = new int[n1];
    int[] right = new int[n2];

    for (int i = 0; i < n1; i++) {
        left[i] = arr[start + i];
    }
    for (int i = 0; i < n2; i++) {
        right[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = start;

    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

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

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

Quicksort

Quicksort is another divide-and-conquer sorting algorithm. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

public 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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

These are just a few examples of sorting algorithms implemented in Java. Each algorithm has its own strengths and weaknesses, and understanding them can greatly enhance your competitive programming skills. Experiment with different algorithms and see how they perform on different types of inputs. Happy coding!