Сортировка пузырьком
И дея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.
Отсортируем массив <1, 5, 2, 7, 6, 3>
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
1, 2, 5, 7, 6, 3
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
1, 2, 5, 6, 7, 3
3 нарушает порядок, меняем местами с 7
1, 2, 5, 6, 3, 7
Возвращаемся к началу массива и проделываем то же самое
1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7
Говорят, что это похоже на "всплытие" более "лёгких" элементов, как пузырьков, отчего алгоритм и получил такое название.
Этот алгоритм всегда будет делать (n-1) 2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1) 2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.
Пусть нужно отсортировать массив 1, 2, 4, 3
1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
После того, как были поменяны местами элемента a[2] и a[3] нет больше необходимости проходить этот участок массива. Примем это во внимание и переделаем алгоритм
Ещё одна реализация
В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.
В этом случае сложность также порядка n 2 , но в случае отсортированного массива будет всего один проход.
Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа void. Так как тип переменной не известен, то нужно будет дополнительно передавать размер одного элемента массива и функцию сравнения.
Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.
Теперь с помощью этих функций можно сортировать массивы любого типа, например
Сортировка многомерного массива
С ортировка статического многомерного массива по существу не отличается от сортировки одномерного. Можно воспользоваться тем свойством, что статический одномерный и многомерный массивы имеют одинаковое представление в памяти.
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
Во-вторых, можно сначала переместить массив в одномерный, отсортировать одномерный массив, после чего переместить его обратно в двумерный.
Если вас смущает эта функция, то воспользуйтесь типизированной. Вызов, из предыдущего примера
Я должен отсортировать матрицу по столбцу; В качестве входных данных у меня есть одномерный массив и O преобразовать его в матрицу:
Первый элемент в столбце — это значение, а второй — количество появлений. Я должен отсортировать их по значению (по первому столбцу). Это то, что я пробовал до сих пор.
но вывод для этого кода:
Решение
Вам нужно две петли для сортировки. Я считаю, что вы не реализуете это правильно, потому что приведенная ниже демонстрация показывает, что это работает.
Хотите улучшить этот вопрос? Update the question so it’s on-topic for Stack Overflow на русском.
Закрыт 1 год назад .
Здравствуйте. Возникла проблема при сортировке двумерного массива по столбцам. По строках сделал, по столбцам не получается.
Должно получится что-то типа этого:
2 ответа 2
Сортируете все элементы матрицы (как одномерный массив), а потом заполняете из него (отсортированного одномерного массива) матрицу по столбцам (в примере — по три элемента на столбец).
Но это исходя из примера. Ещё вашу формулировку (не глядя на пример) можно понять как сортировка каждого столбца в отдельности, тогда по другому надо делать.
Загрузка...
