Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
1

Quiсk sort

10.07.2009, 19:30. Просмотров 985. Ответов 14
Метки нет (Все метки)

Пытаюсь освоить метод быстрой сортировки, в оригинале quick sort.
Очень новенький в c++. Учил не много c++ builder, но решил написать в "консоли". Вот простой код:
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
//---------------------------------------------------------------------------
 
#include <vcl.h>
#include <iostream.h>
#pragma argsused
 
#pragma hdrstop
 
//---------------------------------------------------------------------------
int a[12];
//---------------------------------------------------------------------------
void swap(int &a,int &b)   //
{                          //  меняет местами два числа
int c=a;                   //
a=b; b=c;                  //
}                          //
//---------------------------------------------------------------------------
void sort (int l,int r)
{
int i=l,j=r;
int x=a[l+random(r-l)+1];          //опорный ел-мент -
while (i<=j)                       //случайный елемент массива
      {
      while (a[i]<x) i++;
      while (a[j]>x) j--;
            if (i<=j)
            swap(a[i],a[j]);
       }
sort(i,r);
sort(l,j);
 
}
 
 
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
randomize();
for(int i=0;i<13;i++)             //
        {                         //
        a[i]=random(199)+1;       // присваивание эл-там массива
        cout<<a[i]<<"   ";        // случайные числа и вывод их
        }                         //
cout<<endl;
sort(0,12);                 //вызов
for(int i=0;i<13;i++)             //
        {                         //
        cout<<a[i];               // вывод
        cout<<"  ";               //
        }                         //
cin>>"";                    //штука что б увидеть результат
}
//---------------------------------------------------------------------------
программа запускается, но выдаёт ошибку
"Project Project1.exe raised exception class EStackOverflost with message 'Stack overflow'.Use Step or Run to continue."
Прогуглив ошибку ничего мне понятного не нашёл. Спасибо за любую помощь.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.07.2009, 19:30
Ответы с готовыми решениями:

Sort(), третий параметр: как sort() выбирает аргументы из переданной последовательности для переданной функции?
Вот sotr() 2 параметра - итераторы, а третий функцию. Допустим, моя функция сортирует список по...

sort()
пожалуйста напишите несколько примеров,с перегруженными версиями sort? vector&lt;int&gt; vec;...

Sort()
Страуструп в своей книге вызывает эту функцию без всяких дополнительных библиотек. У меня же такая...

Алгоритм sort
Товарищи, подскажите, в чем косяк? std::vector&lt;gc_node *&gt; nodes; ... void...

14
121 / 121 / 14
Регистрация: 14.03.2009
Сообщений: 462
10.07.2009, 19:37 2
Цитата Сообщение от Mailto Посмотреть сообщение
int a[12];
Цитата Сообщение от Mailto Посмотреть сообщение
for(int i=0;i<13;i++)
на лицо вылезание за пределы массива
0
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
10.07.2009, 19:41  [ТС] 3
Цитата Сообщение от EnzoMatrix Посмотреть сообщение
на лицо вылезание за пределы массива
спасибо но проблема не в этом. Ошибка та же.
Код в шапке поправлю.

Нет. Не получится поправить.
0
121 / 121 / 14
Регистрация: 14.03.2009
Сообщений: 462
10.07.2009, 19:42 4
ну там еще и второй цикл есть такой же...его исправили тоже?
и в вызове sort число 12 мелькает, на месте которого по идее 11 должно быть
0
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
10.07.2009, 19:44  [ТС] 5
Цитата Сообщение от EnzoMatrix Посмотреть сообщение
ну там еще и второй цикл есть такой же...его исправили тоже?
нет, просто увеличил массив.
0
Эксперт С++
2328 / 1701 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
10.07.2009, 19:44 6
Произошла перегрузка стека при рекурсивном вызове функции sort.
Тебе нужно смотреть в сторону рекурсивных функций и проблем с ними связанными (как раз таки возможная перегрузка стека).
Для новичка это довольно таки сложная тема, но иначе тебе будет не понять эту ошибку (кстати не твою).
0
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
10.07.2009, 19:53  [ТС] 7
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Произошла перегрузка стека при рекурсивном вызове функции sort.
Тебе нужно смотреть в сторону рекурсивных функций и проблем с ними связанными (как раз таки возможная перегрузка стека).
Для новичка это довольно таки сложная тема, но иначе тебе будет не понять эту ошибку (кстати не твою).
по примеру википедии http://ru.wikipedia.org/wiki/%... 0%BA%D0%B0
добавил в начало функции сортировки проверку границ.
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
//---------------------------------------------------------------------------
 
#include <vcl.h>
#include <iostream.h>
#pragma argsused
 
#pragma hdrstop
 
//---------------------------------------------------------------------------
int a[13];
//---------------------------------------------------------------------------
void swap(int &a,int &b)   //
{                          //
int c=a;                   //
a=b; b=c;                  //
}                          //
//---------------------------------------------------------------------------
void sort (int l,int r)
{
if (r<l) return; //новая строчка
int i=l,j=r;
int x=a[l+random(r-l)+1];          //
while (i<=j)                       //
      {
      while (a[i]<x) i++;
      while (a[j]>x) j--;
            if (i<=j)
            swap(a[i],a[j]);
       }
 
sort(i,r);
sort(l,j);
 
}
 
 
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
randomize();
for(int i=0;i<13;i++)             //
        {                         //
        a[i]=random(199)+1;       // 
        cout<<a[i]<<"   ";        // 
        }                         //
