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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
11.08.2012, 22:21     Алгоритм быстрой сортировки против пузырька #1
Решил проверить утверждение, что быстрая сортировка намного эффективнее пузырьковой.
Результат пузырька увидел почти сразу, а быстрой сортировки ждал пару минут и выключил. В чём дело? Ошибка в коде? Или пузырькём лучше быстрой сортировки?

Вот код:


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);
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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);
При этом тест у вас неадекватный, так как тестируете разные массивы.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 22:40     Алгоритм быстрой сортировки против пузырька #3

Не по теме:

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



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

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

Ну и left ещё да. Накидывает к тормозам, что вы ещё раз сортируете уже отсортированное.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 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 очевиден.
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
12.08.2012, 01:37     Алгоритм быстрой сортировки против пузырька #5
Это при рандомном заполнении...
При наличии закономерности результаты могут быть другими...
Но думаю в любом случае пузырек не вариант в производительности.
Catstail
Модератор
 Аватар для Catstail
21501 / 10254 / 1670
Регистрация: 12.02.2012
Сообщений: 17,139
12.08.2012, 08:35     Алгоритм быстрой сортировки против пузырька #6
Даже не вникая в код, можно сказать следующее: единственное достоинство "пузырька" - простота. Хотя сортировка перестановками, по-моему, еще проще.

Тем не менее, есть случаи, когда простые методы эффективнее quicksort. Это случай почти отсортированного массива. Но тогда еще лучше использовать сортировку вставками (она устойчива и естественна, чего лишена quicksort; почти упорядоченные массивы будут сортироваться очень быстро).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.08.2012, 14:02     Алгоритм быстрой сортировки против пузырька
Еще ссылки по теме:

Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов C++
Qvick-sort алгоритм быстрой сортировки. Гляньте плс( C++
Алгоритм быстрой сортировки C++

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

Или воспользуйтесь поиском по форуму:
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 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);
}
Массивы обьявлены глобально.Мне этот вариант по душе.
Yandex
Объявления
12.08.2012, 14:02     Алгоритм быстрой сортировки против пузырька
Ответ Создать тему
Опции темы

Текущее время: 11:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru