Быстрая сортировка двумерного массива

@Михаил Мамаев · Регистрация: 28.10.2014

Author24 — интернет-сервис помощи студентам

Здравствуйте. У меня есть задание по сортировкам. Нужно заданный двумерный массив из рандомных чисел отсортировать по возрастанию по строкам. Прошу помочь только с быстрой сортировкой. Там выдает несколько ошибок, связанных с указателями, а я в них пока не так силён. Функция рекурсивная, поэтому немного запутался. Буду очень благодарен за помощь.

C++
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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
#include <iostream>
#include <stdio.h>
#include <ctime>
 
int quicksort_div(int* arr[], int N, int i)
{
    int comparison = 0, shift = 0;
    int mid_el = N / 2;
    int el_left = 0, el_right = N - 1;
    while (el_left != el_right)
    {
        comparison++;
        while (arr[i][el_left] < arr[i][mid_el])
        {
            comparison++;
            el_left++;
        }
        comparison++;
        while (arr[i][el_right] > arr[i][mid_el])
        {
            comparison++;
            el_right--;
        }
        if (el_left < el_right)
        {
            int shift = 0;
            int tmp = arr[i][el_left];
            arr[i][el_left] = arr[i][el_right];
            arr[i][el_right] = tmp;
            shift++;
            if (el_left == mid_el) mid_el = el_right;
            else if (el_right == mid_el) mid_el = el_left;
        }
    }
    return mid_el;
}
 
void quicksort(int* arr[], int N, int M, int &comparison, int &shift, int i)
{
    for (i = 0; i < M; i++)
    {
        if (N <= 1)
        {
            return;
        }
        else if (N == 2)
        {
            N++;
            if (arr[i][0] > arr[i][1])
            {
                int  tmp = arr[i][0];
                arr[i][0] = arr[i][1];
                arr[i][1] = tmp;
                shift++;
            }
        }
        else
        {
            int mid_val = quicksort_div(arr, N, i);
            quicksort(arr, mid_val, M, comparison, shift, i);
            quicksort(arr + mid_val + 1, N - mid_val - 1, M, comparison, shift, i);
        }
    }
}
 
int main()
{
    int arr[100][100];
    int arr_tmp[100][100];
    int i = 0, tmp = 0, max = 0, counter_words = 0, comparison = 0, shift = 0;
    bool in_word = false;
    int M, N;  
    std::cout << "Enter the number of lines (1-15) \n";
    lines:
    std::cin >> M;
    if (M >= 1 && M <= 15) std::cout << "\n";
    else 
    { 
        std::cout << "Error. Try again:\n";
        goto lines;
    }
    std::cout << "Enter the number of colomns (1-15) \n";
    colomns:
    std::cin >> N;
    if (N >= 1 && N <= 15) std::cout << "\n";
    else
    { 
        std::cout << "Error. Try again:\n";
        goto colomns;
    }
 
    srand(time(NULL));
 
    for (int i = 0; i < M; i++) //строка
    {
        for (int j = 0; j < N; j++) //столбец
        {
            arr[i][j] = rand() % 100;
            arr_tmp[i][j] = arr[i][j];
        }
    }
 
    /////////////////////////////////////////////////////////Вывод массива///////////////////////////////////////////////////
 
    for (int i = 0; i < M; i++)
    {
        printf("\n");
        for (int j = 0; j < N; j++)
        {
            printf("%4i ", arr[i][j]);
        }
    }
 
    ////////////////////////
    //Сортировка пузырьком//
    ////////////////////////
 
    for (int i = 0; i < M; i++)
    {
        for (int k = 0; k < N; k++)
        {
            for (int j = 0; j < N - 1 - k; j++)
            {
                comparison++;
                if (arr[i][j] > arr[i][j + 1])
                {
                    int w = arr[i][j + 1];
                    arr[i][j + 1] = arr[i][j];
                    arr[i][j] = w;
                    shift++;
                }
            }
        }
    }
    /////////////////////////////////////////////////Вывод массива/////////////////////////////////////////
 
    printf("\n");
    for (int i = 0; i < M; i++)
    {
        printf("\n");
        for (int j = 0; j < N; j++)
        {
            printf("%4i ", arr[i][j]);
        }
    }
 
    //////////////////////////////////////////Перезаполнение массива из запасного////////////////////////////////////////////
 
    for (int i = 0; i < M; i++) //строка
    {
        for (int j = 0; j < N; j++) //столбец
        {
            arr[i][j] = arr_tmp[i][j];
        }
    }
 
    int shift_bubble = shift;
    int comparison_bubble = comparison;
    shift = 0;
    comparison = 0;
 
    ////////////////////////
    ////Сортировка выбором//
    ////////////////////////
    for (int i = 0; i < M; i++)
    {
        for (int k = 0; k < N - 1; k++)
        {
            int j;
            int min = k;
            for (j = k + 1; j < N; j++)
            {
                comparison++;
                if (arr[i][min] > arr[i][j])
                {
                    min = j;
                }
            }
            int tmp = arr[i][k];
            arr[i][k] = arr[i][min];
            arr[i][min] = tmp;
            shift++;
        }
    }
 
    /////////////////////////////////////////////////Вывод массива/////////////////////////////////////////
 
    printf("\n");
    for (int i = 0; i < M; i++)
    {
        printf("\n");
        for (int j = 0; j < N; j++)
        {
            printf("%4i ", arr[i][j]);
        }
    }
 
    //////////////////////////////////////////Перезаполнение массива из запасного////////////////////////////////////////////
 
    for (int i = 0; i < M; i++) //строка
    {
        for (int j = 0; j < N; j++) //столбец
        {
            arr[i][j] = arr_tmp[i][j];
        }
    }
 
    int shift_select = shift;
    int comparison_select = comparison;
    shift = 0;
    comparison = 0;
 
    ////////////////////////
    //Сортировка вставками//
    ////////////////////////
 
    for (int i = 0; i < M; i++)
    {
        for (int k = 1; k < N; k++)
        {
            int j;
            int tmp = arr[i][k];
            for (j = k - 1; j >= 0; j--)
            {
                comparison++;
                if (arr[i][j] > tmp)
                {
                    arr[i][j + 1] = arr[i][j];
                    shift++;
                }
                else
                {
                    break;
                }
            }
            arr[i][j + 1] = tmp;
            shift++;
        }
    }
 
    /////////////////////////////////////////////////Вывод массива/////////////////////////////////////////
 
    printf("\n");
    for (int i = 0; i < M; i++)
    {
        printf("\n");
        for (int j = 0; j < N; j++)
        {
            printf("%4i ", arr[i][j]);
        }
    }
 
    //////////////////////////////////////////Перезаполнение массива из запасного////////////////////////////////////////////
 
    for (int i = 0; i < M; i++) //строка
    {
        for (int j = 0; j < N; j++) //столбец
        {
            arr[i][j] = arr_tmp[i][j];
        }
    }
 
    int shift_insert = shift;
    int comparison_insert = comparison;
    shift = 0;
    comparison = 0;
 
    /////////
    //Shell//
    /////////
 
    for (int i = 0; i < M; i++)
    {
        for (int d = N / 2; d >= 1; d /= 2)
        {
            for (int k = d; k < N; k += d)
            {
                int j;
                tmp = arr[i][k];
                for (j = k - d; j >= 0; j -= d)
                {
                    comparison++;
                    if (arr[i][j] > tmp)
                    {
                        arr[i][j + d] = arr[i][j];
                        shift++;
                    }
                    else
                    {
                        break;
                    }
                }
                arr[i][j + d] = tmp;
                shift++;
            }
        }
    }
 
    /////////////////////////////////////////////////Вывод массива/////////////////////////////////////////
 
    printf("\n");
    for (int i = 0; i < M; i++)
    {
        printf("\n");
        for (int j = 0; j < N; j++)
        {
            printf("%4i ", arr[i][j]);
        }
    }
 
    //////////////////////////////////////////Перезаполнение массива из запасного////////////////////////////////////////////
 
    for (int i = 0; i < M; i++) //строка
    {
        for (int j = 0; j < N; j++) //столбец
        {
            arr[i][j] = arr_tmp[i][j];
        }
    }
 
    int shift_shell = shift;
    int comparison_shell = comparison;
    shift = 0;
    comparison = 0;
 
    ////////////////////////
    //      Quicksort     //
    ////////////////////////
 
    quicksort(arr, N, M, comparison, shift, i);
 
    /////////////////////////////////////////////////Вывод массива/////////////////////////////////////////
 
    printf("\n");
    for (int i = 0; i < M; i++)
    {
        printf("\n");
        for (int j = 0; j < N; j++)
        {
            printf("%4i ", arr[i][j]);
        }
    }
 
    int shift_quick = shift;
    int comparison_quick = comparison;
    shift = 0;
    comparison = 0;
 
    /////////////////////////////////////////////////////////////////////////////////////////////////
 
    getchar();
    getchar();
    return 0;
}

@sutop · 02.09.2015, 10:55

С указателями можно решить вопрос так:

C++
1
2
    int *pointer = &arr[0][0];
    quicksort(&pointer, N, M, comparison, shift, i);

только там еще в логике быстрой сортировки не все хорошо( Пока не понял что, если надо - могу разобрать.

Добавлено через 2 часа 13 минут
Собственно сразу бросился в глаза первый цикл внутри quicksort - по количеству измерений(M), его либо надо вынести в тело программы либо добавить еще одну функцию, где происходит обход.
За передачу индекса в качестве параметра и использовании одноименных индексов (i) однозначно отругают, но это дело житейское.
В функции quicksort_div происходит зацикливание после прохода слева и справа (индексы el_left и el_right не меняются).
После того как помучился чуть - заглянул в википедию и понял, что рекурсия там идет не по mid_val, а именно по el_left и el_right , так что такое разбиение на просчет среднего элемента и вызов рекурсивно от дробленого массива не по канону(. Собственно решение из википедии:

C++
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
int qsort(int *a, int left, int right)
{
int l   = left;
int r   = right;
int foo = 0;
int mid = a[(l + r) / 2];
 
        while (l <= r)
        {
                while ((a[l] < mid) && (l <= right))
                {
                        l++;
                }
                while ((a[r] > mid) && (r >= left))
                {
                        r--;
                }
 
                if (l <= r)
                {
                        foo = a[l];
                        a[l] = a[r];
                        a[r] = foo;
                        l++;
                        r--;
                }
        }
 
        if (r > left)
        {
                qsort(a, left, r);
        }
        if (l < right)
        {
                qsort(a, l, right);
        }
 
return 0;
}
 
// ...
 
//  в main вместо quicksort(arr, N, M, comparison, shift, i);
 
 
    ////////////////////////
    //      Quicksort     //
    ////////////////////////
 
    for(int j=0;j<M;j++)
    {
      int *pointer = arr[j];
      qsort(pointer, 0, N-1);
    }
 
 
    /////////////////////////////////////////////////Вывод массива/////////////////////////////////////////

Правда, под общий стиль программы это не подходит. Но работает.

@Михаил Мамаев · 02.09.2015, 11:10 **[ТС]**

sutop, я вот тоже не понимаю. Просто изначально код был для одномерного массива, а когда я стал писать для двумерного, в быстрой сортировке сразу косяк за косяком пошёл ( в основном по причине добавления индекса i, отвечающий за строки). Если Вы мне поможете, я буду очень благодарен.

Upd: только что отправил. Не заметил Ваше сообщение. Сейчас погляжу.

Добавлено через 14 минут
sutop, я не могу почему то ставить благодарность, но на словах - огромное Вам спасибо.
Я тоже много где видел, что аргументы в функции - это значения лефт и райт, а не мид. Просто нам препод видимо так объяснил. Хотя и не факт, что неправильно. Ваш вариант функции ещё более понятен, чем то, что было. Сейчас буду ставить сравнения и перестановки=) Сильно выручили. Ещё раз спасибо.

Новые блоги и статьи Все статьи Все блоги /
Winforstrap или красявый дизайн своими руками на HTML+JS+Winforms anomal6 04.03.2025 Сидел тут вечером ковырял проект на MAUI, и как же глупо создаются пакеты MSIX и система обновлений пакета публикации, но не об этом. Бывает нужен современный дизайн программы а писать на MAUI,. . .	Формат данных для симуляции физики, посредством распространённых не обученных моделей. Hrethgir 04.03.2025 Что-то как-то снова потерялось, зато катангенсы закатангесились в одном сообщении. На днях писал, что планирую для работы апгрейдить (на этот раз удачно) девайс для работы (конкретно - здоровья для,. . .	Концепция variadic CoderHuligan 04.03.2025 Мне не очень нравится (а кому это нравится?) что у нас есть отдельно компилятор, отдельно линковщик, причем со своим собственным командным языком. При этом усложнении надо знать помимо языка. . .	Java Record или Kotlin Data Class: что лучше для неизменяемых данных Wired 04.03.2025 Java Record и Kotlin Data Class — два мощных инструмента для обуздания неизменяемых структур данных, каждый со своим уникальным подходом к решению этой задачи. История их появления весьма. . .	Создание производительных API с Java и gRPC Wired 04.03.2025 В мире микросервисной разработки вопрос производительности часто становится краеугольным камнем. И хотя REST API давно завоевал сердца разработчиков своей простотой и интуитивностью, при высоких. . .
Что нового в JDK 24 Wired 04.03.2025 JDK 24 — это настоящий прорыв в эволюции Java, который кардинально меняет правила игры. В этом релизе разработчики Oracle наконец-то довели до ума множество критически важных улучшений в. . .	Разработка блокчейн с использованием Java: смарт-контракты и dApp Wired 04.03.2025 Погружаясь в мир блокчейн-разработки на Java, разработчик получает доступ к внушительному арсеналу инструментов. В отличие от Solidity, который "заперт" в экосистеме Ethereum, Java предоставляет. . .	WebAssembly в Kubernetes stackOverflow 03.03.2025 В современной экосистеме облачных технологий WebAssembly (Wasm) становится все более значимым компонентом, предлагая уникальный подход к выполнению кода в распределенных системах. Эта технология. . .	GitHub Actions или Jenkins: Выбираем CI/CD платформу stackOverflow 03.03.2025 Непрерывная интеграция и развертывание (CI/ CD) изменили подход к разработке программного обеспечения, превратив его в бесшовный процесс от написания кода до развертывания в продакшн. GitHub Actions и. . .	Автоматизация тестирования Pull Request в Kubernetes: Интеграция с GitHub Actions и GKE stackOverflow 03.03.2025 Масштабные проекты с использованием Kubernetes требуют надежной системы тестирования изменений перед их внедрением в продакшн-среду. Традиционный подход с ручной проверкой Pull Request не справляется. . .

@Михаил Мамаев 1 / 1 / 0 Регистрация: 28.10.2014 Сообщений: 34
	02.09.2015, 11:10 [ТС]	3
	sutop, я вот тоже не понимаю. Просто изначально код был для одномерного массива, а когда я стал писать для двумерного, в быстрой сортировке сразу косяк за косяком пошёл ( в основном по причине добавления индекса i, отвечающий за строки). Если Вы мне поможете, я буду очень благодарен. Upd: только что отправил. Не заметил Ваше сообщение. Сейчас погляжу. Добавлено через 14 минут sutop, я не могу почему то ставить благодарность, но на словах - огромное Вам спасибо. Я тоже много где видел, что аргументы в функции - это значения лефт и райт, а не мид. Просто нам препод видимо так объяснил. Хотя и не факт, что неправильно. Ваш вариант функции ещё более понятен, чем то, что было. Сейчас буду ставить сравнения и перестановки=) Сильно выручили. Ещё раз спасибо. 0