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

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

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

Quiсk sort - C++

10.07.2009, 19:30. Просмотров 866. Ответов 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."
Прогуглив ошибку ничего мне понятного не нашёл. Спасибо за любую помощь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.07.2009, 19:30     Quiсk sort
Посмотрите здесь:

C++ Алгоритм sort
C++ q-sort сортировка
qsort vs sort C++
Quick sort c++ C++
Функция sort C++
C++ STL sort()
Strand Sort C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
EnzoMatrix
120 / 120 / 5
Регистрация: 14.03.2009
Сообщений: 462
10.07.2009, 19:37     Quiсk sort #2
Цитата Сообщение от Mailto Посмотреть сообщение
int a[12];
Цитата Сообщение от Mailto Посмотреть сообщение
for(int i=0;i<13;i++)
на лицо вылезание за пределы массива
Mailto
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
10.07.2009, 19:41  [ТС]     Quiсk sort #3
Цитата Сообщение от EnzoMatrix Посмотреть сообщение
на лицо вылезание за пределы массива
спасибо но проблема не в этом. Ошибка та же.
Код в шапке поправлю.

Нет. Не получится поправить.
EnzoMatrix
120 / 120 / 5
Регистрация: 14.03.2009
Сообщений: 462
10.07.2009, 19:42     Quiсk sort #4
ну там еще и второй цикл есть такой же...его исправили тоже?
и в вызове sort число 12 мелькает, на месте которого по идее 11 должно быть
Mailto
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
10.07.2009, 19:44  [ТС]     Quiсk sort #5
Цитата Сообщение от EnzoMatrix Посмотреть сообщение
ну там еще и второй цикл есть такой же...его исправили тоже?
нет, просто увеличил массив.
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.07.2009, 19:44     Quiсk sort #6
Произошла перегрузка стека при рекурсивном вызове функции sort.
Тебе нужно смотреть в сторону рекурсивных функций и проблем с ними связанными (как раз таки возможная перегрузка стека).
Для новичка это довольно таки сложная тема, но иначе тебе будет не понять эту ошибку (кстати не твою).
Mailto
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
10.07.2009, 19:53  [ТС]     Quiсk sort #7
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Произошла перегрузка стека при рекурсивном вызове функции sort.
Тебе нужно смотреть в сторону рекурсивных функций и проблем с ними связанными (как раз таки возможная перегрузка стека).
Для новичка это довольно таки сложная тема, но иначе тебе будет не понять эту ошибку (кстати не твою).
по примеру википедии http://ru.wikipedia.org/wiki/%D0%91%...B2%D0%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>>"";                    //
}
//---------------------------------------------------------------------------
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.07.2009, 20:03     Quiсk sort #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);
}
Mailto
0 / 0 / 0
Регистрация: 10.07.2009
Сообщений: 5
10.07.2009, 20:13  [ТС]     Quiсk sort #9
довольно таки странно. Подставив вашу подпрограмму, у меня появилась идентичная ошибка. Но стоило мне дописать в конце всего кода
C++
1
return 0;
всё заработало и с моим вариантом. В общем проблема решена, но непонятки остались...
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.07.2009, 20:50     Quiсk sort #10
Ха.
Занимался я тут как-то оптимизацией qsort().
Вы все будете сильно удивлены, если посмотрите на реализацию функции быстрой сортировки в Linux, BSD, etc.
Там все весьма и весьма не тривиально.
А все ради скорости выполнения.
Otaka
1822 / 678 / 18
Регистрация: 11.12.2008
Сообщений: 1,019
10.07.2009, 21:54     Quiсk sort #11
Я так скажу, что быстрая сортировка плохо работает на почти отсортированых данных, и очень плохо на отсортированых. В книгах(например "Алгоритмы" Мюллера) пишут, что желательно перед сортировкой сделать один проход случайного перемешивания данных. Мож в этом была проблема?
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.07.2009, 19:47     Quiсk sort #12
А кто сказал что функция qsort() реализует именно быструю сортировку ?
Они там сначала пытаются сделать inserting sort, который на сортированных данных скорее всего быстрее работает. Никакого предварительного перемешивания нигде не видел, да и глупо это все.
Gravity
558 / 552 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
11.07.2009, 20:12     Quiсk sort #13
Цитата Сообщение от Otaka Посмотреть сообщение
Я так скажу, что быстрая сортировка плохо работает на почти отсортированых данных, и очень плохо на отсортированых.
На моем (не самом крутом) железе библиотечная qsort работает с отсортированным массивом из N=1000000 (можно увеличить по желанию) примерно 0.18 сек., лучше еще никто не справлялся.
Otaka
1822 / 678 / 18
Регистрация: 11.12.2008
Сообщений: 1,019
11.07.2009, 20:41     Quiсk sort #14
Ну не знаю. Я просто сказал, то что написано в книге "Алгоритмы. Построение и анализ". В этой книге куча алгоритмов на разные темы и быстрая сортировка разобрана очень подробно, приведлен её математический анализ.
(страница 161)
Идея состоит в привнесении случайности, обеспечивающее нужное распределение. Например, перед началом сортировки можно случайным образом переставить элементы, после чего уже все перестановки станут равновероятными(это можно сделать за О(n)). Такая модификация не увеличит серьезно время работы, но теперь мат ожидание времени работы не зависит от порядка входных элементов.
...
Для такого вероятностного алгоритма быстрой сортировки нет неудобных входов.
...
Там же даны и другие улучшения: процедура разбиения Ламуто, разбиение с помощью медианы трех элементов.
Есть еще куча улучшений данной сортировки, и они справляются со всеми этими неудобными входами(например реализация в том же линуксе).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2009, 20:43     Quiсk sort
Еще ссылки по теме:

Bubble sort C++
C++ sort()
C++ Sort()
Merge Sort C++
Merge sort C++

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

Или воспользуйтесь поиском по форуму:
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
11.07.2009, 20:43     Quiсk sort #15
Цитата Сообщение от Gravity Посмотреть сообщение
из N=1000000
Цитата Сообщение от Gravity Посмотреть сообщение
лучше еще никто не справлялся
элементы что собой представляют? строки? целые цисла? структуры?

можно ручками реализовать другие методы сортировки- гораздо более эффективные, чем qsort из standard library.
тот же mergesort например. которая имеет гарантированное время выполнения сортировки в худшем случае O(n*lgn), кроме того она устойчивая, в отличии от быстрой сортировки, время выполнения которой в худшем случае O(N*N). В общем тут нужно с умом (в зав-ти от природы сортируемых данных) подходить к выбору/реализации метода сортировки.
Yandex
Объявления
11.07.2009, 20:43     Quiсk sort
Ответ Создать тему
Опции темы

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