В статье рассмотрены одни из самых популярных алгоритмов сортировки для массивов, применяемых как практически, так и в учебных целях. Сразу хочу оговориться, что все рассмотренные алгоритмы медленнее, чем метод классической сортировки массива через список значений, но тем не менее, заслуживают внимания. Текста получается много, поэтому по каждому алгоритму описываю самое основное.
1.Алгоритм "Сортировка выбором".
Является одним из самых простых алгоритмов сортировки массива. Смысл в том, чтобы идти по массиву и каждый раз искать минимальный элемент массива, обменивая его с начальным элементом неотсортированной части массива. На небольших массивах может оказаться даже эффективнее, чем более сложные алгоритмы сортировки, но в любом случае проигрывает на больших массивах. Число обменов элементов по сравнению с "пузырьковым" алгоритмом N/2, где N - число элементов массива.
Алгоритм:
1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Опять ищем минимальный элемент в неотсортированной части массива
4. Меняем местами уже второй элемент массива и минимальный найденный, потому как первый элемент массива является отсортированной частью.
5. Ищем минимальные значения и меняем местами элементы,пока массив не будет отсортирован до конца.
//Сортировка выбором {--- Функция СортировкаВыбором(Знач Массив) Мин = 0; Для i = 0 По Массив.ВГраница() Цикл Мин = i; Для j = i + 1 ПО Массив.ВГраница() Цикл //Ищем минимальный элемент в массиве Если Массив[j] < Массив[Мин] Тогда Мин = j; КонецЕсли; КонецЦикла; Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем. Продолжить; КонецЕсли; Смена = Массив[i]; //Производим замену элементов массива. Массив[i] = Массив[Мин]; Массив[Мин] = Смена; КонецЦикла; Возврат Массив; КонецФункции
2.Алгоритм "Сортировка пузырьком".
Пожалуй самый известный алгоритм, применяемый в учебных целях, для практического же применения является слишком медленным. Алгоритм лежит в основе более сложных алгоритмов: "Шейкерная сортировка", "Пирамидальная сортировка", "Быстрая сортировка". Примечательно то, что один из самых быстрых алгоритмов "Быстрый алгоритм" был разработан путем модернизации одного из самых худших алгоритмов "Сортировки пузырьком"."Быстрая" и "Шейкерная" сортировки будут рассмотрены далее. Смысл алгоритма заключается в том, что самые "легкие" элементы массива как бы "всплывают" , а самые "тяжелые" "тонут". Отсюда и название "Сортировка пузырьком"
Алгоритм:
1. Каждый элемент массива сравнивается с последующим и если элемент[i] > элемент происходит замена. Таким образом самые "легкие" элементы "всплывают" - перемещаются к началу списка,а самые тяжелые "тонут" - перемещаются к концу.
2. Повторяем Шаг 1 n-1 раз, где n - Массив.Количество ().
//Сортировка пузырьком {--- Функция СортировкаПузырьком(Знач Массив) Для i = 0 По Массив.ВГраница() Цикл Для j = 0 ПО Массив.Вграница() - i - 1 Цикл Если Массив[j] > Массив Тогда Замена = Массив[j]; Массив[j] = Массив; Массив = Замена; КонецЕсли; КонецЦикла; КонецЦикла; Возврат Массив; КонецФункции //---}
3.Алгоритм "Шейкерная сортировка"(Сортировка перемешиванием,Двунаправленная пузырьковая сортировка).
Алгоритм представляет собой одну из версий предыдущей сортировки - "сортировки пузырьком". Главное отличие в том, что в классической сортировке пузырьком происходит однонаправленное движение элементов снизу - вверх, то в шейкерной сортировке сначало происходит движение снизу-вверху, а затем сверху-вниз.
Алгоритм такой же, что и у пузырьковой сортировки + добавляется цикл пробега сверху-вниз.
В приведенном ниже примере, есть усовершенствование в шейкерной сортировке. В отличие от классической, используется в 2 раза меньше итераций.
//Сортировка перемешивание (Шейкер-Сортировка) {--- Функция СортировкаПеремешиванием(Знач Массив) Для i = 0 ПО Массив.ВГраница()/2 Цикл нИтер = 0; конИтер = Массив.ВГраница(); Пока нИтер Массив[нИтер+1] Тогда Замена = Массив[нИтер]; Массив[нИтер] = Массив[нИтер + 1]; Массив[нИтер + 1] = Замена; КонецЕсли; нИтер = нИтер + 1;//Двигаем позицию на шаг вперед //Проходим с конца Если Массив[конИтер - 1] > Массив[конИтер] Тогда Замена = Массив[конИтер - 1]; Массив[конИтер-1] = Массив[конИтер]; Массив[конИтер] = Замена; КонецЕсли; конИтер = конИтер - 1;//Двигаем позицию на шаг назад КонецЦикла; КонецЦикла; Возврат Массив; КонецФункции //---}
4. Алгоритм "Гномья сортировка".
Алгоритм так странно назван благодаря голландскому ученому Дику Груну.
Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Дик Грун
Вот собственно и все описание алгоритма "Гномья сортировка". Что интересно, алгоритм не содержит вложенных циклов, а сортирует весь массив за один проход.
//Гномья сортировка {--- Функция ГномьяСортировка(Знач Массив) i = 1; j = 2; Пока i < Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - по убыванию Если Массив i = j; j = j + 1; Иначе Замена = Массив[i]; Массив[i] = Массив; Массив = Замена; i = i - 1; Если i = 0 Тогда i = j; j = j + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат Массив; КонецФункции //---}
5. Алгоритм "Сортировка вставками".
Представляет собой простой алгоритм сортировки. Смысл заключается в том, что на каждом шаге мы берем элемент, ищем для него позицию и вставляем в нужное место.
Элементарный пример: При игре в дурака, вы тянете из колоды карту и вставляете ее в соответствующее место по возрастанию в имеющихся у вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50. Заглядываете в кошелек, а там купюры достоинством 10,100,1000. Вы вставляете купюру
достоинсвом 50р. между купюрами достоинством 10р и 100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10,50,100,500,1000 - Вот вам
и алгоритм "Сортировка вставками".
Таким образом с каждым шагом алгоритма, вам необходимо отсортировать подмассив данных и вставить значение в нужное место.
//Сортировка вставками {--- Функция СортировкаВставками(Знач Массив) Для i = 0 По Массив.ВГраница()-1 Цикл Ключ = i + 1; Замена = Массив[Ключ]; j = i + 1; Пока j > 0 И Замена < Массив Цикл Массив[j] = Массив; Замена = j - 1; Ключ = j - 1; j = j - 1; КонецЦикла; Массив[Ключ] = Замена; КонецЦикла; Возврат Массив; КонецФункции //---}
6. Алгортим "Сортировка слиянием".
Интересный в плане реализации и идеи алгоритм. Смысл его в том, чтобы разбивать массив на подмассивы, пока длина каждого подмассива не будет равна 1. Тогда мы утверждаем, что такой подмассив отсортирован. Затем сливаем получившиеся подмассивы воедино, одновременно сравнивая и сортируя поэлементно значения подмассивов.
p/s не смог вставить сюда рисунок с более наглядной схемой, постоянно размазывается. Зато хорошо видна в блоке скриншотов внизу. Можно посмотреть как работает алгоритм.
//Сортировка слиянием {---
Функция СортировкаСлиянием(Знач Массив) Если Массив.Количество() = 1 Тогда Возврат Массив; КонецЕсли; ТочкаРазрыв = Массив.Количество() / 2; лМассив = Новый Массив; прМассив = Новый Массив; Для Сч = 0 ПО Массив.ВГраница() Цикл Если Сч < ТочкаРазрыв Тогда лМассив.Добавить(Массив[Сч]); Иначе прМассив.Добавить(Массив[Сч]); КонецЕсли; КонецЦикла; Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив)); КонецФункции Функция Слияние(массив1,массив2) a = 0; b = 0; слМассив = Новый Массив; Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл слМассив.Добавить(); КонецЦикла; Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл Если b < массив2.Количество() И a < массив1.Количество() Тогда Если (массив1[a] > массив2[b]) И (b < массив2.Количество()) Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; Иначе Если b < массив2.количество() Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат слМассив; КонецФункции //---}
7. Алгортим "Сортировка Шелла".
Алгоритм назван так в честь американского ученого Дональда Шелла. По своей сути этот алгоритм является усовершенствованным алгоритмом "Сортировка вставками". Смысл алгоритма заключается в том, чтобы сравнивать не только элементы, стоящие рядом друг с другом, но и на некотором удалении. Сначало выбирается Шаг - некий промежуток, через который будут сравниваться элементы массива на каждой итерации. Обычно его определяют так:
Для первой итерации Шаг = Цел(Массив.Количество()/2), для последующих Шаг = Цел(Шаг/2). Т.е. постепенно шаг сокращается и когда Шаг будет равен 1 произойдет последние сравнение и массив будет отсортирован.
Пример:
Дан массив (10,5,3,1,14,2,7,12).
1. Шаг = 4.
Сортируем простыми вставками каждые 4 группы по 2 элемента (10,14)(5,2)(3,7)(1,12)
10 ,2 ,3 ,1,14 ,5 ,7 ,12
2. Шаг = 2
Сортируем простыми вставками каждые 2 группы по 4 элемента (10,3,14,7)(2,1,5,12)
3 ,1 ,7 ,2 ,10 ,5 ,14 ,12
3. Шаг = 1
Сортируем простыми вставками каждую 1 группу по 8 элементов.
1,2,3,5,7,10,12,14
//Сортировка Шелла {--- Функция СортировкаШелла(Знач Массив) Шаг = Цел(Массив.Количество()/2); Пока Шаг > 0 Цикл i = 0; Пока i < (Массив.Количество() - Шаг) Цикл j = i; Пока j >= 0 И Массив[j] > Массив Цикл Замена = Массив[j]; Массив[j] = Массив; Массив = Замена; j = j - 1; Если ПрименитьОтображениеСортировки Тогда ОтобразитьДиаграммуСортировки(Массив); КонецЕсли; КонецЦикла; i = i + 1; КонецЦикла; Шаг = Цел(Шаг/2); ОбработкаПрерыванияПользователя(); КонецЦикла; Возврат Массив; КонецФункции //---}
8. Алгортим "Быстрая сортировка".
Наиболее популярный и применяемый алгоритм на практике. Является одним из самых эффективных алгоритмов сортировки данных.
Вся суть алгоритма сводится к тому, чтобы разбить сложную задачу на маленькие и решить их по отдельности. Выбирается некая опорная точка и все значения которые меньше перебрасываются влево, все остальные вправо. Далее для каждой полученной части выполняетя тоже самое, до тех пор пока дробить части уже нельзя. В конце мы получаем множество отсортированных частей, которые необходимо просто склеить в 1 целое.
//Алгоритм "Быстрая сортировка" { Процедура б_Сортировка(Массив,НижнийПредел,ВерхнийПредел) i = НижнийПредел; j = ВерхнийПредел; m = Массив[Цел((i+j)/2)]; Пока Истина Цикл Пока Массив[i] < m Цикл i = i + 1; КонецЦикла; Пока Массив[j] > m Цикл j = j - 1; КонецЦикла; Если i > j Тогда Прервать; КонецЕсли; КонецЦикла; Если НижнийПредел < j Тогда б_Сортировка(Массив,НижнийПредел,j); КонецЕсли; Если i < ВерхнийПредел Тогда б_Сортировка(Массив,i,ВерхнийПредел); КонецЕсли; КонецПроцедуры Функция БыстраяСортировка(Массив) НижняяГраница = 0; ВерхняяГраница = Массив.ВГраница(); б_Сортировка(Массив,НижняяГраница,ВерхняяГраница); Возврат Массив; КонецФункции //---}
9. Классическая сортировка массива в 1с.
Передаем массив в список значений. Сортируем стандартным методом "Сортировать".
//Сортировка списком значений {--- Функция СортировкаСпискомЗначений(Знач Массив) мСписокЗнч = Новый СписокЗначений; мСписокЗнч.ЗагрузитьЗначения(Массив); мСписокЗнч.СортироватьПоЗначению(НаправлениеСортировки.Возр); Возврат мСписокЗнч.ВыгрузитьЗначения(); КонецФункции //---}
Все сортировки можно ускорить расположив код в циклах в 1 строку. Но для читабельности, оставил так.
Написал обработку в которой реализованы все вышеперечисленные алгоритмы, также поддерживается динамическая анимация процесса сортировки (Кроме стандартной сортировки 1с).
-При запуске обработки автоматически происходит формирование массива случайных чисел от 0 до 100 размерностью 100 элементов.
-Для создания другого массива необходимо нажать на кнопку "Создание ГСЧ массива ", также можно выбирать необходимый диапазон.
-Для включения динамической анимации необходимо поставить галочку на "Отобразить сортировку в диаграмме". Советую на неэффективных алгоритмах устанавливать галочку при размерности массива до 100 элементов, иначе состаритесь ждать сортировки:)
Динамическая отрисовка процесса сортировки очень сильно снижает производительность, зато наглядно видно как работает алгоритм.
Рано или поздно необходимость сортировать данные из массива возникает у любого программиста. Будь то вывод данных из базы в алфавитном порядке или сортировка имен файлов по дате последнего изменения, можно осуществить благодаря встроенным php функциям для сортировки данных массива. В данной статье продемонстрирую и объясню в примерах как работают такие функции как: sort(), rsort().
Функция ; - Сортировка массива по возрастанию и по алфавиту
Структура:
($Массив, $Флаг);
Функция сортирует заданный ей массив $Массив по возрастанию. Функция предназначена для работы со списками. Списки это обычные массивы, ключи которых начинаются с нуля. Функции можно задать необязательный аргумент $Флаг, который манипулирует тем как именно должно происходить сортировка . Рассмотрим описание аргумента $Флаг:
SORT_REGULAR – Сортировка по умолчанию работы функции
SORT_NUMERIC - Сортировка чисел, по возрастанию
SORT_STRING - Сортировка строк, по алфавиту
Рассмотрим пример, у нас есть массив где хранятся в хаотичном виде данные о количестве пар студента в разные года учебы.
"; } ?> Результат работы скрипта: Курс: 1 - 72 пар Курс: 2 - 83 пар Курс: 3 - 100 пар Если бы мы не применили функцию результат работы был бы следующим: Курс: 1 - 83 пар Курс: 2 - 100 пар Курс: 3 - 72 пар
Сортировка по алфавиту
Ниже приведен скрипт который сортирует страны их массива по алфавиту, второй аргумент функции ($Флаг) не обязательно ставить, т.к. функция сама поймет, что предстоит работать со строками.
"; } ?> Результат работы: Армения Италия Россия Япония
Функция rsort() - Сортировка массива по убыванию
функция является алогичной функции только сортирует массивы по убыванию. рассмотрим структуру синтаксиса:
($Массив, $Флаг);
Пример для данной функции будет похож на примеры выше приведенные, кроме одного, данные из массива будут отсортированы по убыванию. Создаем массив с призами для тех кто займет 1-е, 2-е и 3-е место в конкурсе.
"; } ?> Результат выполнения скрипта: 1 место - приз: 2800 руб. 2 место - приз: 1200 руб. 3 место - приз: 500 руб.
При работе на многих сайтах часто встречается вопрос сортировки данных массива в алфавитном порядке. Многие для этого пишут дополнительные массивы, сравнивают крупные таблицы и перебирают каждое название... Этот вариант не самый лучший, хотя его мы тоже рассмотрим. В данной статье я бы хотел предложить самый простой и короткий путь, который при внимательном прочтении мануалов можно найти в документации.
Массив в алфавитном порядке PHP
Способ достаточно прост и заключается в двух шагах: установке локали (setlocal) и непосредственно сортировки массива. Рассмотрим пример с комментариями.Код PHP
setlocale(LC_ALL, "Russian_Russia.1251"); // установили локаль для русских букв
// пример массива, где слова расположены НЕ по порядку
$example=array("банка","Борис","вид","анкета","егерь","Фёдор","жена","голос");
Natcasesort($example, SORT_LOCALE_STRING); // сортируем массив БЕЗ учёта регистра
// ДЛЯ УЧЁТА РЕГИСТРА используйте sort вместо natcasesort
// выводим результат
foreach ($example as $key => $value){
echo "$value "; // отобразим только слова, без индекса
}
?>
Демонстрация
Скачать исходники
В демонстрации можете посмотреть работу скрипта. При желании можете также скачать архив с файлом.
Если у Вас сервер не на Windows, то нужно будет установить другие локали или сразу несколько:
(LC_ALL, "ru_RU.CP1251", "rus_RUS.CP1251", "Russian_Russia.1251");
// Выведет ru_RU.CP1251 для FreeBSD
// Выведет rus_RUS.CP1251 для линукса
// Выведет Russian_Russia.1251 для Windows
Опережу ответом один из вопросов - локаль для Украины в PHP выглядит так:
Как установить локаль для других кодировок в PHP?
// Устновка локалей для Windows
// Кодировка Windows-1251
setlocale(LC_ALL, "Russian_Russia.1251");
// Кодировка KOI8-R
setlocale(LC_ALL, "Russian_Russia.20866");
// Кодировка UTF-8 (использовать осторожно)
setlocale(LC_ALL, "Russian_Russia.65001");
?>
Второй способ выстроить массив в алфавитном порядке PHP
Если данный способ не устроит и Вы хотите пойти сложным путём, то создайте массив следующего вида:Код PHP
=> а
=> б
=> в
=> г
=> д
=> е
=> ё
=> ж
=> з
=> и
=> й
=> к
=> л
=> м
=> н
=> о
=> п
=> р
=> с
=> т
=> у
=> ф
=> х
=> ц
=> ч
=> ш
=> щ
=> ъ
=> ы
=> ь
=> э
=> ю
=> я
И переберите по первой букве второй массив.
Первую букву какого-либо элемента массива вычисляем так:
Код PHP
$city="Москва"; // например элемент с индексом 1
$first_letter = mb_substr($city,0,1,"UTF-8"); // получим букву "М"
Поскольку работаем с русскими буквами (многобайтной кодировкой), то использовать лучше функцию mb_substr
, а в конце лучше точно указать кодировку данных переменной или массива, в нашем случае UTF-8.
Спасибо за внимание! Надеюсь информация была полезна. Если есть вопросы, то пишите в комментариях.
Чем больше массив анализируемых данных, тем труднее сконцентрировать внимание на их основных характеристиках. Чтобы лучше воспринять информацию, содержащуюся в наборе данных, их необходимо правильно организовать. Для этого используют либо упорядоченный массив, либо диаграмму «ствол и листья».
Упорядоченный массив
Упорядоченный массив (не обязательно одномерный) состоит из последовательности данных, расположенных по возрастанию. Например, таблица (рис. 1) содержит показатели о пятилетней среднегодовой доходности 158 фондов. Упорядоченные массивы позволяют сразу определить минимальное и максимальное значения, типичные величины, а также диапазон, которому принадлежит основная масса значений.
Рис. 1. Упорядоченный массив, содержащий данные о пятилетней среднегодовой доходности 158 фондов, ориентированных на быстрый рост капитала, за период с 1 января 1997 до 31 декабря 2001
Скачать заметку в формате или , примеры в формате
Видно, что наименьший уровень пятилетней среднегодовой доходности равен –6,1% в год, а наивысший достигает 26,3%. Кроме того, среднегодовые показатели большинства фондов колеблются в диапазоне от 5 до 15%. И всё же представление данных в виде двумерного массива (как на рис. 1) не является оптимальным, так как не позволяет быстро и легко создать сводную таблицу. Поэтому я рекомендую создавать одномерные вертикальные упорядоченные массивы. Excel предоставляет несколько возможностей для этого.
Рассмотрим в качестве сквозного примера среднемесячные температуры июля в Москве за 130 лет наблюдений (рис. 2).
Рис. 2. Среднемесячная температура июля в Москве; исходные данные
Простейший способ упорядочения массива данных предоставляется опцией Excel Сортировать . Выделите столбцы А и В; пройдите по меню Данные → Сортировка (рис. 3). Откроется меню Сортировка . В поле Сортировать по выберите Средняя температура июля, °C , в поле Порядок – По возрастанию . Нажмите Ok.
Рис. 3. Сортировка данных
Вы получите отсортированный (упорядоченный) по температуре список (рис. 4). Сразу видно, что минимальная среднемесячная температура в июле была зафиксирована в Москве в 1904 г. – 14,6°С, а самая высокая – в 2010 г. – 26,1°С. Наверное, вы помните этот ужасный год!? Обратите внимание, что предыдущий рекорд был превышен более, чем на 10%.
Рис. 4. Упорядоченный список
Диаграмма «ствол и листья»
Диаграмма «ствол и листья» представляет собой инструмент для наглядной организации набора данных и анализа их распределения. Данные в диаграмме распределены в соответствии с первыми цифрами, или стволами, и замыкающими цифрами, или листьями. Например, число 18,9 в диаграмме «ствол и листья» состоит из ствола 18 и листа 9 (рис. 5). К сожалению, Excel не умеет автоматически строить диаграмму «ствол и листья». Поэтому воспользуемся ручной процедурой. В качестве ствола используем целую часть температуры, а в качестве листьев – десятичную (см. формулы на листе «Ствол и листья» Excel-файла; сначала я выделил дробную часть, затем перенес дроби из столбцов в строки, и, наконец, отформатировал диаграмму для придания ей большей наглядности).
Рис. 5. Диаграмма «ствол и листья»
Диаграмма «ствол и листья» визуализирует большой массив информации. Например, по ней непосредственно можно определить минимальное (14,6) и максимальное (26,1) значения. Видно, что большинство значений попадают в диапазон 16…20°С, а сами значения образуют со средним около 18°С. Также наблюдается довольно широкий хвост в области бо льших значений.
Контрольные задания
- Данные, приведенные ниже, содержат количество чеков, возвращенных 23 банками своим вкладчикам ввиду отсутствия средств на счете. (Минимальный размер вклада не должен быть ниже 100 долл.): 26 28 20 20 21 22 25 25 18 25 15 20 18 20 25 25 22 30 30 30 15 20 29.
- Постройте диаграмму «ствол и листья», содержащую указанные данные.
- Определите значение, вокруг которого концентрируется распределение количества возвращенных чеков.
- Данные, приведенные ниже, содержат величину ежемесячной платы за услуги (в долларах), взимаемой 26 банками со своих клиентов, если сумма на счету клиента не превышает установленного минимума, равного 1500 долл.: 12 8 5 5 6 6 10 10 9 7 10 7 7 5 0 10 6 9 12 0 5 10 8 5 5 9.
- Создайте упорядоченный массив, содержащий указанные данные.
- Постройте диаграмму «ствол и листья, содержащую указанные данные.
- Какой способ представления данных более информативен? Обоснуйте свой ответ.
- Определите значение, вокруг которого концентрируется распределение ежемесячной оплаты банковских услуг.
Ответы на контрольные задания
1. См. лист «КонтрЗад1» Excel-файла и рис. 6. Диаграмма «ствол и листья» более информативна, чем упорядоченный массив, так как лучше визуализирует данные. Среднее значение составляет приблизительно 22. Хитрость задания заключается в выборе шага для значений ствола. Если в качества шага выбрать число десятков (10, 20, 30), диаграмма «ствол и листья» потеряет в своей наглядности.
Сортировка массива — это процесс распределения всех элементов в определённом порядке. Очень часто это бывает полезным. Например, в вашем почтовом ящике электронные письма отображаются в зависимости от времени получения; новые письма считаются более релевантными, чем те, которые вы получили полчаса, час, два или день назад; когда вы переходите в свой список контактов, имена обычно находятся в алфавитном порядке, потому что так легче что-то найти. Все эти случаи включают в себя сортировку данных перед их фактическим выводом.
Как работает сортировка?
Сортировка данных может сделать поиск внутри массива более эффективным не только для людей, но и для компьютеров. Например, рассмотрим случай, когда нам нужно узнать, отображается ли определённое имя в списке имён. Чтобы это узнать, нужно проверить каждый элемент массива на соответствие с нашим значением. Поиск в массиве с множеством элементов может оказаться слишком неэффективным (затратным).
Однако, предположим, что наш массив с именами отсортирован в алфавитном порядке. Тогда наш поиск начинается с первой буквы нашего значения и заканчивается буквой, которая идёт следующей по алфавиту. В таком случае, если мы дошли до этой буквы и не нашли имя, то точно знаем, что оно не находится в остальной части массива, так как в алфавитном порядке нашу букву мы уже прошли!
Не секрет, что есть алгоритмы поиска внутри отсортированных массивов и получше. Используя простой алгоритм, мы можем искать определённый элемент в отсортированном массиве, содержащем 1 000 000 элементов, используя всего лишь 20 сравнений! Недостатком, конечно же, является то, что сортировка массива с таким огромным количеством элементов — дело сравнительно затратное, и оно точно не выполняется ради одного поискового запроса.
В некоторых случаях сортировка массива делает поиск ненужным. Например, мы ищем наилучший результат студента за тест. Если массив не отсортирован, то нам придётся просмотреть каждый элемент массива, чтобы найти наивысшую оценку. Если же массив отсортирован, то наивысшая оценка будет находиться либо на первой позиции, либо на последней (в зависимости от метода сортировки массива: в порядке возрастания или в порядке убывания), поэтому нам не нужно искать вообще!
Сортировка обычно выполняется путём повторного сравнения пар элементов массива и замены значений, если они отвечают определённым критериям. Порядок, в котором эти элементы сравниваются, зависит от того, какой алгоритм сортировки используется. Критерии состоят из того, как будет сортироваться массив (например, в порядке возрастания или в порядке убывания).
Чтобы поменять два элемента местами, мы можем использовать функцию std::swap() из стандартной библиотеки C++, которая определена в algorithm. В C++11 std::swap() был перенесён в заголовочный файл utility:
#include
#include #include int main () int a = 3 ; int b = 5 ; std :: cout << "Before swap: a = " << a << ", b = " << b << "\n" ; std :: swap (a , b ) ; // меняем местами значения переменных a и b std :: cout << "After swap: a = " << a << ", b = " << b << "\n" ; |
Результат выполнения программы выше:
Before swap: a = 3, b = 5
After swap: a = 5, b = 3
После выполнения операции замены значения переменных a и b поменялись местами.
Сортировка массивов методом выбора
Существует множество способов сортировки массивов. Сортировка массивов методом выбора, пожалуй, самая простая для понимания, хоть и одна из самых медленных.
Для сортировки массива методом выбора от наименьшего до наибольшего элемента выполняются следующие шаги:
Начиная с элемента под индексом 0, ищем в массиве наименьшее значение.
Найденное значение меняем местами с нулевым элементом.
Повторяем шаги №1 и №2 уже для следующего индекса в массиве.
Другими словами, мы ищем наименьший элемент в массиве и перемещаем его на первое место. Затем ищем второй наименьший элемент и перемещаем его уже на второе место после первого наименьшего элемента. Этот процесс продолжается до тех пор, пока в массиве не закончатся неотсортированные элементы.
Вот пример работы этого алгоритма в массиве с 5-ью элементами:
{ 30, 50, 20, 10, 40 }
Сначала ищем наименьший элемент, начиная с индекса 0:
{ 30, 50, 20, 10 , 40 }
Затем меняем местами наименьший элемент с элементом под индексом 0:
{ 10 , 50, 20, 30 , 40 }
Теперь, когда первый элемент массива отсортирован, мы его игнорируем. Ищем следующий наименьший элемент, но уже начиная с индекса 1:
{ 10 , 50, 20 , 30, 40 }
И меняем его местами с элементом под индексом 1:
{ 10 , 20 , 50 , 30, 40 }
Теперь мы можем игнорировать первые два элемента. Ищем следующий наименьший элемент, начиная с индекса 2:
{ 10 , 20 , 50, 30 , 40 }
И меняем его местами с элементом под индексом 2:
{ 10 , 20 , 30 , 50 , 40 }
Ищем следующий наименьший элемент, начиная с индекса 3:
{ 10 , 20 , 30 , 50, 40 }
И меняем его местами с элементом под индексом 3:
{ 10 , 20 , 30 , 40 , 50 }
Ищем следующий наименьший элемент, начиная с индекса 4:
{ 10 , 20 , 30 , 40 , 50 }
И меняем его местами с элементом под индексом 4 (выполняется самозамена, т.е. ничего не делаем):
{ 10 , 20 , 30 , 40 50 }
{ 10, 20, 30, 40, 50 }
Обратите внимание, последнее сравнение всегда будет одиночным (т.е. самозамена), что является лишней операцией, поэтому, фактически, мы можем остановить выполнение сортировки перед последним элементом массива.
Сортировка массивов методом выбора в C++
Вот как этот алгоритм реализован в C++:
#include
#include #include int main () const int length = 5 ; // Перебираем каждый элемент массива // (кроме последнего, он уже будет отсортирован к тому времени, когда мы до него доберёмся) < length - 1 ; ++ startIndex ) // В переменной smallestIndex хранится индекс наименьшего значения, которое мы нашли в этой итерации // Начинаем с того, что наименьший элемент в этой итерации - это первый элемент (индекс 0) int smallestIndex = startIndex ; // Затем ищем элемент поменьше в остальной части массива < length ; ++ currentIndex ) // Если мы нашли элемент, который меньше нашего наименьшего элемента, if (array [ currentIndex ] < array [ smallestIndex ] ) // то запоминаем его smallestIndex = currentIndex ; // smallestIndex теперь наименьший элемент // Меняем местами наше начальное наименьшее число с тем, которое мы обнаружили std :: swap (array [ startIndex ] , array [ smallestIndex ] ) ; // Теперь, когда весь массив отсортирован - выводим его на экран for (int index = 0 ; index < length ; ++ index ) std :: cout << array [ index ] << " " ; return 0 ; |
Наиболее запутанной частью этого алгоритма является внутри другого цикла (так называемый вложенный цикл). Внешний цикл (startIndex) перебирает элементы один за другим (поочерёдно). В каждой итерации внешнего цикла внутренний цикл (currentIndex) используется для поиска наименьшего элемента среди элементов, которые остались в массиве (начиная со startIndex + 1). smallestIndex отслеживает индекс наименьшего элемента, найденного внутренним циклом. Затем smallestIndex меняется значением со startIndex . И, наконец, внешний цикл (startIndex) передаёт этот элемент, и процесс повторяется.
Подсказка: Если у вас возникли проблемы с пониманием того, как работает программа выше, то попробуйте записать её выполнение на листке бумаги. Запишите начальные (неотсортированные) элементы массива горизонтально в строке в верхней части листа. Нарисуйте стрелки, указывающие, какие элементы являются startIndex , currentIndex и smallestIndex на данный момент. Прокрутите выполнение программы вручную и перерисуйте стрелки по мере изменения индексов. После каждой итерации внешнего цикла нарисуйте новую строку, показывающую текущее состояние массива (расположение его элементов).
Сортировка текста выполняется с помощью того же алгоритма. Просто измените тип массива из -а в и инициализируйте его с помощью соответствующих значений.
std::sort()
Поскольку операция сортировки массивов очень распространена, то стандартная библиотека C++ предоставляет встроенную функцию сортировки — std::sort() . Она находится в заголовочном файле algorithm и вызывается следующим образом:
#include
#include #include int main () const int length = 5 ; int array [ length ] = { 30 , 50 , 20 , 10 , 40 } ; std :: sort (array , array + length ) ; for (int i = 0 ; i < length ; ++ i ) std :: cout << array [ i ] << " " ; return 0 ; |
Тест
Задание №1
Напишите на листке бумаги выполнение сортировки следующего массива методом выбора (так как мы это делали выше):
{30, 60, 20, 50, 40, 10}
Ответ №1
30 60 20 50 40 10
10
60 20 50 40 30
10 20
60
50 40 30
10 20 30
50 40 60
10 20 30 40
50
60
10 20 30 40 50
60 (самозамена)
10 20 30 40 50 60
(самозамена)
Задание №2
Перепишите код программы из подзаголовка «Сортировка массивов методом выбора в C++» так, чтобы сортировка выполнялась в порядке убывания (от наибольшего числа к наименьшему). Хотя это может показаться сложным на первый взгляд, но, на самом деле, это очень просто.
Ответ №2
Просто измените:
If (array < array)
if (array [ currentIndex ] < array [ smallestIndex ] ) |
If (array > array)
if (array [ currentIndex ] > array [ smallestIndex ] ) |
Также smallestIndex следует переименовать в largestIndex:
#include
#include #include int main () const int length = 5 ; int array [ length ] = { 30 , 50 , 20 , 10 , 40 } ; // Перебираем каждый элемент массива, кроме последнего for (int startIndex = 0 ; startIndex < length - 1 ; ++ startIndex ) // largestIndex - это индекс наибольшего элемента, который мы обнаружили до сих пор int largestIndex = startIndex ; // Перебираем каждый элемент массива начиная со startIndex + 1 for (int currentIndex = startIndex + 1 ; currentIndex < length ; ++ currentIndex ) // Если текущий элемент больше нашего наибольшего элемента, if (array [ currentIndex ] > array [ largestIndex ] ) // то это новый наибольший элемент в этой итерации largestIndex = currentIndex ; // Меняем местами наше стартовое число с обнаруженным наибольшим элементом std :: swap (array [ startIndex ] , array [ largestIndex ] ) ; // Выводим отсортированный массив на экран for (int index = 0 ; index < length ; ++ index ) std :: cout << array [ index ] << " " ; return 0 ; |
Задание №3
Это задание уже немного сложнее.
Ещё одним простым методом сортировки элементов является «сортировка пузырьком» (или ещё «пузырьковая сортировка» ). Суть заключается в сравнении пары значений, которые находятся рядом, и, если удовлетворены заданные критерии, значения из этой пары меняются местами. И таким образом элементы «скачут пузырьком» до конца массива. Хотя есть несколько способов оптимизировать сортировку пузырьком, в этом задании мы будем придерживаться неоптимизированной версии, так как она проще.
При неоптимизированной версии сортировки пузырьком выполняются следующие шаги для сортировки массива от наименьшего до наибольшего значения :
Сравнивается элемент массива под индексом 0 с элементом массива под индексом 1. Если элемент под индексом 0 больше элемента под индексом 1, то значения меняются местами.
Затем мы перемещаемся к следующей пары значений: элемент под индексом 1 и элемент под индексом 2 и так до тех пор, пока не достигнем конца массива.
Повторяем шаг №1 и шаг №2 до тех пор, пока весь массив не будет отсортирован.
Напишите программу, которая отсортирует следующий массив методом пузырька в соответствии с правилами выше:
const int length(9); int array = { 7, 5, 6, 4, 9, 8, 2, 1, 3 };
const int length (9 ) ; |
В конце программы выведите отсортированные элементы массива.
Подсказка: Если мы можем отсортировать только один элемент за одну итерацию, то это означает, что нам нужно будет повторить выполнение цикла столько раз, сколько есть чисел в нашем массиве (его длина), дабы гарантировать выполнение сортировки всего массива.
Ответ №3
#include
#include #include int main () const int length (9 ) ; int array [ length ] = { 7 , 5 , 6 , 4 , 9 , 8 , 2 , 1 , 3 } ; for (int iteration = 0 ; iteration < length - 1 ; ++ iteration ) // Перебираем каждый элемент массива до последнего элемента (не включительно) // Последний элемент не имеет пары для сравнения for (int currentIndex = 0 ; currentIndex < length - 1 ; ++ currentIndex ) { // Если текущий элемент больше элемента после него, то меняем их местами if (array [ currentIndex ] > array [ currentIndex + 1 ] ) std :: swap (array [ currentIndex ] , array [ currentIndex + 1 ] ) ; } } // Выводим отсортированный массив на экран for (int index = 0 ; index < length ; ++ index ) std :: cout << array [ index ] << " " ; return 0 ; } |
Задание №4
Реализуйте следующие два решения оптимизации алгоритма сортировки пузырьком, который вы написали в предыдущем задании:
Обратите внимание, с каждым выполнением сортировки пузырьком наибольшее значения в массиве «пузырится» до конца. После первой итерации последний элемент массива уже отсортирован. После второй итерации отсортирован предпоследний элемент массива и т.д. С каждой новой итерацией нам не нужно перепроверять элементы, которые уже были отсортированы. Измените свой цикл так, чтобы не перепроверять элементы, которые уже были отсортированы.
