Как можно отсортировать по другому?

@Vardan · Регистрация: 25.06.2020

Студворк — интернет-сервис помощи студентам

Как написать сортирующий алгоритм в ручную чтобы не использовать std::sort ???
какие варианты есть?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
 
void printSorted(double* arr, int size)
{
    std::sort(arr, arr + size);
    for(int i = 0; i < size; ++i)
    std::cout << arr[i] << " ";
}
 
int main()
{
    int n;
    std::cin >> n; 
    double* arr = new double[n];
    for(int i = 0; i < n; ++i) {
      std::cin >> arr[i];
    }
    printSorted(arr, n);
 
    delete [] arr;
    return 0;
}

сортировка массива по возрастанию...

@DrOffset · 03.08.2020, 15:50

Сообщение от Vardan

какие варианты есть?

Если вы учитесь и впервые с этим столкнулись, то используйте пузырьковую сортировку. Ее, в основном, применяются при обучении. Я бы даже сказал, что вы, если подумаете, сможете ее "изобрести" самостоятельно без какой либо помощи извне.

@avgoor · 03.08.2020, 17:38

Сообщение от DrOffset

то используйте пузырьковую сортировку

Ну, вот, почему? Мне всегда был интересен ответ на этот вопрос. Сначала в школе, потом в институте. Поясню:
Попросите Равшана с Джамшутом разложить лопаты по размеру. Вы считаете, что они будут делать это не выбором или вставками, а пузырьком?
Т.е. пузырек - не интуитивный алгоритм, для которого, к тому же сложнее (по сравнению с выбором или вставками) доказать валидность.
Почему во всех книжках пишут, мол, он самый простой, с него и начнем. Может Вы знаете? (Мне правда интересно)

@GbaLog- · 03.08.2020, 17:56

Сообщение от avgoor

Почему во всех книжках пишут, мол, он самый простой, с него и начнем.

видимо, потому что её легче всего реализовать.
для примера из моего учебного проекта.

bubble sort

C++
1
2
3
4
5
6
7
8
9
10
11
void bubbleSort(int * arr, int n)
{
  for (int i = 0; i < n; ++i)
  {
    for (int j = i; j < n; ++j)
    {
      if (arr[i] > arr[j])
        swap(arr[i], arr[j]);
    }
  }
}

insert sort

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insertionSort(int * arr, int n)
{
  for (int i = 1; i < n; ++i)
  {
    int j = i - 1;
    int k = arr[i];
 
    while (j >= 0 && arr[j] > k)
    {
      arr[j + 1] = arr[j];
      --j;
    }
 
    arr[j + 1] = k;
  }
}

selection sort

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void selectionSort(int * arr, int n)
{
  int min;
  for (int i = 0; i < n - 1; ++i)
  {
    min = i;
    for (int j = i + 1; j < n; ++j)
    {
      if (arr[min] > arr[j])
        min = j;
    }
    swap(arr[min], arr[i]);
  }
}

лично для меня легче всего из них воспринимается именно сортировка пузырьком.

@avgoor · 03.08.2020, 18:11

Сообщение от GbaLog-

видимо, потому что её легче всего реализовать.
для примера из моего учебного проекта.

Один проход пузырька эквивалентен одному проходу вставки, с точностью до пределов:

C++
1
2
3
4
5
6
7
8
9
10
11
void NOTbubbleSortBUTInsertionSort(int* arr, int n)
{
    for (int i = 1; i < n; ++i)
    {
        for (int j = i - 1; j > 0 ; --j)
        {
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
    }
}

(Не проверял, мог ошибиться, но смысл тот понятен)

Добавлено через 4 минуты

Сообщение от GbaLog-

лично для меня легче всего из них воспринимается именно сортировка пузырьком.

Попросите ребенка пяти лет разложить кубики по размеру. Как он это сделает? Вставкой или выбором. Я об этом пишу. Так то - ребенок 5 лет, а мы об алгоритмах

@DrOffset · 03.08.2020, 18:47

Сообщение от avgoor

Может Вы знаете? (Мне правда интересно)

Давным давно, когда я только учился, именно эту сортировку я написал на интуиции, никуда не подглядывая. Чуть позже, когда я уже ознакомился с ней в учебнике, лично для меня как-то естественным образом стало понятно, почему она используется для обучения. Раз мне она показалась самоочевидной настолько, что я фактически сам для себя ее придумал. Возможно на самом деле я не прав, но так сложилось исторически

@avgoor · 03.08.2020, 18:53

DrOffset, А как Вы к ней пришли? Мне именно это и интересно.
Вот, допустим, принес я домой стопку книг по программированию. Мне как-то надо засунуть их в шкаф (пустой, иначе вставка - очевидна). И я хочу по алфавиту. Какие рассуждения приведут к пузырьку? Вставки и выбор - очевидны. Пузырек для меня - нонсенс.

@DrOffset · 03.08.2020, 18:56

Сообщение от avgoor

А как Вы к ней пришли? Мне именно это и интересно.

Это сейчас трудновато будет вспомнить, за давностью лет.
Как-то естественно пришел, без "напряга".

@GbaLog- · 03.08.2020, 19:08

Сообщение от avgoor

Один проход пузырька эквивалентен одному проходу вставки, с точностью до пределов

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

Кликните здесь для просмотра всего текста

для сравнения я проверил и на моём ПК ваша версия(исправленная) на 100'000 элементов выполняется 5.4сек в релизе.
моя версия выполняется 1.5сек.
это среднее из 3-х запусков.
элементы я рандомизировал по типу (10, 1, 9, 2, 8, 3...).

C++
1
2
3
4
5
6
7
for (int i = 1; i < n; ++i)
{
  for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; --j)
  {
    swap(arr[j], arr[j + 1]);
  }
}

Сообщение от avgoor

Попросите ребенка пяти лет разложить кубики по размеру. Как он это сделает?

это понятно. я же говорю, что пузырёк просто легче в понимании реализации в коде, а не алгоритма.

@avgoor · 03.08.2020, 19:18

Сообщение от DrOffset

Это сейчас трудновато будет вспомнить, за давностью лет.
Как-то естественно пришел, без "напряга".

Ну вот, опять. Так и не узнаю я сакральный смысл "простоты" пузырьковой сортировки. Хотя, ставлю бутылку лагавулина против бутылки "портвейна" 777, что если Вас вдруг попросить, допустим, разложить по порядку (т.е. по возрастанию длины) какие-нибудь, допустим, винтики - последнее о чем Вы подумаете - пузырек.

@DrOffset · 03.08.2020, 19:22

avgoor, даже если вы окажетесь правы, то нынешний я - это совсем не то же самое, что тогда

Сравнивать это не очень корректно.

@avgoor · 03.08.2020, 19:24

Сообщение от GbaLog-

в вашем примере как минимум 2 ошибки.

Дык, я ж писал:

Сообщение от avgoor

Не проверял, мог ошибиться, но смысл тот понятен

По сути-то есть претензии?

Сообщение от GbaLog-

я же говорю, что пузырёк просто легче в понимании реализации в коде, а не алгоритма.

А чем алгоритм принципиально отличается от реализации? Код - всего лишь формальное описание алгоритма на формальном языке.

Добавлено через 1 минуту
DrOffset, Без рефлексии (во всех смыслах) в нашем деле - никуда, так что - не принимается

Добавлено через 15 секунд
DrOffset, Без рефлексии (во всех смыслах) в нашем деле - никуда, так что - не принимается

@DrOffset · 03.08.2020, 19:26

Сообщение от avgoor

Без рефлексии (во всех смыслах) в нашем деле - никуда, так что - не принимается

Опять же, если бы я что-то кому-то доказывал, то "не принимается" было бы уместно, а так, я просто поделился воспоминаниями на тему.

@avgoor · 03.08.2020, 19:33

DrOffset, ну, доказывали или нет - это вторично. Реплику/аргумент в разговоре отвергнуть можно всегда

@GbaLog- · 03.08.2020, 20:11

Сообщение от avgoor

А чем алгоритм принципиально отличается от реализации?

ну вам же DrOffset сказал, что эта сортировка пишется интуитивно.
одно дело алгоритм из жизни перенести в код, другое дело придумать свой.
и при придумывании своего ты думаешь, как код написать, а не как бы ты в жизни этот вопрос решал.
и на ум первым приходит вариант с двумя циклами.
у меня так было, у DrOffset так же. возможно, у этого и нет какого-то "научного" объяснения.

IGPIGP · 03.08.2020, 20:37

avgoor, винтики и книжки перемещаются вместе со своим "местом". Для контейнера список, это естественный способ переупорядочивания. Плохо то, что список неинтуитивен для новичков по сравнению с массивом. А в массиве элементы копируются из одного места в другое. А пузырёк и вправду не так интуитивен как вставки, хотя вполне интуитивен.
Множество для новичка - трепанация черепа. А сортировка состоит в том чтобы ничего не делать. Тоже взрыв мозга.
Чем интуитивнее алгоритм тем он, как правило, медленнее. Вот пример:

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int ar[]={2,5,4,3,6,2,8} ;
    while (!is_sorted(ar, ar+7))random_shuffle(ar, ar+7);//пинать до победы
    for(int i=0; i<7; ++i)cout<<ar[i]<<' ';
    return 0;
}

@avgoor · 03.08.2020, 20:41

Сообщение от GbaLog-

ну вам же DrOffset сказал, что эта сортировка пишется интуитивно.

Ну, он мне сказал, что он ее написал интуитивно (чем, в общем, отказался озвучить ход своих соображений). Я спрашиваю как раз о ходе рассуждений: как именно и из каких соображений вы(он) пришли к этой сортировке.
Вот есть у нас 10 лопат. Как повесить их на крючки (у нас есть крючки для лопат

, (у каждой лопаты есть ушко на ручке), чтобы они висели, скажем, по возрастанию массы?
Как именно Вы будете эту операцию производить? Вы, правда, сначала развесите все лопаты на крючки, а потом будете менять соседние, пока не останется инверсий (в чем метод пузырька и состоит)?
Или все-таки из оставшихся лопат выберете лопату минимальной массы и повесите ее на следующий крючёк (выбор), или просто берете лопату из кучи и впихиваете ее на свое место (вставка)?

В какой жизненной ситуации индивидуум, будучи не знаком с программированием вообще, применит пузырек вместо вставки или выбора?

@DrOffset · 03.08.2020, 20:56

Сообщение от avgoor

Как именно Вы будете эту операцию производить? Вы, правда, сначала развесите все лопаты на крючки, а потом будете менять соседние, пока не останется инверсий (в чем метод пузырька и состоит)?

Это так абсурдно звучит только если мы их взвешивать хотим, а если, например хотим отсортировать по длине черенка, то лопаты и правда лучше сначала развесить, т.к. в сравнении разность длин, особенно если она незначительно отличается, будет виднее.

@zayats80888 · 03.08.2020, 21:41

Сообщение от GbaLog-

видимо, потому что её легче всего реализовать.
для примера из моего учебного проекта.

Ваш первый пример - это не сортировка пузырьком, скорее вариант сортировки выбором.
Поэтому соглашусь с avgoor, интуитивно она самая понятная и простая.

IGPIGP · 03.08.2020, 23:01

Сообщение от zayats80888

Поэтому соглашусь с avgoor, интуитивно она самая понятная и простая.

Сортировка выбором, действительно, достаточно очевидна. И всё же базовый математический уровень должен быть. Без умения мыслить мало-мальски обобщенно всё теряет смысл. Я помню, принцип матиндукции нам показывали вначале 6 класса. Это потрясающе для человека в 13 лет узнать о таком способе обобщения. А "всплытие" можно попытаться объяснить как можно проще. Оно вполне очевидно.
Какое максимальное "разупорядочивание (количество ходов-обменов для постановки на своё окончательное место)" может быть встречено для одной частицы в системе с правилом "возрастание слева-на-право"? Очевидно - это случай для минимальной частицы находящейся в крайнем правом положении. Для перестановки её в крайне левое положения ряда из n частиц требуется n-1 обменов. Если проходя по ряду мы будет менять каждую "неправильную" пару местами, то помимо продвижения самой неудачной (считаем что у нас именно такой случай), мы двигаем и все другие частицы, которые имеют "плохое" соседство. Поскольку все частицы относительно перестановки равноправны то из того что самая минимальная находившаяся справа (самая плохая и трудоёмкая) частица проследует на крайне левое место, следует, что любая другая частица займет наиболее левое место из возможных. Это потому, что у любой такой частицы путь меньше, а количество акций "контроаль-перстановка (если нужно) пары" такое же как и у самой плохой, - то есть, по крайней мере не меньше чем может потребоваться в худшем случае для данной выбранной частицы.
Отсюда следует, что количество работы при данной сортировке практически не зависит от степени упорядоченности стартового набора. Что грустно, но понятно. Однако, в принципе, пузырёк вполне очевиден. Стакан газированной воды прозрачен и нагляден.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@avgoor 1550 / 877 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	03.08.2020, 18:53
	DrOffset, А как Вы к ней пришли? Мне именно это и интересно. Вот, допустим, принес я домой стопку книг по программированию. Мне как-то надо засунуть их в шкаф (пустой, иначе вставка - очевидна). И я хочу по алфавиту. Какие рассуждения приведут к пузырьку? Вставки и выбор - очевидны. Пузырек для меня - нонсенс. 0

@DrOffset 19500 / 10105 / 2461 Регистрация: 30.01.2014 Сообщений: 17,816
	03.08.2020, 19:22
	avgoor, даже если вы окажетесь правы, то нынешний я - это совсем не то же самое, что тогда Сравнивать это не очень корректно. 0

@avgoor 1550 / 877 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	03.08.2020, 19:33
	DrOffset, ну, доказывали или нет - это вторично. Реплику/аргумент в разговоре отвергнуть можно всегда 0