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

@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;
}

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

@GbaLog- · 04.08.2020, 08:00

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

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

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

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

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

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

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

Как именно Вы будете эту операцию производить?

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

@Annemesski · 04.08.2020, 08:16

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

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

И третий момент: не путайте понятия. Одно дело дать задание отсортировать и посмотреть как испытуемый с ним справится, а совсем другое научить сортировать, взять в качестве первого и самого легкого для объяснения принципа наглядный пузырек, очевидно, проще чем любой другой не имеющий таких вот простых, наглядных и повсеместно распространенных природных аналогов.

IGPIGP · 04.08.2020, 09:23

GbaLog-,

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]);
    }
  }
}

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

. Чтобы пресечь выход за границу массива нужно i<n-1 похоже. Или я неправ?

@GbaLog- · 04.08.2020, 09:31

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

Чтобы пресечь выход за границу массива нужно i<n-1 похоже. Или я неправ?

неправы, потому что индексы массивов начинаются с нуля, а n - это кол-во элементов в массиве.
соответственно первый невалидный элемент будет на arr[n], чего никогда не случится, потому что неравенство строгое.
как только i станет равным n - цикл остановится.
другое дело, что можно сделать в первом цикле i - 1, т.к. на этом шаге уже все числа будут отсортированы и последнее будет стоять на своём месте.

IGPIGP · 04.08.2020, 09:56

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

неправы,

Прав

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

если пузырёк барыня, то данный пузырек это она же но с выходом

У вас не пузырёк. Он делает лишние перестановки и похож лишь по количеству сравнений (порядка n²/2). По классике пузырёк меняется с соседом. Вот с geeksforgeeks чтобы долго не искать:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubbleSort(int arr[], int n) 
{ 
   int i, j; 
   bool swapped; 
   for (i = 0; i < n-1; i++) 
   { 
     swapped = false; 
     for (j = 0; j < n-i-1; j++) 
     { 
        if (arr[j] > arr[j+1]) 
        { 
           swap(arr[j], arr[j+1]); 
           swapped = true; 
        } 
     } 
  
     // IF no two elements were swapped by inner loop, then break 
     if (swapped == false) 
        break; 
   } 
}

IGPIGP · 04.08.2020, 09:57

у них там свой нестандартный своп по адресам был - поправил

@Annemesski · 04.08.2020, 09:57

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

другое дело, что можно сделать в первом цикле i - 1, т.к. на этом шаге уже все числа будут отсортированы и последнее будет стоять на своём месте.

Точнее: во вложенном цикле j имеет смысл инициализировать значением i + 1 ибо не имеет смысла выполнять сравнение if (arr[i] > arr[j]) при i == j, а тогда да: чтобы не было выхода за пределы массива внешний цикл треба запускать до i < n - 1

@GbaLog- · 04.08.2020, 09:59

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

У вас не пузырёк.

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

Вот с geeksforgeeks чтобы долго не искать

https://www.geeksforgeeks.org/bubble-sort/

C++
1
2
3
4
5
6
7
8
9
10
11
// A function to implement bubble sort  
void bubbleSort(int arr[], int n)  
{  
    int i, j;  
    for (i = 0; i < n-1; i++)      
      
    // Last i elements are already in place  
    for (j = 0; j < n-i-1; j++)  
        if (arr[j] > arr[j+1])  
            swap(&arr[j], &arr[j+1]);  
}

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

IGPIGP · 04.08.2020, 10:03

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

не понимаю, что вы тут хотите мне доказать.

что меняется сосед с соседом: arr[j] > arr[j+1] и это породило название. Пузырь всплывает меняясь местами с каплями над головой последовательно.

@GbaLog- · 04.08.2020, 10:08

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

что меняется сосед с соседом:arr[j] > arr[j+1] и это породило название.

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

IGPIGP · 04.08.2020, 11:54

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

хм. вы правы.

Я здесь вначале индексы попутал,
Потом скукожился и весь зачах.
А Заяц первым высказался круто,
Со светом истины в разверзнутых очах,
Морковью в седце и вилком надежды.
Замечу: он был прав не раз и прежде)

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

Ваш первый пример - это не сортировка пузырьком

Вот.

@alexu_007 · 05.08.2020, 07:51

Самое простое, сразу приходит в голову:

1. сравниваем 1-й и 2-й элементы массива, если второй меньше - меняем местами (если сортировка по возрастанию).
2. сравниваем 3-й элемент массива с 2-м и затем с первым, если 3-й меньше меняем местами.
3. и так далее до конца массива.

Если это и есть пузырёк, то вот он самый интуитивный алгоритм. Не надо путать с "человеческими" решениями. Человек просто разложит все предметы на земле, посмотрит на них сверху, выберет самый крупный и положит в конец, затем следующий и так далее. Компьютер не может "посмотреть сверху", он может либо пробежать из конца в конец, либо сравнить два соседних.

@Annemesski · 05.08.2020, 15:12

Не по теме:

IGPIGP,

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

Я здесь вначале индексы попутал...

неплохо, а теперь кодом )))

IGPIGP · 05.08.2020, 15:43

Не по теме:

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

неплохо, а теперь кодом )))

Не кодом единым жив алгоритм. Хотя код был:

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

По классике пузырёк меняется с соседом. Вот с geeksforgeeks чтобы долго не искать:

Кот Бегемот.

Новые блоги и статьи Все статьи Все блоги /
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .

@Annemesski 2689 / 1346 / 485 Регистрация: 08.11.2016 Сообщений: 3,734
	04.08.2020, 08:16
	Действительно, если сравнить сортировки выбором, вставками и пузырьком, то самой простой для понимания и реализации окажется сортировка выбором, но у пузырька есть серьезное преимущество - естесственность, можно сказать природная - на которую прямо ссылается само название алгоритма. Вот представьте что вы не знаете алгоритмов сортировок и вам сказали мол есть такой алгоритм: сортировка выбором - какие у Вас при этом мысли? Предположу что-то такое: что и по какому принципу выбираем и что с этим выбором делаем дальше? Для вставок, расчесок и прочего картина будет похожей - сплошные вопросы. А вот сказали: сортировка пузырьком, какие мысли? Думается что-то вроде: ага, пузырьки всплывают, потому что они легкие, ведь все же видели пузырьки, то как они себя ведут - процесс совершенно естественный известный и понятный. Другой момент рассуждать об этом с позиции постзнания, конечно логичнее и проще выбрать максимум или минимум и поместить его справа или слева чем долго и нудно ждать пока всплывет пузырек. И третий момент: не путайте понятия. Одно дело дать задание отсортировать и посмотреть как испытуемый с ним справится, а совсем другое научить сортировать, взять в качестве первого и самого легкого для объяснения принципа наглядный пузырек, очевидно, проще чем любой другой не имеющий таких вот простых, наглядных и повсеместно распространенных природных аналогов. 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9007 / 4708 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	04.08.2020, 09:57
	у них там свой нестандартный своп по адресам был - поправил 0

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,316
	05.08.2020, 07:51
	Самое простое, сразу приходит в голову: 1. сравниваем 1-й и 2-й элементы массива, если второй меньше - меняем местами (если сортировка по возрастанию). 2. сравниваем 3-й элемент массива с 2-м и затем с первым, если 3-й меньше меняем местами. 3. и так далее до конца массива. Если это и есть пузырёк, то вот он самый интуитивный алгоритм. Не надо путать с "человеческими" решениями. Человек просто разложит все предметы на земле, посмотрит на них сверху, выберет самый крупный и положит в конец, затем следующий и так далее. Компьютер не может "посмотреть сверху", он может либо пробежать из конца в конец, либо сравнить два соседних. 0