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

Быстрая сортировка с выбором случайного элемента - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
27.08.2011, 13:42     Быстрая сортировка с выбором случайного элемента #1
Вот тут быстрая сортировка с выбором случайного элемента:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quicksort(int from, int to)
{
 int i=from,j=to,k,temp;
 if (from>=to) return;
 k=from+rand()%(to-from)+1;
 while (i<=j)
  {
   while (mas[i]<mas[k]) i++;
   while (mas[j]>mas[k]) j--;
   if (i<=j)
    {
     temp=mas[i]; mas[i]=mas[j]; mas[j]=temp;
     i++;
     j--;
    }
  }
 quicksort(from,j);
 quicksort(i,to);
}
ошибка возникает вот на таком тесте:
10
90 65 65 21 24 65 25 15 32 65
выдаёт:
15 21 24 25 65 32 65 65 65 90

В чём ошибка кода?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.08.2011, 13:42     Быстрая сортировка с выбором случайного элемента
Посмотрите здесь:

C++ Быстрая + сортировка выбором
Связь между функцией и выбором случайного числа C++
Выбор случайного элемента массива C++
Быстрая сортировка C++
C++ Быстрая сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LosAngeles
Заблокирован
27.08.2011, 13:49     Быстрая сортировка с выбором случайного элемента #2
прокрути деббагером и посмотри
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.08.2011, 13:58     Быстрая сортировка с выбором случайного элемента #3
Ошибка здесь.
C++
1
k=from+rand()%(to-from)+1;
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
27.08.2011, 14:01  [ТС]     Быстрая сортировка с выбором случайного элемента #4
ошибок таковых нет, дело в рандуме, но как исправить?

Добавлено через 3 минуты
Цитата Сообщение от Thinker Посмотреть сообщение
Ошибка здесь.
Код C++
1
k=from+rand()%(to-from)+1;
И что надо вместо этого написать?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.08.2011, 14:05     Быстрая сортировка с выбором случайного элемента #5
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
void QuickSort (int *a, int l, int r)
{
        int i, j;
        int x, buf;
        i = l;
        j = r;
        x = a[(l+r)/2];
        do
        {
            while (a[i] < x)
               i++;
            while (x < a[j])
               j--;
            if (i <= j)
            {
                buf = a[i];
                a[i] = a[j];
                a[j] = buf;
                i++;
                j--;
            }
        } while( i <= j);
        if (l < j) QuickSort (a, l, j);
        if (r > i) QuickSort (a, i, r);
}
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
27.08.2011, 14:12  [ТС]     Быстрая сортировка с выбором случайного элемента #6
Thinker, это я уже писал, это работает. Мне надо со случайным элементом.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.08.2011, 14:21     Быстрая сортировка с выбором случайного элемента #7
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Thinker, это я уже писал, это работает. Мне надо со случайным элементом.
Нет ничего невозможного:

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
void QuickSort (int *a, int l, int r)
{
        int i, j;
        int x, buf;
        i = l;
        j = r;
        x = a[l + rand()%(r - l + 1)];
        do
        {
            while (a[i] < x)
               i++;
            while (x < a[j])
               j--;
            if (i <= j)
            {
                buf = a[i];
                a[i] = a[j];
                a[j] = buf;
                i++;
                j--;
            }
        } while( i <= j);
        if (l < j) QuickSort (a, l, j);
        if (r > i) QuickSort (a, i, r);
}
Добавлено через 6 минут
Цитата Сообщение от Thinker Посмотреть сообщение
Ошибка здесь.
C++
1
k=from+rand()%(to-from)+1;
Я не прав, ошибка не только здесь, весь алгоритм надо было поменять.
gorin
 Аватар для gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
23.10.2011, 00:07     Быстрая сортировка с выбором случайного элемента #8
Thinker, Маленький вопрос, как Эту рекурсивную функцию использовать в кнопке?

Добавлено через 3 минуты
Вот например ты мне давал код рекурсивной функции где в
C++
1
2
3
4
5
6
7
8
9
10
int main(){
//Создаем массив
...
InsertSort(mas, N); // исаользуем рекурс. функц.
    for (i = 0; i < N; i++)
    {
       //печатается отсортированный массив
    }
 
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.10.2011, 10:15     Быстрая сортировка с выбором случайного элемента #9
C++
1
QuickSort (a, 0, N-1);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2011, 19:26     Быстрая сортировка с выбором случайного элемента
Еще ссылки по теме:

Быстрая сортировка C++
C++ Быстрая сортировка
C++ Сортировка расчёской и быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
gorin
 Аватар для gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
24.10.2011, 19:26     Быстрая сортировка с выбором случайного элемента #10
Thinker, спс
Yandex
Объявления
24.10.2011, 19:26     Быстрая сортировка с выбором случайного элемента
Ответ Создать тему
Опции темы

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