Алгоритм быстрой сортировки не работает с большим количеством чисел

@EvgenyDrogba · Регистрация: 25.07.2012

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

Требовалось написать программу с алгоритмами сортировки, затем сравнить эти алгоритмы (но проблема не в этом). Все работает, кроме быстрой сортировке. Ввожу размер массива 77, все сортируется во всех алгоритмах, ввожу 78 и выше, зависает именно на быстрой сортировке и завершается((( В чем проблема можеть быть? Вот, собственно, код.

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
#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <iomanip>
using namespace std;
 
void bubble_sort(int*, int);
void paste_sort(int*, int);
void selection_sort(int*, int);
void quick_sort(int *, int, int);
void output_mass(int *, int);
 
int main()
{
    int size;
    srand (time(NULL));
 
    cout << "Sorting algorithms.\n\n";
    cout << "Enter the size of array: ";
 
    cin >> size;
 
    cout << "\nInitial array: " << endl;
 
    int *array = new int[size];
 
    for (int i = 0; i < size; ++i)
    {
        array[i] = rand()% 50+1;
        cout << setw(3) << array[i];
    }
 
    cout << "\n\nSorted array (bubble method): " << endl;
    bubble_sort(array, size);
 
    cout << "\n\nSorted array (paste method): " << endl;
    paste_sort(array, size);
 
    cout << "\n\nSorted array (selection method): " << endl;
    selection_sort(array, size);
 
    cout << "\n\nSorted array (quick method): " << endl;
    int first = array[0];
    int last = array[size];
    quick_sort(array, first, last);
    output_mass(array,size);
 
    cout << endl << endl;
 
    delete [] array;
    system ("pause");
    return 0;
}
 
void bubble_sort (int *mass, int n)
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = n-1; j > i; --j)
            if (mass[j] < mass[j - 1])
            {
                int tmp = mass[j];
                mass[j] = mass[j-1];
                mass[j - 1] = tmp;
            }
    }
    output_mass(mass,n);
}
 
void paste_sort (int *mass, int n)
{
    for (int i = 0; i < n; ++i)
    {
        int tmp = mass[i];
        int j = i - 1;
        while (j >= 0 && tmp < mass[j])
        {
            mass[j + 1] = mass[j];
            j--;
        }
        mass[j+1] = tmp;
    }
     output_mass(mass,n);
}
 
void selection_sort (int *mass, int n)
{
    for (int i = 0; i < n; ++i)
    {
        int indexMin = i;
        for (int j = indexMin + 1; j < n; ++j)
            if (mass[j] < mass[indexMin])
                indexMin = j;
        if (indexMin != i)
        {
            int tmp = mass[indexMin];
            mass[indexMin] = mass[i];
            mass[i] = tmp;
        }
    }
    output_mass(mass,n);
}
 
void quick_sort(int *mass,int a,int b)
{
    int temp;
    int i = a;
    int j = b;
    int x = mass[(a + b) / 2];
 
    do
    {
        while (mass[i] <  x)
            j--;
        if(i <= j)
        {
            if (i < j)
            {
                temp = mass[i];
                mass[i]=mass[j];
                mass[j]=temp;
            }
            i++;
            j--;
        }
    }
    while (i <= j);
 
    if (i < b)
        quick_sort(mass,i, b);
    if (a < j)
        quick_sort(mass,a,j);
}
 
void output_mass (int *mass, int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << setw(3) << mass[i];
    }
}

@renald · 29.09.2013, 21:10

в подробности не вдавался, но по моему вместо

Сообщение от EvgenyDrogba

int last = array[size];

нужно

C++
1
int last = array[size-1];

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .