Нравится 0
Создать форк 0

Последняя активность 1718984838

kristofer's Avatar kristofer ревизий этого фрагмента 1718984838. К ревизии

1 file changed, 345 insertions

SortingExamples.java(файл создан)

@@ -0,0 +1,345 @@
1 + import java.util.Arrays;
2 + import java.util.Scanner;
3 +
4 + public class SortingExamples {
5 + public static void main(String[] args) {
6 + Scanner input = new Scanner(System.in);
7 +
8 + // Input array from the user
9 + System.out.print("Enter the number of elements in the array: ");
10 + int n = input.nextInt();
11 + int[] arr = new int[n];
12 +
13 + System.out.println("Enter the elements of the array:");
14 + for (int i = 0; i < n; i++) {
15 + arr[i] = input.nextInt();
16 + }
17 +
18 + // Choose a sorting algorithm
19 + System.out.println("\nChoose a sorting algorithm (1-10):");
20 + System.out.println("1- Selection sort");
21 + System.out.println("2- Bubble sort");
22 + System.out.println("3- Insertion sort");
23 + System.out.println("4- Merge sort");
24 + System.out.println("5- Quick sort");
25 + System.out.println("6- Heap sort");
26 + System.out.println("7- Counting sort");
27 + System.out.println("8- Radix sort");
28 + System.out.println("9- Bucket Sort");
29 + System.out.println("10- Shell Sort");
30 + System.out.print("Enter your choice: ");
31 + int choice = input.nextInt();
32 +
33 + switch (choice) {
34 + case 1:
35 + selectionSort(arr);
36 + break;
37 + case 2:
38 + bubbleSort(arr);
39 + break;
40 + case 3:
41 + insertionSort(arr);
42 + break;
43 + case 4:
44 + mergeSort(arr);
45 + break;
46 + case 5:
47 + quickSort(arr, 0, n - 1);
48 + break;
49 + case 6:
50 + heapSort(arr);
51 + break;
52 + case 7:
53 + countingSort(arr);
54 + break;
55 + case 8:
56 + radixSort(arr);
57 + break;
58 + case 9:
59 + bucketSort(arr);
60 + break;
61 + case 10:
62 + shellSort(arr);
63 + break;
64 + default:
65 + System.out.println("Invalid choice. No sorting performed.");
66 + }
67 +
68 + // Print the sorted array
69 + System.out.println("Sorted array: " + Arrays.toString(arr));
70 + }
71 +
72 + // Selection Sort
73 + public static void selectionSort(int[] arr) {
74 + int n = arr.length;
75 + for (int i = 0; i < n - 1; i++) {
76 + int minIndex = i;
77 + for (int j = i + 1; j < n; j++) {
78 + if (arr[j] < arr[minIndex]) {
79 + minIndex = j;
80 + }
81 + }
82 + int temp = arr[minIndex];
83 + arr[minIndex] = arr[i];
84 + arr[i] = temp;
85 + }
86 + }
87 +
88 + // Bubble Sort
89 + public static void bubbleSort(int[] arr) {
90 + int n = arr.length;
91 + boolean swapped;
92 + for (int i = 0; i < n - 1; i++) {
93 + swapped = false;
94 + for (int j = 0; j < n - i - 1; j++) {
95 + if (arr[j] > arr[j + 1]) {
96 + int temp = arr[j];
97 + arr[j] = arr[j + 1];
98 + arr[j + 1] = temp;
99 + swapped = true;
100 + }
101 + }
102 + if (!swapped) {
103 + break;
104 + }
105 + }
106 + }
107 +
108 + // Insertion Sort
109 + public static void insertionSort(int[] arr) {
110 + int n = arr.length;
111 + for (int i = 1; i < n; i++) {
112 + int key = arr[i];
113 + int j = i - 1;
114 + while (j >= 0 && arr[j] > key) {
115 + arr[j + 1] = arr[j];
116 + j--;
117 + }
118 + arr[j + 1] = key;
119 + }
120 + }
121 +
122 + // Merge Sort
123 + public static void mergeSort(int[] arr) {
124 + mergeSort(arr, 0, arr.length - 1);
125 + }
126 +
127 + private static void mergeSort(int[] arr, int left, int right) {
128 + if (left < right) {
129 + int mid = (left + right) / 2;
130 + mergeSort(arr, left, mid);
131 + mergeSort(arr, mid + 1, right);
132 + merge(arr, left, mid, right);
133 + }
134 + }
135 +
136 + private static void merge(int[] arr, int left, int mid, int right) {
137 + int n1 = mid - left + 1;
138 + int n2 = right - mid;
139 + int[] L = new int[n1];
140 + int[] R = new int[n2];
141 +
142 + for (int i = 0; i < n1; i++) {
143 + L[i] = arr[left + i];
144 + }
145 + for (int i = 0; i < n2; i++) {
146 + R[i] = arr[mid + 1 + i];
147 + }
148 +
149 + int i = 0, j = 0, k = left;
150 + while (i < n1 && j < n2) {
151 + if (L[i] <= R[j]) {
152 + arr[k] = L[i];
153 + i++;
154 + } else {
155 + arr[k] = R[j];
156 + j++;
157 + }
158 + k++;
159 + }
160 +
161 + while (i < n1) {
162 + arr[k] = L[i];
163 + i++;
164 + k++;
165 + }
166 +
167 + while (j < n2) {
168 + arr[k] = R[j];
169 + j++;
170 + k++;
171 + }
172 + }
173 +
174 + // Quick Sort
175 + public static void quickSort(int[] arr, int low, int high) {
176 + if (low < high) {
177 + int pivotIndex = partition(arr, low, high);
178 + quickSort(arr, low, pivotIndex - 1);
179 + quickSort(arr, pivotIndex + 1, high);
180 + }
181 + }
182 +
183 + private static int partition(int[] arr, int low, int high) {
184 + int pivot = arr[high];
185 + int i = low - 1;
186 + for (int j = low; j < high; j++) {
187 + if (arr[j] < pivot) {
188 + i++;
189 + int temp = arr[i];
190 + arr[i] = arr[j];
191 + arr[j] = temp;
192 + }
193 + }
194 + int temp = arr[i + 1];
195 + arr[i + 1] = arr[high];
196 + arr[high] = temp;
197 + return i + 1;
198 + }
199 +
200 + // Heap Sort
201 + public static void heapSort(int[] arr) {
202 + int n = arr.length;
203 + for (int i = n / 2 - 1; i >= 0; i--) {
204 + heapify(arr, n, i);
205 + }
206 + for (int i = n - 1; i >= 0; i--) {
207 + int temp = arr[0];
208 + arr[0] = arr[i];
209 + arr[i] = temp;
210 + heapify(arr, i, 0);
211 + }
212 + }
213 +
214 + private static void heapify(int[] arr, int n, int i) {
215 + int largest = i;
216 + int left = 2 * i + 1;
217 + int right = 2 * i + 2;
218 +
219 + if (left < n && arr[left] > arr[largest]) {
220 + largest = left;
221 + }
222 + if (right < n && arr[right] > arr[largest]) {
223 + largest = right;
224 + }
225 +
226 + if (largest != i) {
227 + int swap = arr[i];
228 + arr[i] = arr[largest];
229 + arr[largest] = swap;
230 + heapify(arr, n, largest);
231 + }
232 + }
233 +
234 + // Counting Sort
235 + public static void countingSort(int[] arr) {
236 + int n = arr.length;
237 + int max = Arrays.stream(arr).max().getAsInt();
238 + int min = Arrays.stream(arr).min().getAsInt();
239 + int range = max - min + 1;
240 + int[] count = new int[range];
241 + int[] output = new int[n];
242 +
243 + for (int i = 0; i < n; i++) {
244 + count[arr[i] - min]++;
245 + }
246 +
247 + for (int i = 1; i < range; i++) {
248 + count[i] += count[i - 1];
249 + }
250 +
251 + for (int i = n - 1; i >= 0; i--) {
252 + output[count[arr[i] - min] - 1] = arr[i];
253 + count[arr[i] - min]--;
254 + }
255 +
256 + for (int i = 0; i < n; i++) {
257 + arr[i] = output[i];
258 + }
259 + }
260 +
261 + // Radix Sort
262 + public static void radixSort(int[] arr) {
263 + int max = Arrays.stream(arr).max().getAsInt();
264 + for (int exp = 1; max / exp > 0; exp *= 10) {
265 + countingSortByDigit(arr, exp);
266 + }
267 + }
268 +
269 + private static void countingSortByDigit(int[] arr, int exp) {
270 + int n = arr.length;
271 + int[] output = new int[n];
272 + int[] count = new int[10];
273 + Arrays.fill(count, 0);
274 +
275 + for (int i = 0; i < n; i++) {
276 + count[(arr[i] / exp) % 10]++;
277 + }
278 +
279 + for (int i = 1; i < 10; i++) {
280 + count[i] += count[i - 1];
281 + }
282 +
283 + for (int i = n - 1; i >= 0; i--) {
284 + output[count[(arr[i] / exp) % 10] - 1] = arr[i];
285 + count[(arr[i] / exp) % 10]--;
286 + }
287 +
288 + for (int i = 0; i < n; i++) {
289 + arr[i] = output[i];
290 + }
291 + }
292 +
293 + // Bucket Sort
294 + public static void bucketSort(int[] arr) {
295 + int n = arr.length;
296 + int max = Arrays.stream(arr).max().getAsInt();
297 + int min = Arrays.stream(arr).min().getAsInt();
298 + int range = max - min + 1;
299 +
300 + int bucketSize = Math.min(range / n, n);
301 + int bucketCount = (range + bucketSize - 1) / bucketSize;
302 +
303 + // Create buckets
304 + int[][] buckets = new int[bucketCount][];
305 + for (int i = 0; i < bucketCount; i++) {
306 + buckets[i] = new int[0];
307 + }
308 +
309 + // Add elements to buckets
310 + for (int i = 0; i < n; i++) {
311 + int index = (arr[i] - min) / bucketSize;
312 + buckets[index] = append(buckets[index], arr[i]);
313 + }
314 +
315 + // Sort individual buckets and merge
316 + int index = 0;
317 + for (int i = 0; i < bucketCount; i++) {
318 + insertionSort(buckets[i]);
319 + for (int j = 0; j < buckets[i].length; j++) {
320 + arr[index++] = buckets[i][j];
321 + }
322 + }
323 + }
324 +
325 + private static int[] append(int[] arr, int value) {
326 + int[] result = Arrays.copyOf(arr, arr.length + 1);
327 + result[arr.length] = value;
328 + return result;
329 + }
330 +
331 + // Shell Sort
332 + public static void shellSort(int[] arr) {
333 + int n = arr.length;
334 + for (int gap = n / 2; gap > 0; gap /= 2) {
335 + for (int i = gap; i < n; i++) {
336 + int temp = arr[i];
337 + int j;
338 + for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
339 + arr[j] = arr[j - gap];
340 + }
341 + arr[j] = temp;
342 + }
343 + }
344 + }
345 + }
Новее Позже

Работает на Opengist ⋅ Load: 23ms⋅

Русский