Аватар для SanychBY
39 / 46 / 3
Регистрация: 04.06.2013
Сообщений: 1,532

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

12.04.2015, 20:58. Показов 24736. Ответов 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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
12.04.2015, 20:58
Ответы с готовыми решениями:

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

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

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

7
20 / 20 / 14
Регистрация: 07.02.2015
Сообщений: 145
12.04.2015, 21:20
Цитата Сообщение от 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  [ТС]
DISTURB, вам никогда не было интересно почему не работает именно Ваш велосипед?

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

Добавлено через 1 минуту
Тем более данный пример неверный (я его проверял, точно не помню), но то, что этот алгоритм не совсем оптимизирован, видно.
0
20 / 20 / 14
Регистрация: 07.02.2015
Сообщений: 145
12.04.2015, 21:40
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  [ТС]
[quote="DISTURB;7471348"] меня интересует мой.
0
20 / 20 / 14
Регистрация: 07.02.2015
Сообщений: 145
12.04.2015, 22:24
Цитата Сообщение от SanychBY Посмотреть сообщение
меня интересует мой.
Попробуйте сравнить построчно с тем примером, который я привел.
0
 Аватар для SanychBY
39 / 46 / 3
Регистрация: 04.06.2013
Сообщений: 1,532
12.04.2015, 22:26  [ТС]
Цитата Сообщение от DISTURB Посмотреть сообщение
Попробуйте сравнить построчно с тем примером, который я привел.
Есть различия в алгоритме, собственно поэтому мне этот пример и не нравится, реализация не верна.
while (mas[f]<mid) f++;
while (mas[l]>mid) l--;
Я могу спокойно выйти за медиану, а этого делать нельзя.
0
20 / 20 / 14
Регистрация: 07.02.2015
Сообщений: 145
12.04.2015, 22:55
Цитата Сообщение от SanychBY Посмотреть сообщение
реализация не верна.
Цитата Сообщение от SanychBY Посмотреть сообщение
while (mas[f]<mid) f++;
while (mas[l]>mid) l--;
Всё по пунктам. Можно сказать, классическая реализация.
  • Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
  • Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
12.04.2015, 22:55
Помогаю со студенческими работами здесь

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

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

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

Сортировка Слиянием vs Быстрая Сортировка - что лучше
Народ, помогите разобраться какой из методов сортировки лучше &quot;Сортировка Слиянием&quot; или &quot;Быстрая Сортировка&quot;: у быстрой...

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


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

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

Новые блоги и статьи
Деплой Flask приложения
py-thonny 23.06.2025
За годы работы с Flask я натыкался на одни и те же грабли достаточно часто, чтобы наконец научится их обходить. И сегодня хочу поделится опытом, который сбережет вам немало нервных клеток. Начнем с. . .
WebAssembly и контейнеры в .NET Aspire для оркестрации распределенных архитектур
ArchitectMsa 23.06.2025
Я наблюдаю, как WebAssembly (или просто WASM) постепенно выходит за рамки своего первоначального предназначения — исполнения кода на стороне браузера. Теперь эта технология проникает в серверную. . .
Непрерывная интеграция для пакета Python
Mr. Docker 22.06.2025
Было 4 часа утра пятницы, когда я выпустил новую версию нашей внутренней библиотеки для обработки данных. Релиз 0. 5. 2 содержал небольшой фикс для обработки дат в ISO формате, что может пойти не так?. . .
Продвинутый ETL на C# из OLTP БД в хранилище
stackOverflow 22.06.2025
Работая в сфере корпоративной аналитики, я постоянно сталкиваюсь с одним и тем же - нужны чистые, структурированные и, главное, свежие данные. Без них современные аналитические системы, машинное. . .
Мастер-класс по микросервисам на Node.js
Reangularity 21.06.2025
Node. js стал одной из самых популярных платформ для микросервисной архитектуры не случайно. Его неблокирующая однопоточная модель и событийно-ориентированный подход делают его идеальным для. . .
Управление Arduino из WPF приложения
Wired 21.06.2025
Зачем вообще связывать Arduino с WPF-приложением? Казалось бы, у Arduino есть собственная среда разработки, своя экосистема, свои способы управления. Однако при создании серьезных проектов. . .
Звёздная пыль
kumehtar 20.06.2025
Я просто это себе представляю: как создавался этот мир. Как энергия слипалась в маленькие частички. Как они собирались в первые звёзды, как во вселенной впервые появился Свет. Как эти звёзды. . .
Создание нейросети с PyTorch
AI_Generated 19.06.2025
Ключевое преимущество PyTorch — его питоновская натура. В отличие от TensorFlow, который изначально был построен как статический вычислительный граф, PyTorch предлагает динамический подход. Это. . .
JWT аутентификация в ASP.NET Core
UnmanagedCoder 18.06.2025
Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .
Краткий курс по С#
aaLeXAA 18.06.2025
Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru