16.02.2022, 15:28. Показов 528. Ответов 1
Добрый день. Можете помочь. Задание было таким: Напишите программу на языке java для определения вычислительной сложности алгоритмов сортировки пузырем, быстрой сортировки и сортировки разрядами. Все получается, кроме последней сортировки, не понимаю как и куда впихнуть рекурсию. Вот код:
Функции сортировки:
| Java |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
| import java.util.Random;
//класс функций
public class Project {
private int[] array;
//размер массива
public Project(int size) {
array = new int[size];
}
//рандомное заполнение массива
public void randomFilling(int min, int max) {
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = (int) (Math.random() * 100) + 1;
}
}
//показать массив
public void show() {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + "\t");
}
}
// получение максимального значения
public int getMax(int[] array) {
int max = array[0]; // начинаем с первого элемента
for (int i = 0; i < array.length - 1; i++) { // идем по всему массиву
if (array[i] > max) // ищем максимальное число
max = array[i]; // находим максимальное значение
}
return max; // возвращаем найденное максимальное значение
}
// Функция сортировки разрядами
public int radixSort() {
int counter = 0; //счетчик
int tmp; //временная переменная
counter++; //tmp
int digitPlace = 1;
counter+=2; //digitPlace = 1
int[] result = new int[array.length]; // массив результата
// Нахождение максимального числа, чтоб узнать количество цифр
int largestNum = getMax(array);
int[] count = new int[10];
// выполняем цикл до тех пор, пока не достигнем места с наибольшей цифрой
counter++; //while
while (largestNum / digitPlace > 0) {
counter+=2; // largestNum / digitPlace > 0
counter++; //i=0
counter++; //i<10
// Инициализация счетного массива C[] в 0
for (int i = 0; i < 10; i++) {
counter += 2;
count[i] = 0;
}
counter++; //i++ for first
counter++; //exit for i
counter++; //i=0;
counter++; //i < array.length
// Сохранение количество "ключей" или цифр в count[].
for (int i = 0; i < array.length; i++) {
counter += 10;
tmp = Math.abs((array[i] / digitPlace) % 10);
count[tmp]++;
}
counter++; //exit for i
// Изменение count[i] так, чтобы count[i] теперь содержал фактические данные
// положения этой цифры в результатах[]
// Работаем аналогично алгоритму счетной сортировки
counter++; //i=1;
counter++; //i < 10
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
counter+=7; //i++
}
counter++; //exit for i
// Строим результирующий массив
counter+=2; //i=array.length-1
counter++; //i >=0
for (int i = array.length-1; i >= 0; i--) {
counter+=12;
tmp = Math.abs((array[i] / digitPlace) % 10);
result[count[tmp] - 1] = array[i];
count[tmp]--;
}
counter++; //i--
counter++; //exit for i
// Теперь основной массив A[] содержит отсортированные
// числа в соответствии с текущим местом разряда
counter++; //i=0;
counter++; //i < array.length
for (int i = 0; i < array.length; i++) {
counter += 4;
array[i] = result[i];
}
counter++; //i++
counter++; //exit for i
// Переход к следующему разряду
counter++;
digitPlace *= 10;
}
return counter;
}
//функция сортировки пузырьками
public int BubbleSort() {
int counter2 = 0; //счетчик
int temp; //временная переменная
counter2++; //tеmp
counter2++; //i=0
for (int i = 0; i < array.length - 1; i++) {
counter2++; //i < array.length-1
counter2++; //j=0
for (int j = 0; j < array.length - 1; j++) {
counter2++; //j < array.length - 1
counter2++; //if
counter2+=4;
if (array[i] > array[j + 1]) {
counter2+=10;
temp = array[i];
array[i] = array[j + 1];
array[j + 1] = temp;
}
counter2++; //j++
counter2++; //jump
}
counter2++; //exit second
counter2++; //i++ for first
counter2++; // jump first
}
counter2++; //exit first
return counter2;
}
//быстрая сортировка
public int quickSort() {
int counter3 = 0; //счетчик
int low = 0;
counter3+=2; //low = 0
int high = array.length - 1;
counter3+=3; //high = array.length - 1
counter3++; //if
counter3++; //array.length == 0
if (array.length == 0)
return counter3;
counter3++; //if
counter3++; //low >= high
if (low >= high)
return counter3;
// выбрать опорный элемент
int middle = low + (high - low) / 2;
counter3+=6; //middle = low + (high - low) / 2
int opora = array[middle];
counter3+=3; //opora = array[middle]
// разделить на подмассивы, который больше и меньше опорного элемента
counter3+=2; //i = low, j = high
int i = low, j = high;
counter3++; //while
while (i <= j) {
counter3++; //i <= j
counter3++; // while
while (array[i] < opora) {
counter3+=2; //array[i] < opora
i++;
counter3++; //i++
counter3++; //jump
}
counter3++; //exit
counter3++; // while
while (array[j] > opora) {
counter3+=2; //array[j] > opora
j--;counter3++; //j--
counter3++; // jump
}
counter3++; // exit
counter3++; //if
counter3++; //i <= j
if (i <= j) { //меняем местами
counter3+=9;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
counter3++; //jump
counter3++; //exit
}
return counter3;
}
} |
|
Основная функция:
| Java |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| import java.io.FileWriter;
import java.io.IOException;
//основной класс
public class Main {
public static void main(String[] args) throws IOException {
//вывод результата в текст
FileWriter fileWriter = new FileWriter("result1.txt");
int repeatCount = 97; //повтор
int maxSize = 76; //максимальное значение
int minSize = 10; //минимальное значение
//сортировка разрядами
for (int k = minSize; k <= maxSize; k += 10) {
int avg1 = 0;
for (int i = 0; i < repeatCount; i++) {
Project arraySort = new Project(k);
arraySort.randomFilling(1, 13);
avg1 = avg1 + arraySort.radixSort();
}
avg1 = avg1 / repeatCount;
//вывод результата в текстовый документ
System.out.println("Avg1: " + avg1);
fileWriter.write(avg1 + " \n");
}
fileWriter.write(" \n"); //пробел
//сортировка пузырьками
for(int k = minSize; k <= maxSize; k+=10) {
int avg2 = 0;
for (int i = 0; i < repeatCount; i++) {
Project arraySort = new Project(k);
arraySort.randomFilling(1, 13);
avg2 = avg2 + arraySort.BubbleSort();
}
avg2 = avg2 / repeatCount;
//вывод результата в текстовый документ
System.out.println("Avg2: " + avg2);
fileWriter.write( avg2 + " \n");
}
fileWriter.write(" \n"); //пробел
//сортировка быстрая
for (int k = minSize; k <= maxSize; k += 10) {
int avg3 = 0;
for (int i = 0; i < repeatCount; i++) {
Project arraySort = new Project(k);
arraySort.randomFilling(1, 13);
avg3 = avg3 + arraySort.quickSort();
}
avg3 = avg3 / repeatCount;
//вывод результатов в текстовый документ
System.out.println("Avg3: " + avg3);
fileWriter.write(avg3 + " \n");
}
//закрыть запись в текстовый документ
fileWriter.close();
}
} |
|
И кусочек, который должен быть в конце быстрой сортировки:
| Java |
1
2
3
4
5
6
7
8
| // вызов рекурсии для сортировки левой и правой части
counter3+=2; //if (low < j)
if (low < j)
quickSort();
counter3+=2; //if (high > i)
if (high > i)
quickSort(); |
|
(