cout<<endl;
sort(0,12);                 //
for(int i=0;i<13;i++)             //
        {                         //
        cout<<a[i];               //
        cout<<"  ";               //
        }                         //
cin>>"";                    //
}
//---------------------------------------------------------------------------
0
Эксперт С++
2328 / 1701 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
10.07.2009, 20:03 8
Цитата Сообщение от Mailto Посмотреть сообщение
добавил в начало функции сортировки проверку границ.
Дело не в границах, дело в перегрузке стека, я же тебе говорю смотри в сторону рекурсии. В примере явно ошибка. Подожди, счас пороюсь, где то была функция быстрой сортировки.
Вот держи, замени свою sort на эту:
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
void sort(int l, int u)
{
  int i = l;
  int j = u;
 
  int x = a[(l + u) / 2];
 
  do {
    while (a[i] < x)
      ++i;
    while (a[j] > x)
      --j;
 
    if(i <= j){
      if (i < j) 
        swap(a[i], a[j]);
 
      ++i;
      --j;
    }
  } while (i <= j);
 
  if (i < u)
    sort(i, u);
  if (l < j)
    sort(l, j);
}
0
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
10.07.2009, 20:13  [ТС] 9
довольно таки странно. Подставив вашу подпрограмму, у меня появилась идентичная ошибка. Но стоило мне дописать в конце всего кода
C++
1
return 0;
всё заработало и с моим вариантом. В общем проблема решена, но непонятки остались...
0
Эксперт С++
7171 / 3229 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
10.07.2009, 20:50 10
Ха.
Занимался я тут как-то оптимизацией qsort().
Вы все будете сильно удивлены, если посмотрите на реализацию функции быстрой сортировки в Linux, BSD, etc.
Там все весьма и весьма не тривиально.
А все ради скорости выполнения.
0
1848 / 705 / 55
Регистрация: 11.12.2008
Сообщений: 1,019
10.07.2009, 21:54 11
Я так скажу, что быстрая сортировка плохо работает на почти отсортированых данных, и очень плохо на отсортированых. В книгах(например "Алгоритмы" Мюллера) пишут, что желательно перед сортировкой сделать один проход случайного перемешивания данных. Мож в этом была проблема?
0
Эксперт С++
7171 / 3229 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
11.07.2009, 19:47 12
А кто сказал что функция qsort() реализует именно быструю сортировку ?
Они там сначала пытаются сделать inserting sort, который на сортированных данных скорее всего быстрее работает. Никакого предварительного перемешивания нигде не видел, да и глупо это все.
0
576 / 570 / 65
Регистрация: 29.01.2009
Сообщений: 1,274
11.07.2009, 20:12 13
Цитата Сообщение от Otaka Посмотреть сообщение
Я так скажу, что быстрая сортировка плохо работает на почти отсортированых данных, и очень плохо на отсортированых.
На моем (не самом крутом) железе библиотечная qsort работает с отсортированным массивом из N=1000000 (можно увеличить по желанию) примерно 0.18 сек., лучше еще никто не справлялся.
0
1848 / 705 / 55
Регистрация: 11.12.2008
Сообщений: 1,019
11.07.2009, 20:41 14
Ну не знаю. Я просто сказал, то что написано в книге "Алгоритмы. Построение и анализ". В этой книге куча алгоритмов на разные темы и быстрая сортировка разобрана очень подробно, приведлен её математический анализ.
(страница 161)
Идея состоит в привнесении случайности, обеспечивающее нужное распределение. Например, перед началом сортировки можно случайным образом переставить элементы, после чего уже все перестановки станут равновероятными(это можно сделать за О(n)). Такая модификация не увеличит серьезно время работы, но теперь мат ожидание времени работы не зависит от порядка входных элементов.
...
Для такого вероятностного алгоритма быстрой сортировки нет неудобных входов.
...
Там же даны и другие улучшения: процедура разбиения Ламуто, разбиение с помощью медианы трех элементов.
Есть еще куча улучшений данной сортировки, и они справляются со всеми этими неудобными входами(например реализация в том же линуксе).
0
depict1
281 / 146 / 4
Регистрация: 11.07.2009
Сообщений: 606
11.07.2009, 20:43 15
Цитата Сообщение от Gravity Посмотреть сообщение
из N=1000000
Цитата Сообщение от Gravity Посмотреть сообщение
лучше еще никто не справлялся
элементы что собой представляют? строки? целые цисла? структуры?

можно ручками реализовать другие методы сортировки- гораздо более эффективные, чем qsort из standard library.
тот же mergesort например. которая имеет гарантированное время выполнения сортировки в худшем случае O(n*lgn), кроме того она устойчивая, в отличии от быстрой сортировки, время выполнения которой в худшем случае O(N*N). В общем тут нужно с умом (в зав-ти от природы сортируемых данных) подходить к выбору/реализации метода сортировки.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.07.2009, 20:43

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

list sort()
Подскажите пожалуйста. Есть упрощенный класс class NOTE { public: char name; char...

Strand Sort
Кто-нибудь реализовывал Strand сортировку на С++ ? на википедии примеры только на других...

Bubble sort
Учу сортировки массивов, но не знаю, как обращаться к ним через процедуру! Процедура: int...

std::sort
Достоинства и недостатки делаю таблицу, достоинств и недостатков std::Sort. собственно, не...


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

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

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