Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Shadowdown
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 17
1

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

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

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

Заранее спасибо.
0
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.09.2015, 11:28
Ответы с готовыми решениями:

Быстрая сортировка стобцов матрицы по возрастанию
Всем доброго времени суток! Задается квадратная матрица с четным количеством...

Быстрая сортировка. Сложности с сортировкой по возрастанию и убыванию
Сложность в то, что не корректно работает быстрая сортировка по возрастанию и...

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

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

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

11
sashatref
75 / 75 / 29
Регистрация: 21.05.2015
Сообщений: 257
Завершенные тесты: 1
07.09.2015, 11:30 2
Shadowdown, есть std::qsort, где это уже реализовано, или нужно именно самому написать алгоритм?
0
Shadowdown
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 17
07.09.2015, 11:38  [ТС] 3
Sashatref, нужно именно самому алгоритм написать
0
Kuzia domovenok
2435 / 2142 / 523
Регистрация: 25.03.2012
Сообщений: 7,714
Записей в блоге: 1
07.09.2015, 12:28 4
Shadowdown, а что картинка-то означает?
1
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
0
Shadowdown
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 17
07.09.2015, 12:47  [ТС] 6
Kuzia domovenok, Белое поле, это где не надо сортировать, а где стрелки - это в какую сторону элементы должны увеличиваться по значению
0
ture
529 / 337 / 206
Регистрация: 27.11.2014
Сообщений: 1,043
07.09.2015, 12:49 7
Shadowdown, быструю сортировку британ какой-то придумал. Чего он там напридумывал, надо в вики глядеть, там и пример кода. Я тож врубался долго и ошибки лепил. Короч смотри сразу реализацию ибо родить это самому крайне не просто. Хотя это бритн как-то выродил.
0
Kuzia domovenok
2435 / 2142 / 523
Регистрация: 25.03.2012
Сообщений: 7,714
Записей в блоге: 1
07.09.2015, 14:45 8
Лучший ответ Сообщение было отмечено Shadowdown как решение

Решение

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);
}
1
ture
529 / 337 / 206
Регистрация: 27.11.2014
Сообщений: 1,043
07.09.2015, 15:21 9
Kuzia domovenok, эти Ваши бендеровцы разносят нас на олимпиадах по программированию в прах.
0
MansMI
1448 / 1157 / 549
Регистрация: 08.01.2012
Сообщений: 4,509
07.09.2015, 15:43 10
Лучший ответ Сообщение было отмечено Shadowdown как решение

Решение

если самому, вроде так:
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");
}
0
Shadowdown
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 17
07.09.2015, 16:47  [ТС] 11
Kuzia domovenok, MansMI, спасибо за разъяснение!
0
Kuzia domovenok
2435 / 2142 / 523
Регистрация: 25.03.2012
Сообщений: 7,714
Записей в блоге: 1
07.09.2015, 17:33 12
Цитата Сообщение от ture Посмотреть сообщение
Kuzia domovenok, эти Ваши бендеровцы разносят нас на олимпиадах по программированию в прах.
https://en.wikipedia.org/wiki/International_Olympiad_in_Informatics
дай пруф на то, что венгры где-то нас разносят в прах по программированию.
0
07.09.2015, 17:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2015, 17:33

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

Сортировка: сначала положительные числа по возрастанию, а потом - отрицательные тоже по возрастанию
Имеется код программы сортировки чисел. нужно чтобы сначала выводило...

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


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

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

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