Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
130 / 117 / 30
Регистрация: 14.11.2010
Сообщений: 707
1

Рекурсивная сортировка разделением

06.01.2011, 11:51. Просмотров 1598. Ответов 0
Метки нет (Все метки)


ниже привел код рекурсивной сортировки разделением, но она сортирует нормально, если в массиве представлены только уникальные элементы, а если появляются одинаковые, то зацикливается...
не могу понять в чем дело...
вызов в main Qsort(0, a.size-1); где a - объект класса vector

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
template <class T> void vector<T>::Qsort(int l, int r)
{
   if(l < r)
   {
       int k = Partition(l, r);
       Qsort(l, k);
       Qsort(k+1, r);
   }
}
 
template <class T> int vector<T>::Partition(int l, int r)
{
    T x = array[(l+r)/2];  
    int i = l;
    int j = r;
    while(1)
    {
       while(array[j] > x)
       {
           j--;
       }
       while(array[i] < x)
       {
           i++;
       }
       if(i < j)
       {
           T t = array[i];
             array[i] = array[j];
             array[j] = t;
       } else return j;
    }
}
Добавлено через 21 час 50 минут
нашел в чем ошибка, нужно добавить в тело if i++; j--;

C++
1
2
3
4
5
6
7
8
if(i < j)
           {
                   T t = array[i];
                         array[i] = array[j];
                         array[j] = t;
                         i++;
                         j--;
           } else return j;
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.01.2011, 11:51
Ответы с готовыми решениями:

Сортировка разделением
Написать программу, использующую рекурсивную функцию sort, которая сортирует одномерный массив...

Сортировка разделением
Всем привет. В универе задали сделать курсовую на тему &quot;Сортировка разделением&quot;. Написал вот такой...

Сортировка разделением
Здравствуйте! Помогите пожалуйста с задачей. Мне не нужна готовая программа, мне надо большее :)...

Быстрая сортировка с разделением
Помогите создать функцию быстрой сортировки с разделением. Мы не изучали ее алгоритм в делфи....

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.01.2011, 11:51

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

Быстрая» сортировка (разделением) с использованием указателей
У меня не принимают работу, так как говорят, что не по заданию. В чем ошибка? #include &quot;stdafx.h&quot;...

Рекурсивная сортировка массива.
Помогите срочно! Дан массив в c++ {'A','B','C','D','E','F','G'}, надо написать код через int или...

1)Бинарный поиск 2)Сортировка включением 3)Шейкерная сортировка 4)Сортировка разделением
1)В заданном массиве К(N) найти индексы элементов, которые кратны минимальному значению элемента...

сортировка разделением
Задан массив A(N). Добавить массив X(М). Выполнить сортировку разделением. Подсчитайте сумму...


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

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

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