В программировании очень часто появляется потребность в упорядочивании коллекции данных. Будь то список учеников по алфавиту, сводные таблицы результативности, или еще какие-нибудь статистические данные. Да все что угодно можно упорядочить. Главное выбрать критерий по которому необходимо проводить сортировку. Наиболее распространена сортировка по возрастанию и убыванию значений, или сортировка по алфавиту.
Чтобы провести сортировку по определенному критерию, нужно понять алгоритм упорядочивания. Их много, одни быстры и сложны в написании, другие медленнее, но просты в реализации. В этой теме мы разберем два самых популярных метода сортировки — сортировка методом пузырька и сортировка методом Шелла. Самую эффективную и быструю сортировку рассмотрим после темы методов и рекурсии.
Сортировка методом пузырька, самая простая в реализации, но одна из самых долгих в исполнении, при самом худшем случае, при количестве элементов n, время выполнения сортировки будет n*n. Поэтому используется только в учебных целях и на практике почти никогда не применяется.
Python | Урок 9: Сортировка
Само название метода говорит о его способе реализации. Как самые большие пузыри опережая средние и маленькие пузырики в воде выходят на поверхность, так и в массиве — самые крупные значения опережают более меньшие числа.
Для того чтобы отсортировать по возрастанию, мы будем поочередно сравнивать пару элементов, и если левый элемент больше правого, то менять их местами. Рассмотрим на примере сортировки массива array по возрастанию:
int[] array = ;
Распишем трассировочную таблицу при каждой итерации сравнения:
Сравниваем элемент массива с индексом 0 поочередно со следующими элементами Шаг 1. 24 19 18 30 17 26 сравнение 24 и 19 19 24 18 30 17 26 обмен 24 19 Шаг 2. 19 24 18 30 17 26 сравнение 19 и 18 18 24 19 30 17 26 обмен 19 18 Шаг 3. 18 24 19 30 17 26 сравнение 18 и 30 18 24 19 30 17 26 не меняем Шаг 4. 18 24 19 30 17 26 сравнение 18 и 17 17 24 19 30 18 26 обмен 18 17 Шаг 5. 17 24 19 30 18 26 сравнение 17 и 26 17 24 19 30 18 26 не меняем Сравниваем элемент массива с индексом 1 поочередно со следующими элементами Шаг 6. 17 24 19 30 18 26 сравнение 24 и 19 17 19 24 30 18 26 обмен 24 19 Шаг 7. 17 19 24 30 18 26 сравнение 19 и 30 17 19 24 30 18 26 не меняем Шаг 8. 17 19 24 30 18 26 сравнение 19 и 18 17 18 24 30 19 26 обмен 19 18 Шаг 9. 17 18 24 30 19 26 сравнение 18 и 26 17 18 24 30 19 26 не меняем Сравниваем элемент массива с индексом 2 поочередно со следующими элементами Шаг 10. 17 18 24 30 19 26 сравнение 24 и 30 17 18 24 30 19 26 не меняем Шаг 11.
17 18 24 30 19 26 сравнение 24 и 19 17 18 19 30 24 26 обмен 24 19 Шаг 12. 17 18 19 30 24 26 сравнение 19 и 26 17 18 19 30 24 26 не меняем Сравниваем элемент массива с индексом 3 поочередно со следующими элементами Шаг 13. 17 18 19 30 24 26 сравнение 30 и 24 17 18 19 24 30 26 обмен 30 24 Шаг 14. 17 18 19 24 30 26 сравнение 24 и 26 17 18 19 24 30 26 не меняем Сравниваем элемент массива с индексом 4 поочередно со следующими элементами Шаг 15.
Язык C++ с нуля | #32 Сортировка массива в c++
17 18 19 24 30 26 сравнение 30 и 26 17 18 19 24 26 30 обмен 30 26
//Листинг решения пузырьковой сортировки using System; namespace Serg40in < class Program < static void Main() < int[] array = < 24, 19, 18, 30, 17, 26 >; for (int i = 0; i < array.Length — 1; i++) for (int j = i + 1; j < array.Length; j++) if (array[i] >array[j]) < int temp = array[i]; array[i] = array[j]; array[j] = temp; >Console.Write(string.Join(» «, array)); Console.ReadKey(); > > >
Сортировка методом Шелла, также простая в реализации, но она менее эффективная чем Q-сортировка на больших последовательностях. А также, может быть дольше в исполнении по сравнению с пузырьковой сортировкой на маленьких массивах.
Используется в практических целях, так как худший вариант исполнения будет гарантированно быстрее худшего варианта быстрой сортировки. Алгоритм этой реализации состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной пузырьковой сортировкой). Рассмотрим на примере сортировки массива array по возрастанию с такими же значения как и в пузырьковой сортировке:
int[] array = ;
Распишем трассировочную таблицу при каждой итерации сравнения:
Расстояние между элементами = 3 Сравниваем элемент массива с индексом 0 поочередно со следующими элементами Шаг 1. 24 19 18 30 17 26 Сравниваем 24 и 30 24 19 18 30 17 26 не меняем Сравниваем элемент массива с индексом 1 поочередно со следующими элементами Шаг 2. 24 19 18 30 17 26 Сравниваем 19 и 17 24 17 18 30 19 26 меняем 19 и 17 Сравниваем элемент массива с индексом 2 поочередно со следующими элементами Шаг 3. 24 17 18 30 19 26 Сравниваем 18 и 26 24 17 18 30 19 26 не меняем Расстояние между элементами = 1 Сравниваем элемент массива с индексом 0 поочередно со следующими элементами Шаг 4. 24 17 18 30 19 26 Сравниваем 24 и 17 17 24 18 30 19 26 меняем 24 и 17 Шаг 5. 17 24 18 30 19 26 Сравниваем 17 и 18 17 24 18 30 19 26 не меняем Шаг 6. 17 24 18 30 19 26 Сравниваем 17 и 30 17 24 18 30 19 26 не меняем Шаг 7. 17 24 18 30 19 26 Сравниваем 17 и 19 17 24 18 30 19 26 не меняем Шаг 8. 17 24 18 30 19 26 Сравниваем 17 и 26 17 24 18 30 19 26 не меняем Сравниваем элемент массива с индексом 1 поочередно со следующими элементами Шаг 9. 17 24 18 30 19 26 Сравниваем 24 и 18 17 18 24 30 19 26 меняем 24 и 18 Шаг 10. 17 18 24 30 19 26 Сравниваем 18 и 30 17 18 24 30 19 26 не меняем Шаг 11.
17 18 24 30 19 26 Сравниваем 18 и 19 17 18 24 30 19 26 не меняем Шаг 12. 17 18 24 30 19 26 Сравниваем 18 и 26 17 18 24 30 19 26 не меняем Сравниваем элемент массива с индексом 2 поочередно со следующими элементами Шаг 13. 17 18 24 30 19 26 Сравниваем 24 и 30 17 18 24 30 19 26 не меняем Шаг 14. 17 18 24 30 19 26 Сравниваем 24 и 19 17 18 19 30 24 26 меняем 24 и 19 Шаг 15.
17 18 19 30 24 26 Сравниваем 19 и 26 17 18 19 30 24 26 не меняем Сравниваем элемент массива с индексом 3 поочередно со следующими элементами Шаг 16. 17 18 19 30 24 26 Сравниваем 30 и 24 17 18 19 24 30 26 меняем 30 и 24 Шаг 17. 17 18 19 24 30 26 Сравниваем 24 и 26 17 18 19 24 30 26 не меняем Сравниваем элемент массива с индексом 4 поочередно со следующими элементами Шаг 18. 17 18 19 24 30 26 Сравниваем 30 и 26 17 18 19 24 26 30 меняем 30 и 26
//Листинг решения сортировки методом Шелла using System; namespace Serg40in < class Program < static void Main() < int[] array = < 24, 19, 18, 30, 17, 26 >; int size = array.Length; for (int i = size / 2; i > 0; i /= 2) for (int j = 0; j < size; j++) for (int k = j + i; k < size; k += i) if (array[j] >array[k]) < int temp = array[k]; array[k] = array[j]; array[j] = temp; >Console.Write(string.Join(» «, array)); Console.ReadKey(); > > >
Более подробно о сортировках:
- https://ru.wikipedia.org/wiki/Сортировка_пузырьком
- https://ru.wikipedia.org/wiki/Сортировка_Шелла
- https://ru.wikipedia.org/wiki/Быстрая_сортировка
- https://ru.wikipedia.org/wiki/Сортировка_перемешиванием
- https://ru.wikipedia.org/wiki/Пирамидальная_сортировка
Array_37
С консоли дан неупорядоченный массив данных роста учеников в сантиметрах. А также рост нового ученика. Напишите программу, которая упорядочит значения по убыванию и укажет на каком месте расположится новый ученик в шеренге по росту на уроке физкультуры. Не использовать метод Array.Sort!
Пример использования: Выходные данные 1: Введите рост учеников, перечисляйте значения через пробел. Входные данные 1: 164 150 172 182 169 190 184 164 162 176 181 179 182 Выходные данные 1: Упорядоченный по росту массив: Выходные данные 1: 190 184 182 182 181 179 176 172 169 164 164 162 150 Выходные данные 1: Введите рост нового ученика Входные данные 1: 178 Выходные данные 1: Позиция в строю на №7 Пример использования: Выходные данные 2: Введите рост учеников, перечисляйте значения через пробел.
Входные данные 2: 164 150 172 182 169 190 184 164 162 176 181 179 182 Выходные данные 2: Упорядоченный по росту массив: Выходные данные 2: 190 184 182 182 181 179 176 172 169 164 164 162 150 Выходные данные 2: Введите рост нового ученика Входные данные 2: 199 Выходные данные 2: Позиция в строю на №1 Пример использования: Выходные данные 3: Введите рост учеников, перечисляйте значения через пробел. Входные данные 3: 164 150 172 182 169 190 184 164 162 176 181 179 182 Выходные данные 3: Упорядоченный по росту массив: Выходные данные 3: 190 184 182 182 181 179 176 172 169 164 164 162 150 Выходные данные 3: Введите рост нового ученика Входные данные 3: 145 Выходные данные 3: Позиция в строю на №14 Пример использования: Выходные данные 4: Введите рост учеников, перечисляйте значения через пробел.
Входные данные 4: 164 150 172 182 169 190 184 164 162 176 181 179 182 Выходные данные 4: Упорядоченный по росту массив: Выходные данные 4: 190 184 182 182 181 179 176 172 169 164 164 162 150 Выходные данные 4: Введите рост нового ученика Входные данные 4: 79i Выходные данные 4: Не корректный рост нового ученика! Пример использования: Выходные данные 5: Введите числовой массив, перечисляйте элементы через пробел.
Входные данные 5: f2 ret2 oo2 Выходные данные 5: Массив введен не корректно! Пример использования: Выходные данные 6: Введите числовой массив, перечисляйте элементы через пробел. Входные данные 6: Выходные данные 6: Ошибка ввода. Пустая строка
Задача очень проста в решении, если не отлавливать критические ситуации представленные в примерах использования.
Ошибки при пустом вводе и некорректном значении мы уже умеем обрабатывать.
Принимаем строку от пользователя, проверим его на пустое значение, если строка равна string.Empty, то завершим приложение с выводом сообщения, что был пустой ввод. Иначе, в безопасной конструкции try/catch попробуем преобразовать строку в числовой массив, если произойдет ошибка — то сообщим о не корректной конвертации и выйдем из приложения. Иначе, отсортируем массив по убыванию, где в начале массива будут находиться максимальные значения и убывать по мере увеличения индекса элемента. Сортировать будет методом пузырька.
Далее, приглашаем ввести числовое значение роста ученика, проверим его на правильный ввод, и если будет ошибка преобразования — выйдем из программы с сообщением о не корректном вводе числа. Иначе, организуем цикл for для перебора всего массива упорядоченного массива, где в теле, создадим условие, в котором спросим, если рост больше текущего элемента массива, то закончим цикл и сделаем вывод в консоль номер позиции ученика в строю — переменная цикла плюс единица.
Но в этой задаче может быть ситуация, когда рост ученика будет меньше роста всех учеников, поэтому нам этот момент необходимо тоже учитывать.
//Листинг решения задачи array_37 using System; namespace Serg40in < class Program < static void Main() < Console.WriteLine(«Введите рост учеников, перечисляйте значения через пробел.»); string input = Console.ReadLine().Trim(); if (input != «») < int[] array; try < array = Array.ConvertAll(input.Split(‘ ‘), int.Parse); >catch < Console.WriteLine(«Массив введен не корректно!»); Console.ReadKey(); return; >for (int i = 0; i < array.Length — 1; i++) for (int j = i + 1; j < array.Length; j++) if (array[i] < array[j]) < int temp = array[i]; array[i] = array[j]; array[j] = temp; >Console.WriteLine(«Упорядоченный по росту массив:n» + string.Join(» «, array)); Console.WriteLine(«Введите рост нового ученика»); if (!int.TryParse(Console.ReadLine().Trim(), out int heigth)) < Console.WriteLine(«Не корректный рост нового ученика!»); Console.ReadKey(); return; >for (int i = 0; i < array.Length; i++) < if (heigth >array[i]) < Console.WriteLine(«Позиция в строю на №» + (i + 1)); Console.ReadKey(); return; >> Console.WriteLine(«Позиция в строю на №» + (array.Length + 1)); > else Console.WriteLine(«Ошибка ввода. Пустая строка»); Console.ReadKey(); > > >
Array_38
С консоли дан неупорядоченный список фамилий студентов группы. Упорядочить список по фамилии. Не использовать метод Array.Sort!
Пример использования: Выходные данные 1: Введите фамилии студентов, перечисляйте значения через пробел. Входные данные 2: Сорокин Прозоров Доценко Цецхладзе Соврокин Рассолов Соарокин Выходные данные 1: Cписок фамилий по алфавиту: Выходные данные 1: Доценко Выходные данные 1: Прозоров Выходные данные 1: Рассолов Выходные данные 1: Соарокин Выходные данные 1: Соврокин Выходные данные 1: Сорокин Выходные данные 1: Цецхладзе Пример использования: Выходные данные 2: Введите числовой массив, перечисляйте элементы через пробел.
Входные данные 2: Выходные данные 2: Ошибка ввода. Пустая строка
Принимаем строку от пользователя, проверим его на пустое значение, если строка равна string.Empty, то завершим приложение с выводом сообщения, что был пустой ввод.
Иначе, сортировку массива методом пузырька, где в теле внутреннего цикла for будем сравнивать результат выполнении функции string.Compare(string, string). Этом метод очень удобен для выбора значения, которое имеет ранее расположение в алфавитном порядке из двух представленных. Возвратом метода будет значения: -1, 0, 1. Где если первый параметр стоит раньше второго вернется -1, если равен — вернется ноль, иначе вернется 1. Что нам собственно и нужно. Если метод string.Compare(array[i], array[j]) вернет единицу, то сделай обмен значений.
После двух циклов сделаем вывод упорядоченного массива фамилий при помощи string.Join().
//Листинг решения задачи array_38 using System; namespace Serg40in < class Program < static void Main() < Console.WriteLine(«Введите фамилии студентов, перечисляйте значения через пробел.»); string input = Console.ReadLine().Trim(); if (input != «») < string[] array = input.Split(‘ ‘); for(int i = 0; i < array.Length — 1; i++) for (int j = i + 1; j < array.Length; j++) if (string.Compare(array[i], array[j]) >0) < string temp = array[i]; array[i] = array[j]; array[j] = temp; >Console.WriteLine(«Cписок фамилий по алфавиту:n» + string.Join(«n», array)); > else Console.WriteLine(«Ошибка ввода. Пустая строка»); Console.ReadKey(); > > >
Ниже приведены задания по теме для самостоятельного решения:
- При решении не использовать пользовательские методы и методы класса Array, кроме ConvertAll;
- Программа не должна критически останавливаться с ошибкой конвертирования данных;
- Интерфейс консольного приложения обязан быть опрятным и дружелюбным!
Home_154. Даны два неупорядоченных массива, но элементы связанны индексами. В первом массиве указаны фамилии и инициалы во втором массиве стоят оценки по информатике каждого ученика. Вывести оценочную ведомость учеников:
а). упорядоченного по фамилии;
б). упорядоченного по оценкам.
Home_155. Дана массив из 200 случайных значений. Упорядочить его следующим образом:
а). первая сотня элементов по убыванию, вторая сотня по возрастанию;
б). нечетный десяток элементов по убыванию, четный десяток по возрастанию.
Источник: serg40in.ru
Сортировка массива по возрастанию — Pascal ABC
Дан массив a[0..n-1] из n чисел 0 и 1. Требуется разделить элементы друг от друга так, чтобы сначала оказались все 0, а в конце 1. Преобразовать текст решения на псевдокоде в программу на Паскале.
int[] sort(int[] a): int left = 0, right = n — 1 while (left < right) while (a[left] == 0 and left < right) left++ while (a[right] == 1 and left < right) right— if (left < right) swap(a[left], a[right]) left++ right— return a
Код к задаче: «Сортировка массива по возрастанию»
Листинг программы
const n = 10; var a: array[1..n] of integer; i, j, temp: integer; begin randomize; writeln(‘Исходный массив: ‘); for i := 1 to n do begin a[i] := random(2); write(a[i]:3); end; writeln; for i := 1 to n — 1 do for j := i + 1 to n do if a[i] > a[j] then begin temp := a[i]; a[i] := a[j]; a[j] := temp; end; writeln(‘Отсортированный массив: ‘); for i := 1 to n do write(a[i]:3); end.
Источник: studassistent.ru
Сортировка массива в порядке возрастания в C++
В этом посте мы обсудим, как отсортировать массив в порядке возрастания в C++.
Чтобы отсортировать массив в естественном/возрастающем порядке, вы можете использовать std::sort алгоритм, предоставляемый STL. Он сортирует элементы контейнера в диапазоне, указанном указанными итераторами. Поскольку итераторы — это не что иное, как обобщение указателей, вы можете передать указатель на первый элемент массива и (1+) последний элемент массива для сортировки всего массива в стиле C.
int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ;
std :: sort ( arr , arr + n ) ;
for ( int const
std :: cout << i << ‘ ‘ ;
результат:
2 3 4 5 7
Стоит отметить, что std::sort не дает стабильной сортировки. Это означает, что относительный порядок одинаковых элементов не будет сохранен в отсортированной последовательности. Рекомендуемый подход к получению стабильной сортировки заключается в использовании std::stable_sort алгоритм.
Кроме того, приведенный выше код требует, чтобы вы заранее знали размер массива. Можно пропустить это в C++11 используя новые std::begin а также std::end функции, которые перегружены для массивов в стиле C:
Источник: www.techiedelight.com