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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
#1

Алгоритм быстрой сортировки против пузырька - C++

11.08.2012, 22:21. Просмотров 1996. Ответов 6
Метки нет (Все метки)

Решил проверить утверждение, что быстрая сортировка намного эффективнее пузырьковой.
Результат пузырька увидел почти сразу, а быстрой сортировки ждал пару минут и выключил. В чём дело? Ошибка в коде? Или пузырькём лучше быстрой сортировки?

Вот код:


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
//Sort.cpp
 
void BubbleSort(int num[], int size_num){
    bool change;
    int t;
 
    for(int i = 1; i<size_num; i++){
        for(int j=size_num-1;j >=i ; j--)
            if(num[j] > num[j-1]){
                t = num[j];
                num[j] = num[j-1];
                num[j-1] = t;
                change = true;
            }
        if(!change) break;
    }
}
 
void QuickSort(int num[], int size_num){
    Qs(num,0,size_num -1);
}
 
void Qs(int num[], int left, int right){
    register int i = left;
    register int j = right;
 
    int x = num[(left + right)/2];
    int temp;
 
    do{
        while(num[i] < x) i++;
        while(num[j] > x) j--;
 
        if(i<=j){
            temp = num[i];
            num[i] = num[j];
            num[j] = temp;
            i++; j--;
        }
    }while(i<=j);
 
    if(j > left) Qs(num,0,j);
    if(i < right) Qs(num,i,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
//main.cpp
 
#include <iostream>
#include <conio.h>
#include <time.h>
#include "Sort.h"
using namespace std;
 
 
 
void ShowArray(int num[], int size_num){
    int i;
 
    for(i=0; i<size_num; i++)
        cout << num[i] << ' ';
    cout << "\n";
}
 
 
void main(){
    srand(time(NULL));
    
    int *num = new int[10000];
 
    for(int i = 0; i<10000; i++)
        num[i] = rand();
    BubbleSort(num,10000);
    ShowArray(num,10000);
 
        getch();
 
    for(int i = 0; i<100; i++)
        num[i] = rand();
    Qs(num,0,10000);
    ShowArray(num,10000);
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2012, 22:21
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм быстрой сортировки против пузырька (C++):

Комбинированный метод быстрой сортировки с методом «пузырька» - C++
Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов. Алгоритм сортировки (поиска) оформить в виде функции. ...

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

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

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

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

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

6
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.08.2012, 22:36 #2
Здесь ошибка
C++
1
if(j > left) Qs(num,0,j);
Надо так
C++
1
if(j > left) Qs(num,left,j);
При этом тест у вас неадекватный, так как тестируете разные массивы.
1
OhMyGodSoLong
~ Эврика! ~
1245 / 994 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 22:40 #3

Не по теме:

Пузырёк это ошибка эволюции и его вообще если приводить, то с припиской, что хуже его только bogosort.



Во-вторых, у вас в цикле на 33 строке потерялась пара нулей. Значит, 9800 элементов массива у вас уже были отсортированы пузырьком. Вы напоролись на классический случай, когда qsort лажает: на (почти) отсортированном массиве quicksort превращается в сортировку пузырьком, да ещё и с рекурсией сверху (что, очевидно, приводит к тому, что он тормозит ещё больше пузырька).

Попробуйте поправить, должно быть быстрее. Если нет, то надо смотреть, где вы напортачили в алгоритме.

Ну и left ещё да. Накидывает к тормозам, что вы ещё раз сортируете уже отсортированное.
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
12.08.2012, 01:16 #4
Раз зашла речь о эффективности алгоритмов сортировок, то и я слово скажу.Недавно мне нефиг было делать, и решил протестировать алгоритмы сортировок на скорость.
Итак, имеется массив на 100000 чисел типа int.Числа эти - от 0 до 9 включительно.Заполняется рандомно.Ну вот результаты:

Сортировка вставками - 7016 мс.
Сортировка пузырьком - 41319 мс.
Сортировка Хоара(быстрая сортировка) - 30 мс.
Сортировка выбором - 11556 мс.

Как говорится, no comments.

Я не опечатался.такие данные я и получил.Сортирвки копировал из темы на нашем форуме.QuickSort свой вариант писал.Выбор в сторону QuickSort очевиден.
1
Avazart
Эксперт С++
7572 / 5557 / 326
Регистрация: 10.12.2010
Сообщений: 24,917
Записей в блоге: 17
12.08.2012, 01:37 #5
Это при рандомном заполнении...
При наличии закономерности результаты могут быть другими...
Но думаю в любом случае пузырек не вариант в производительности.
0
Catstail
Модератор
23446 / 11573 / 1882
Регистрация: 12.02.2012
Сообщений: 18,895
12.08.2012, 08:35 #6
Даже не вникая в код, можно сказать следующее: единственное достоинство "пузырька" - простота. Хотя сортировка перестановками, по-моему, еще проще.

Тем не менее, есть случаи, когда простые методы эффективнее quicksort. Это случай почти отсортированного массива. Но тогда еще лучше использовать сортировку вставками (она устойчива и естественна, чего лишена quicksort; почти упорядоченные массивы будут сортироваться очень быстро).
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
12.08.2012, 14:02 #7
Да, согласен с Вами, на опчти отсортированных массивах quick sort плохо себя показывает.Но на случайных массивах quicksort выигрывает и очень серьезно.Я думаю, что надо на случайных массивах юзать quick sort и только его(если других каких либо условий нет).

А насчёт простоты пузырька - для меня и квиксорт очень прост.всегда пользуюсь этим вариантом этой сортировки:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void quickSort(int first,int last)
{
     int i=first;
     int j=last;
     int mid=a[first + rand() % (last-first+1)];
     while(i<=j)
        {
            while(a[i]<mid) i++;
            while(a[j]>mid) j--;
               if(i<=j)
                {
                    swap(a[i],a[j]);
                    i++;
                    j--; 
                }
        }
      if(i<last)
         quickSort(i,last);
      if(first<j)
         quickSort(first,j);
}
Массивы обьявлены глобально.Мне этот вариант по душе.
0
12.08.2012, 14:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.08.2012, 14:02
Привет! Вот еще темы с ответами:

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

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

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

Алгоритм быстрой сортировки не работает с большим количеством чисел - C++
Требовалось написать программу с алгоритмами сортировки, затем сравнить эти алгоритмы (но проблема не в этом). Все работает, кроме быстрой...


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

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

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