12 / 12 / 3
Регистрация: 27.07.2012
Сообщений: 208
1

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

11.08.2012, 22:21. Показов 4710. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.08.2012, 22:21
Ответы с готовыми решениями:

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

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

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

Алгоритм Быстрой Сортировки на C++
Можно ли этот алгоритм использовать для последовательности чисел? Просто в книге Сэджвика...

6
Эксперт С++
4264 / 2238 / 203
Регистрация: 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
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 22:40 3

Не по теме:

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



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

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

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

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

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

Я не опечатался.такие данные я и получил.Сортирвки копировал из темы на нашем форуме.QuickSort свой вариант писал.Выбор в сторону QuickSort очевиден.
1
Эксперт С++
8381 / 6142 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
12.08.2012, 01:37 5
Это при рандомном заполнении...
При наличии закономерности результаты могут быть другими...
Но думаю в любом случае пузырек не вариант в производительности.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
32453 / 17995 / 3765
Регистрация: 12.02.2012
Сообщений: 30,213
Записей в блоге: 5
12.08.2012, 08:35 6
Даже не вникая в код, можно сказать следующее: единственное достоинство "пузырька" - простота. Хотя сортировка перестановками, по-моему, еще проще.

Тем не менее, есть случаи, когда простые методы эффективнее quicksort. Это случай почти отсортированного массива. Но тогда еще лучше использовать сортировку вставками (она устойчива и естественна, чего лишена quicksort; почти упорядоченные массивы будут сортироваться очень быстро).
0
Мой лучший друг-отладчик!
165 / 165 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.08.2012, 14:02
Помогаю со студенческими работами здесь

Реализовать алгоритм быстрой сортировки
Реализовать алгоритм быстрой сортировки. Суть алгоритма: из исходного массива выбирается нулевой...

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru