Created
July 1, 2025 06:13
-
-
Save HazemKhaled/e911733424d341103bcab8e9f8878a7b to your computer and use it in GitHub Desktop.
Revisions
-
HazemKhaled created this gist
Jul 1, 2025 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,229 @@ import java.util.Arrays; import java.util.Random; /** * SortAlgorithms - A comprehensive implementation and comparison of sorting algorithms * * This code demonstrates two fundamental divide-and-conquer sorting algorithms: * - Merge Sort: Stable, O(n log n) time complexity, O(n) space complexity * - Quick Sort: In-place, average O(n log n), worst-case O(n^2) time complexity * * Both algorithms are benchmarked against different dataset sizes to analyze performance. */ public class SortAlgorithms { /** * Merge Sort - A stable, divide-and-conquer sorting algorithm * * Time Complexity: O(n log n) in all cases (best, average, worst) * Space Complexity: O(n) due to temporary arrays * Stability: Stable (maintains relative order of equal elements) * * Algorithm Steps: * 1. Divide the array into two halves * 2. Recursively sort both halves * 3. Merge the sorted halves back together * * @param array The integer array to be sorted (modified in-place) */ public static void mergeSort(int[] array) { // Base case: arrays with 0 or 1 element are already sorted if (array.length > 1) { // Find the middle point to divide the array into two halves int mid = array.length / 2; // Create left and right subarrays int[] left = Arrays.copyOfRange(array, 0, mid); int[] right = Arrays.copyOfRange(array, mid, array.length); // Recursively sort both halves mergeSort(left); mergeSort(right); // Merge the sorted halves back into the original array merge(array, left, right); } } /** * Merge - Helper method to combine two sorted arrays into one sorted array * * This method performs the "conquer" step of merge sort by merging two * already sorted subarrays into a single sorted array. * * Time Complexity: O(n) where n is the total number of elements * Space Complexity: O(1) as it uses the provided arrays * * @param array The destination array where merged result will be stored * @param left The left sorted subarray * @param right The right sorted subarray */ private static void merge(int[] array, int[] left, int[] right) { int i = 0, j = 0, k = 0; // Pointers for left, right, and result arrays // Compare elements from both arrays and merge in sorted order while (i < left.length && j < right.length) { // Choose the smaller element and advance the corresponding pointer array[k++] = (left[i] <= right[j]) ? left[i++] : right[j++]; } // Copy any remaining elements from the left array while (i < left.length) array[k++] = left[i++]; // Copy any remaining elements from the right array while (j < right.length) array[k++] = right[j++]; } /** * Quick Sort - An efficient, in-place, divide-and-conquer sorting algorithm * * Time Complexity: * - Best/Average case: O(n log n) * - Worst case: O(n^2) when pivot is always the smallest or largest element * Space Complexity: O(log n) due to recursion stack * Stability: Not stable (may change relative order of equal elements) * * Algorithm Steps: * 1. Choose a pivot element (here: last element) * 2. Partition array so elements <= pivot are on left, > pivot on right * 3. Recursively apply quick sort to left and right partitions * * @param array The integer array to be sorted * @param low Starting index of the portion to sort * @param high Ending index of the portion to sort */ public static void quickSort(int[] array, int low, int high) { // Base case: if low >= high, the subarray has 0 or 1 element (already sorted) if (low < high) { // Partition the array and get the pivot's final position int pivotIndex = partition(array, low, high); // Recursively sort elements before the pivot quickSort(array, low, pivotIndex - 1); // Recursively sort elements after the pivot quickSort(array, pivotIndex + 1, high); } } /** * Partition - Helper method for Quick Sort using Lomuto partition scheme * * This method rearranges the array such that: * - All elements <= pivot are moved to the left side * - All elements > pivot are moved to the right side * - The pivot is placed in its correct final position * * Time Complexity: O(n) where n is the number of elements in the range * Space Complexity: O(1) - in-place partitioning * * @param array The array to partition * @param low Starting index of the range to partition * @param high Ending index of the range to partition (pivot element) * @return The final index position of the pivot element */ private static int partition(int[] array, int low, int high) { int pivot = array[high]; // Choose the last element as pivot int i = low - 1; // Index of the smaller element (indicates right position of pivot) // Traverse through all elements except the pivot for (int j = low; j < high; j++) { // If current element is smaller than or equal to pivot if (array[j] <= pivot) { i++; // Increment index of smaller element // Swap elements to move smaller element to the left side int temp = array[i]; array[i] = array[j]; array[j] = temp; } } // Place pivot in its correct position by swapping with element at (i + 1) int temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; return i + 1; // Return the partition index (pivot's final position) } /** * Main method for testing and benchmarking the sorting algorithms * * This method: * 1. Tests both algorithms on datasets of different sizes * 2. Measures execution time in nanoseconds for performance comparison * 3. Uses random integers between 0-999 for realistic testing * 4. Ensures fair comparison by using identical datasets for both algorithms * * Performance Notes: * - Merge Sort: Consistent O(n log n) performance regardless of data distribution * - Quick Sort: Generally faster than Merge Sort due to better cache locality, * but performance can degrade to O(n^2) with poor pivot selection * * @param args Command line arguments (not used) */ public static void main(String[] args) { // Test with different dataset sizes to observe scaling behavior int[] sizes = {10, 50, 100}; Random rand = new Random(); System.out.println("=== Sorting Algorithms Performance Comparison ===\n"); for (int size : sizes) { // Generate random dataset with integers between 0-999 int[] original = rand.ints(size, 0, 1000).toArray(); // Test Merge Sort - create a copy to ensure fair comparison int[] mergeInput = Arrays.copyOf(original, original.length); long startMerge = System.nanoTime(); mergeSort(mergeInput); long endMerge = System.nanoTime(); // Verify the array is sorted (optional validation) boolean mergeSorted = isSorted(mergeInput); // Test Quick Sort - use the same original dataset int[] quickInput = Arrays.copyOf(original, original.length); long startQuick = System.nanoTime(); quickSort(quickInput, 0, quickInput.length - 1); long endQuick = System.nanoTime(); // Verify the array is sorted (optional validation) boolean quickSorted = isSorted(quickInput); // Output detailed results with performance metrics System.out.printf("Dataset Size: %d elements\n", size); System.out.printf("Merge Sort: %d ns %s\n", (endMerge - startMerge), mergeSorted ? "[OK]" : "[ERROR: Not sorted!]"); System.out.printf("Quick Sort: %d ns %s\n", (endQuick - startQuick), quickSorted ? "[OK]" : "[ERROR: Not sorted!]"); // Calculate and display relative performance double ratio = (double)(endQuick - startQuick) / (endMerge - startMerge); System.out.printf("Quick/Merge Ratio: %.2fx %s\n\n", ratio, ratio < 1.0 ? "(Quick Sort faster)" : "(Merge Sort faster)"); } } /** * Helper method to verify if an array is sorted in ascending order * * This method provides validation that the sorting algorithms worked correctly * by checking if each element is less than or equal to the next element. * * @param array The array to check * @return true if the array is sorted in ascending order, false otherwise */ private static boolean isSorted(int[] array) { for (int i = 1; i < array.length; i++) { if (array[i] < array[i - 1]) { return false; // Found an element that breaks the sorted order } } return true; // All elements are in correct order } }