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

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

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

Быстрая сортировка по возрастанию - C++

07.09.2015, 11:28. Просмотров 427. Ответов 11
Метки нет (Все метки)

Добрый день, хотел попросить помощи, смотрел в интернете на тему быстрой сортировки, но адекватного объяснения, понятного мне, я не нашел. В общем, есть динамический массив, и как его сделать я понимаю, а дальше даётся картинка, на которой нарисовано, как нужно отсортировать квиксортом. Я не прошу решить мне задачу, но мог бы кто-нибудь объяснить мне в теории, как это отсортировать?

Заранее спасибо.
Изображения
 
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sashatref
75 / 75 / 27
Регистрация: 21.05.2015
Сообщений: 257
Завершенные тесты: 1
07.09.2015, 11:30     Быстрая сортировка по возрастанию #2
Shadowdown, есть std::qsort, где это уже реализовано, или нужно именно самому написать алгоритм?
Shadowdown
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 17
07.09.2015, 11:38  [ТС]     Быстрая сортировка по возрастанию #3
Sashatref, нужно именно самому алгоритм написать
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
07.09.2015, 12:28     Быстрая сортировка по возрастанию #4
Shadowdown, а что картинка-то означает?
AleksandrMild
0 / 0 / 0
Регистрация: 02.09.2015
Сообщений: 18
07.09.2015, 12:46     Быстрая сортировка по возрастанию #5
На ютубе есть супер понятное объяснение
Quick-sort with Hungarian (Küküllőmenti legényes) folk dance :
https://www.youtube.com/watch?v=ywWBy6J5gz8
Shadowdown
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 17
07.09.2015, 12:47  [ТС]     Быстрая сортировка по возрастанию #6
Kuzia domovenok, Белое поле, это где не надо сортировать, а где стрелки - это в какую сторону элементы должны увеличиваться по значению
ture
437 / 330 / 123
Регистрация: 27.11.2014
Сообщений: 1,038
07.09.2015, 12:49     Быстрая сортировка по возрастанию #7
Shadowdown, быструю сортировку британ какой-то придумал. Чего он там напридумывал, надо в вики глядеть, там и пример кода. Я тож врубался долго и ошибки лепил. Короч смотри сразу реализацию ибо родить это самому крайне не просто. Хотя это бритн как-то выродил.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
07.09.2015, 14:45     Быстрая сортировка по возрастанию #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
AleksandrMild, ой, вот только никакой наглядности на видео я хоть убей - не заметил. Какую роль играют эти бендеровцы в пояснении процесса сортировки? Только отвлекают, имхо. Наглядное объяснение потому и называют наглядным, что сложный процесс становится простым
за счёт визуализации неочевидной его части и абстракции от мешающих пониманию несущественных деталей. На видео же наоборот добавляются всякие детали - вышиванки, горилка, танцы-шманцы, делающие картину пёстрой для мозга.
Вот это - наглядное объяснение сортировки... https://upload.wikimedia.org/wikiped...rt-example.gif

Добавлено через 9 минут
для такой картинки как у автора, двумерный массив int a[n][n] сортировать надо в следующем порядке
C++
1
2
3
4
5
for (i=0 i<n; i++)
{
qsort(a[i], a[i]+abs(n/2-i), less);
qsort(a[i]+n-abs(n/2-i), a[i]+n, more);
}
ture
437 / 330 / 123
Регистрация: 27.11.2014
Сообщений: 1,038
07.09.2015, 15:21     Быстрая сортировка по возрастанию #9
Kuzia domovenok, эти Ваши бендеровцы разносят нас на олимпиадах по программированию в прах.
MansMI
1134 / 931 / 239
Регистрация: 08.01.2012
Сообщений: 3,362
07.09.2015, 15:43     Быстрая сортировка по возрастанию #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
если самому, вроде так:
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
void qSort(int* a, int l, int r)
{
    int i=l, j=r, m=a[(l+r)/2];
    do
    {
        for(; a[i]<m; i++);
        for(; a[j]>m; j--);
        if( i<=j) swap(a[i++],a[j--]);
    }while(i<=j);
    if(l<j) qSort(a,l,j);
    if(i<r) qSort(a,i,r);
}
void main(int argc, char* argv[])
{
    const int n=25;
    int a[n];
 
    srand((unsigned)time(0));
    for(int i=0; i<n; i++)
    {
        a[i]=rand()%100;
        cout<<a[i]<<" ";
    }
    cout<<endl;
    qSort(a,0,n-1);
    for(int i=0; i<n; i++) cout<<a[i]<<" ";
    cout<<endl;
    system("pause");
}
Shadowdown
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 17
07.09.2015, 16:47  [ТС]     Быстрая сортировка по возрастанию #11
Kuzia domovenok, MansMI, спасибо за разъяснение!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2015, 17:33     Быстрая сортировка по возрастанию
Еще ссылки по теме:

Быстрая сортировка (сортировка Хоара) для связных списков C++
C++ Быстрая сортировка
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка
C++ Сортировка расчёской и быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
07.09.2015, 17:33     Быстрая сортировка по возрастанию #12
Цитата Сообщение от ture Посмотреть сообщение
Kuzia domovenok, эти Ваши бендеровцы разносят нас на олимпиадах по программированию в прах.
https://en.wikipedia.org/wiki/Intern...in_Informatics
дай пруф на то, что венгры где-то нас разносят в прах по программированию.
Yandex
Объявления
07.09.2015, 17:33     Быстрая сортировка по возрастанию
Ответ Создать тему
Опции темы

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