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

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

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

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

29.09.2013, 20:58. Просмотров 697. Ответов 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];
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.09.2013, 20:58     Алгоритм быстрой сортировки не работает с большим количеством чисел
Посмотрите здесь:

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

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

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

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

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

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

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

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

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

Применение массивов случайных чисел с большим количеством элементов - C++
Само задание: Создайте две функции для решения одной и той же задачи: динамическое создание и заполнение случайными числами массива...

Реализуйте шаблонный алгоритм "быстрой сортировки" - C++
Реализуйте шаблонный алгоритм &quot;быстрой сортировки&quot;: template&lt;class It, class Cmp&gt; void qsort(It beg, It end, Cmp cmp); Заранее...

Не работает алгоритм сортировки - C++
Не работает алгоритм сортировки Ни при заполнении псевдослучайными числами,ни при заранее заданных. Подскажите пожалуйста, в чем...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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];
Yandex
Объявления
29.09.2013, 21:10     Алгоритм быстрой сортировки не работает с большим количеством чисел
Ответ Создать тему
Опции темы

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