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

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

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

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

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

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

Заранее спасибо.
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.09.2015, 11:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрая сортировка по возрастанию (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 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
438 / 331 / 123
Регистрация: 27.11.2014
Сообщений: 1,038
07.09.2015, 12:49 #7
Shadowdown, быструю сортировку британ какой-то придумал. Чего он там напридумывал, надо в вики глядеть, там и пример кода. Я тож врубался долго и ошибки лепил. Короч смотри сразу реализацию ибо родить это самому крайне не просто. Хотя это бритн как-то выродил.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 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
438 / 331 / 123
Регистрация: 27.11.2014
Сообщений: 1,038
07.09.2015, 15:21 #9
Kuzia domovenok, эти Ваши бендеровцы разносят нас на олимпиадах по программированию в прах.
MansMI
1162 / 954 / 247
Регистрация: 08.01.2012
Сообщений: 3,491
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, спасибо за разъяснение!
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
07.09.2015, 17:33 #12
Цитата Сообщение от ture Посмотреть сообщение
Kuzia domovenok, эти Ваши бендеровцы разносят нас на олимпиадах по программированию в прах.
https://en.wikipedia.org/wiki/Intern...in_Informatics
дай пруф на то, что венгры где-то нас разносят в прах по программированию.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2015, 17:33
Привет! Вот еще темы с ответами:

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

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

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

Быстрая сортировка - C++
Помогите пожалуйста, при использовании алгоритма быстрой сортировки, конечный массив получается не отсортированным, хотя все операции...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.09.2015, 17:33
Ответ Создать тему
Опции темы

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