kristofer / SortingExamples.java

import java.util.Arrays; import java.util.Scanner; public class SortingExamples { public static void main(String[] args) { Scanner input = new Scanner(System.in); // Input array from the user System.out.print("Enter the number of elements in the array: "); int n = input.nextInt(); int[] arr = new int[n]; System.out.println("Enter the elements of the array:"); for (int i = 0; i < n; i++) { arr[i] = input.nextInt(); } // Choose a sorting algorithm System.out.println("\nChoose a sorting algorithm (1-10):"); System.out.println("1- Selection sort"); System.out.println("2- Bubble sort"); System.out.println("3- Insertion sort"); System.out.println("4- Merge sort"); System.out.println("5- Quick sort"); System.out.println("6- Heap sort"); System.out.println("7- Counting sort"); System.out.println("8- Radix sort"); System.out.println("9- Bucket Sort"); System.out.println("10- Shell Sort"); System.out.print("Enter your choice: "); int choice = input.nextInt(); switch (choice) { case 1: selectionSort(arr); break; case 2: bubbleSort(arr); break; case 3: insertionSort(arr); break; case 4: mergeSort(arr); break; case 5: quickSort(arr, 0, n - 1); break; case 6: heapSort(arr); break; case 7: countingSort(arr); break; case 8: radixSort(arr); break; case 9: bucketSort(arr); break; case 10: shellSort(arr); break; default: System.out.println("Invalid choice. No sorting performed."); } // Print the sorted array System.out.println("Sorted array: " + Arrays.toString(arr)); } // Selection Sort 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; } } // Bubble Sort public static void bubbleSort(int[] arr) { int n = arr.length; boolean swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } if (!swapped) { break; } } } // Insertion Sort 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 public static void mergeSort(int[] arr) { mergeSort(arr, 0, arr.length - 1); } private 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); } } private 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 i = 0; i < n2; i++) { R[i] = arr[mid + 1 + i]; } int i = 0, j = 0, 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++; } } // Quick Sort 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); } } 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++; 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; } // Heap Sort public static void heapSort(int[] arr) { int n = arr.length; for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } for (int i = n - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } private static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } // Counting Sort public static void countingSort(int[] arr) { int n = arr.length; int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); int range = max - min + 1; int[] count = new int[range]; int[] output = new int[n]; for (int i = 0; i < n; i++) { count[arr[i] - min]++; } for (int i = 1; i < range; i++) { count[i] += count[i - 1]; } for (int i = n - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } for (int i = 0; i < n; i++) { arr[i] = output[i]; } } // Radix Sort public static void radixSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); for (int exp = 1; max / exp > 0; exp *= 10) { countingSortByDigit(arr, exp); } } private static void countingSortByDigit(int[] arr, int exp) { int n = arr.length; int[] output = new int[n]; int[] count = new int[10]; Arrays.fill(count, 0); for (int i = 0; i < n; i++) { count[(arr[i] / exp) % 10]++; } for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (int i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } for (int i = 0; i < n; i++) { arr[i] = output[i]; } } // Bucket Sort public static void bucketSort(int[] arr) { int n = arr.length; int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); int range = max - min + 1; int bucketSize = Math.min(range / n, n); int bucketCount = (range + bucketSize - 1) / bucketSize; // Create buckets int[][] buckets = new int[bucketCount][]; for (int i = 0; i < bucketCount; i++) { buckets[i] = new int[0]; } // Add elements to buckets for (int i = 0; i < n; i++) { int index = (arr[i] - min) / bucketSize; buckets[index] = append(buckets[index], arr[i]); } // Sort individual buckets and merge int index = 0; for (int i = 0; i < bucketCount; i++) { insertionSort(buckets[i]); for (int j = 0; j < buckets[i].length; j++) { arr[index++] = buckets[i][j]; } } } private static int[] append(int[] arr, int value) { int[] result = Arrays.copyOf(arr, arr.length + 1); result[arr.length] = value; return result; } // Shell Sort public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } } }