Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
SanychBY
39 / 46 / 3
Регистрация: 04.06.2013
Сообщений: 1,532
1

Сортировка Хоара / Быстрая сортировка

12.04.2015, 20:58. Просмотров 1478. Ответов 7
Метки нет (Все метки)

Доброго времени суток.
Написал реализацию алгоритма быстрой сортировки.
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
56
57
58
59
60
61
void SortHhoar(int *arr,int f,int l)//Хоара
{
    int mid = (f + l) / 2;
    int *bufer = new int; 
    int ff = f, ll = l;
    for (;ff <= mid;ff++)
    {
        if (arr[ff] >= arr[mid])
        {
            for (;ll >= mid;ll--)
            {
                if (arr[ll] <= arr[mid])
                {
                    *bufer = arr[ff];
                    arr[ff] = arr[ll];
                    arr[ll] = *bufer;
                    for (int i = 0; i < 10; i++)
                    {
                        cout << arr[i] << " ";
                    }
                    cout << endl;
                    break;
                }
            }
        }
    }
    delete bufer;
    if (ff < l)
    {
        SortHhoar(arr, mid, l);
    }
    if (f < ll)
    {
        SortHhoar(arr , f ,mid);
    }
}
 
void main()
{
    setlocale(LC_ALL,"RU");
    int VArray[10000];
    srand((unsigned)time(0));
 
 
 
    for (int i = 0; i < 10;i++)
    {
        VArray[i] = RANDOM(1000);
        cout << VArray[i] << " ";
    }
    cout << endl;
    SortHhoar(VArray,0,9);
    for (int i = 0; i < 10; i++)
    {
        cout << VArray[i] << " ";
    }
    cout << endl;
 
 
    system("pause");
}
Иногда сортировка выполняется не совсем верно. Помогите разобраться в чем ошибка. Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2015, 20:58
Ответы с готовыми решениями:

Быстрая сортировка (сортировка Хоара) для связных списков
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и...

Быстрая сортировка (сортировка методом Хоара)
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена...

Быстрая сортировка Хоара
Быстрая сортировка Хоара (QSort) разбивает массив в ходе сортировки до ...

7
DISTURB
19 / 19 / 14
Регистрация: 07.02.2015
Сообщений: 145
12.04.2015, 21:20 2
Цитата Сообщение от SanychBY Посмотреть сообщение
Иногда сортировка выполняется не совсем верно. Помогите разобраться в чем ошибка.
Зачем изобретать велосипед? Готовых примеров быстрой сортировки и так масса
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 *mas, int first, int last)
{
int mid, count;
int f=first, l=last;
mid=mas[(f+l) / 2]; //вычисление опорного элемента
do
{
while (mas[f]<mid) f++;
while (mas[l]>mid) l--;
if (f<=l) //перестановка элементов
{
count=mas[f];
mas[f]=mas[l];
mas[l]=count;
f++;
l--;
}
} while (f<l);
if (first<l) quicksort(mas, first, l);
if (f<last) quicksort(mas, f, last);
}
0
SanychBY
39 / 46 / 3
Регистрация: 04.06.2013
Сообщений: 1,532
12.04.2015, 21:24  [ТС] 3
DISTURB, вам никогда не было интересно почему не работает именно Ваш велосипед?

Добавлено через 23 секунды
Гуглить я умею

Добавлено через 1 минуту
Тем более данный пример неверный (я его проверял, точно не помню), но то, что этот алгоритм не совсем оптимизирован, видно.
0
DISTURB
19 / 19 / 14
Регистрация: 07.02.2015
Сообщений: 145
12.04.2015, 21:40 4
SanychBY, я стараюсь избегать написания "велосипедов" в чистом виде.
Цитата Сообщение от SanychBY Посмотреть сообщение
Тем более данный пример неверный
Вполне рабочий пример.
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
#include <iostream>
using namespace std;
void quicksort(int *mas, int first, int last)
{
    int mid, count;
    int f = first, l = last;
    mid = mas[(f + l) / 2]; //вычисление опорного элемента
    do
    {
        while (mas[f]<mid) f++;
        while (mas[l]>mid) l--;
        if (f <= l) //перестановка элементов
        {
            count = mas[f];
            mas[f] = mas[l];
            mas[l] = count;
            f++;
            l--;
        }
    } while (f<l);
    if (first<l) quicksort(mas, first, l);
    if (f<last) quicksort(mas, f, last);
}
 
int main(){
    int mas[10] = { 98, 2, 54, 65, 3, -150, 8, 11, 12, 76 };
    quicksort(mas, 0, 9);
    for (auto&k : mas){
        cout << k << " ";
    }
    system("pause");
    return 0;
0
SanychBY
39 / 46 / 3
Регистрация: 04.06.2013
Сообщений: 1,532
12.04.2015, 21:42  [ТС] 5
[quote="DISTURB;7471348"] меня интересует мой.
0
DISTURB
19 / 19 / 14
Регистрация: 07.02.2015
Сообщений: 145
12.04.2015, 22:24 6
Цитата Сообщение от SanychBY Посмотреть сообщение
меня интересует мой.
Попробуйте сравнить построчно с тем примером, который я привел.
0
SanychBY
39 / 46 / 3
Регистрация: 04.06.2013
Сообщений: 1,532
12.04.2015, 22:26  [ТС] 7
Цитата Сообщение от DISTURB Посмотреть сообщение
Попробуйте сравнить построчно с тем примером, который я привел.
Есть различия в алгоритме, собственно поэтому мне этот пример и не нравится, реализация не верна.
while (mas[f]<mid) f++;
while (mas[l]>mid) l--;
Я могу спокойно выйти за медиану, а этого делать нельзя.
0
DISTURB
19 / 19 / 14
Регистрация: 07.02.2015
Сообщений: 145
12.04.2015, 22:55 8
Цитата Сообщение от SanychBY Посмотреть сообщение
реализация не верна.
Цитата Сообщение от SanychBY Посмотреть сообщение
while (mas[f]<mid) f++;
while (mas[l]>mid) l--;
Всё по пунктам. Можно сказать, классическая реализация.
  • Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
  • Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
0
12.04.2015, 22:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2015, 22:55

Быстрая сортировка Хоара без рекурсивных функций
Здравствуйте мне нужно написать быстрою сортировку Хоара но без рекурсивных...

Сортировка расчёской и быстрая сортировка
В файле in.txt записана последовательность целых чисел. Заданными методами...

сортировка хоара
void QuickSort(int* const a, int low, int N) { int i = low, j = N; ...


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

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

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