PROGRAM_DETAILS.md

PROGRAM DETAILS

This document provides a comprehensive overview of various Java coding programs, outlining their purpose, core concepts, algorithms, and code examples.

1. Bubble Sort

Purpose: Sorting an array in ascending order.

Concepts: Iterative algorithm, comparison-based sorting.

Algorithm:

1. Start from the first element of the array.
2. Compare the current element with the next.
3. Swap if the current element is greater than the next.
4. Repeat until the array is sorted.

Code Example:

public class BubbleSort {
    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+1] and arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

2. Quick Sort

Purpose: Efficiently sorting an array.

Concepts: Divide and conquer, recursive algorithm.

Algorithm:

1. Choose a pivot element from the array.
2. Partition the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
3. Recursively apply the above steps to the sub-arrays.

Code Example:

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1); // index of smaller element

        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] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
}

3. Merge Sort

Purpose: Sorting an array with guaranteed O(n log n) complexity.

Concepts: Divide and conquer, recursive sorting method.

Algorithm:

1. Divide the unsorted list into two approximately equal halves.
2. Recursively sort both sub-lists.
3. Merge the sorted sub-lists into a single sorted list.

Code Example:

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

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

        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[mid + 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++;
        }
    }
}

Conclusion

The above programs represent fundamental algorithms widely used in Java programming. Each serves a unique purpose and enhances the understanding of data structures and algorithms in software development.