Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
EvgenyDrogba
0 / 0 / 0
Регистрация: 25.07.2012
Сообщений: 3
#1

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

29.09.2013, 20:58. Просмотров 715. Ответов 1
Метки нет (Все метки)

Требовалось написать программу с алгоритмами сортировки, затем сравнить эти алгоритмы (но проблема не в этом). Все работает, кроме быстрой сортировке. Ввожу размер массива 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];
    }
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.09.2013, 20:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм быстрой сортировки не работает с большим количеством чисел (C++):

Не алгоритм быстрой сортировки - C++
Просто как подключить эту функцию Не работаеееет #include&lt;iostream&gt; #include&lt;iomanip&gt; #include &lt;algorithm&gt; using namespace std; ...

Алгоритм быстрой сортировки - C++
Написать программу, реализующую алгоритм быстрой сортировки(рекурсивный) для массива целых чисел.

Реализовать алгоритм быстрой сортировки - C++
Реализовать алгоритм быстрой сортировки. Суть алгоритма: из исходного массива выбирается нулевой элемент, после чего массив разделяется на...

Алгоритм быстрой сортировки по убыванию - C++
Я нашёл алгоритм быстрой сортировки по возрастанию: int n, a; //n - количество элементов void qs(int* s_arr, int first, int last) ...

Алгоритм Быстрой сортировки (Quick Sort) - C++
Всем доброго времени суток. Реализовал Быструю Сортировку на C++. Всё работает. Только препод требует доказать, что мой алгоритм...

Разработать эффективный алгоритм быстрой сортировки - C++
Быстрая сортировка. Разработайте эффективный алгоритм для упорядочивания n элементов таким образом, чтобы все отрицательные элементы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
renald
35 / 35 / 2
Регистрация: 11.02.2012
Сообщений: 105
29.09.2013, 21:10 #2
в подробности не вдавался, но по моему вместо
Цитата Сообщение от EvgenyDrogba Посмотреть сообщение
int last = array[size];
нужно
C++
1
int last = array[size-1];
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.09.2013, 21:10
Привет! Вот еще темы с ответами:

Параллельный алгоритм быстрой сортировки (quicksort) - C++
Как реализовать параллельный алгоритм быстрой сортировки на C++? Необходимо в последовательном алгоритме быстрой сортировки...

Алгоритм быстрой сортировки против пузырька - C++
Решил проверить утверждение, что быстрая сортировка намного эффективнее пузырьковой. Результат пузырька увидел почти сразу, а быстрой...

Qvick-sort алгоритм быстрой сортировки. Гляньте плс( - C++
пОДСКАЖИТЕ ПЛС ЧТО НЕ ТАК((( Знаю гдето напортачил когда массив в функцию передавалю Гляньте кто-то шарящий может кто поймет в чем дело,...

Алгоритм быстрой сортировки. Каким образом меняются исходные индексы? - C++
del


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru