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

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

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

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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

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