Инструкция
Существует несколько способов сортировки массива. Наиболее простая для алгоритмизации - «пузырьковая» сортировка, однако она же относится к самым медленным. Суть данного метода заключается в последовательном проходе по массиву данных и сравнении каждой пары элементов. Если нижестоящий элемент оказывается меньше предыдущего, производится обмен местами. Далее алгоритм начинается сначала. Пример кода сортировки на языке С:
int mаss ;
int el_min=10;
for (int i=0; ii; j--)
if (lеss(mаss [j], mаss ))
swаp(mаss [j], mаss );
}
Одним из оптимальных алгоритмов сортировки массива по возрастанию считается упорядочивание методом вставок. Суть алгоритма заключается в формировании заданной последовательности среди группы элементов (по возрастанию). Специальный обработчик в цикле проверяет массив на упорядоченность. Для сортировки по возрастанию задается следующее условие. Если последующий элемент меньше предыдущего, он изымается со своего места и помещается на то, которое соответствует его значению. Пример кода программы сортировки по возрастанию на языке С:
int Kol = 40;
int mаss , k;
for (int i = 1, j=0; i{
k = mаss [i]; // вспомогательная переменная для хранения элемента массива
j = i - 1;
while (k {
mаss = mаss [j];
j--;
if (j mаss = k;
}
}
Еще один из часто используемых методов сортировки – алгоритм упорядочивания через поиск минимального или максимального элемента в массиве. При сортировке по возрастанию в момент первого прохода по массиву находится его элемент с самым минимальным значением и помещается в начало массива. На его же место устанавливается элемент, занимавший ранее первую позицию. При дальнейшем рассмотрении массива заполненное место исключается. Ищется следующий минимальный элемент, помещается уже на второе место и т.д., пока весь массив не будет отсортирован. Код сортировки методом нахождения минимального элемента списка:
int mаss , bb;
int Kоl = 30, min, pоs;
for (int i = 0; i{
min = mаss [i];
pоs = i;
for (int j=0; j {
if (mаss [j] {
min = mаss [j];
pоs = j;
}
bb = mаss [i];
mаss [i] = mаss ;
mаss = bb;
}
}
Способы упорядочивания элементов массивов зависят от инструментов, которые имеются у вас в распоряжении. Ниже приведены несколько вариантов упорядочивания одномерных массивов при использовании наиболее распространенного серверного языка программирования PHP. Самостоятельно составлять функции для перебора элементов массива, их сравнения и присвоения новых значений при использовании этого языка не требуется - все это делают встроенные функции.
Инструкция
Используйте функцию sort(), если надо выстроить данные в массиве в порядке их возрастания. Например:$values = array(58, 15, 2.41, 26, 30);
sort($values);В результате применения изменится расположения данных в массиве - он станет таким: (2.41, 15, 26, 30, 58). Если в вызов функции добавить флаг SORT_STRING, то функция будет считать данные массива строковыми и выстраивать их по . Так как знак строковой переменной «2.41» в алфавите располагается дальше, чем первый знак строковой переменной «15», то после применения функции sort($values, SORT_STRING) переменные выстроятся иначе: (15, 2.41, 26, 30, 58).
Воспользуйтесь функцией rsort() при необходимости упорядочить массив в порядке убывания его значений. Эта функция отличается от описанной в первом шаге только порядком сортировки.
Применяйте функцию asort(), если необходимо упорядочить в порядке возрастания значения именованного (ассоциативного) массива, не изменяя при этом исходных соответствий между индексом и значением каждого элемента массива. Например:$values = array("one" => 58, "two" => 15, "three" => 2.41, "four" => 26, "five" => 30);
asort($values);В результате порядок следования элементов массива станет таким: ("three" => 2.41, "two" => 15, "four" => 26, "five" => 30, "one" => 58). В остальном действие этой функции не отличается от описанной в первом шаге функции sort. Для аналогичного упорядочивания элементов в порядке убывания используйте функцию arsort().
Доброго времени суток, уважаемые читатели нашего блога! На нашем сайте мы уже касались темы массивов и это был пример того, как сделать . Также уже была статья о том, для решения этой задачи тоже были использованы массивы. А сегодня речть пойдет о том, как отсортировать многомерный массив
. Итак, приступим.
Возьмем массив «goods» следующего вида:
200, "manufacture" => "ТОО Целина"); $goods = array("price" => 400, "manufacture" => "ИП Девяткин"); $goods = array("price" => 800, "manufacture" => "АО Аграрник"); $goods = array("price" => 790, "manufacture" => "ЗАО Красный Восток"); ?>
Необходимо отсортировать данный массив по ключу. Для этого воспользуемся функцией «ksort»:
ksort ($goods); print_r($goods); ?>
В результате получаем отсортированный массив по ключу:
Array ( => Array ( => 400 => ИП Девяткин) => Array ( => 200 => ТОО Целина) => Array ( => 800 => АО Аграрник) => Array ( => 790 => ЗАО Красный Восток))
Как видим, ключи идут в порядке возрастания от 45 до 89. Теперь нужно отсортировать массив по значению ключа «price» для этого воспользуемся функцией «uasort» и напишем для неё пользовательскую функцию «sort_p»:
sort_p ($a, $b) { return strcmp($a["price"], $b["price"]); } uasort ($goods, "sort_p" ); print_r($goods); ?>
В результате получаем отсортированный массив по ключу «price»:
Array ( => Array ( => 200 => ТОО Целина) => Array ( => 400 => ИП Девяткин) => Array ( => 790 => ЗАО Красный Восток) => Array ( => 800 => АО Аграрник))
Как видим, значения ключа «price» идут в порядке возрастания от 200 до 800. Чтобы значения ключа «price» шли в обратном порядке, по убыванию, поменяем местами параметры функции «strcmp» в пользовательской функции «sort_p»:
b ["price"], $a ["price"]); } uasort($goods, "sort_p"); print_r($goods); ?>
Получим следующий результат:
Array ( => Array ( => 800 => АО Аграрник) => Array ( => 790 => ЗАО Красный Восток) => Array ( => 400 => ИП Девяткин) => Array ( => 200 => ТОО Целина))
Как видим, теперь значения ключа «price» идут в порядке убывания от 800 до 200. Теперь нужно отсортировать массив по значению двух ключей «manufacture» и «price» для этого напишем пользовательскую функцию «sort_pm»:
sort_pm ($a, $b) { $r1 = strcmp($a["manufacture"], $b["manufacture"]$a["price"], $b["price"]) : $r1; } uasort($goods, "sort_pm" ); print_r($goods); ?>
Теперь сортировка происходит по значениям двух ключей в порядке возрастания, приоритетным является ключ «manufacture».
Array ( => Array ( => 800 => АО Аграрник) => Array ( => 790 => ЗАО Красный Восток) => Array ( => 400 => ИП Девяткин) => Array ( => 200 => ТОО Целина))
Если для Вас более приоритетным являются значения ключа «price», то поменяйте местами параметры функций «strcmp» и запишите функцию «sort_pm» следующим образом:
$a["price"], $b["price"] ); return ($r1 == 0) ? strcmp() : $r1; } uasort($goods, "sort_pm"); print_r($goods); ?>
То есть были изменены параметры функций «strcmp». Теперь значения ключа «price» будут приоритетнее, значит сортировка в первую очередь будет осуществлятся по ним, затем будут отсортированы значения ключа «manufacture». Поясним на следующем примере:
200, "manufacture" => "ТОО Целина"); $goods = array("price" => 400, "manufacture" => "ИП Девяткин"); $goods = array("price" => 400, "manufacture" => "АО Праздник"); $goods = array("price" => 800, "manufacture" => "АО Аграрник"); $goods = array("price" => 790, "manufacture" => "ЗАО Красный Восток"); function sort_pm($a, $b) { $r1 = strcmp($a["price"], $b["price"] ); return ($r1 == 0) ? strcmp($a["manufacture"], $b["manufacture"] ) : $r1; } uasort($goods, "sort_pm"); print_r($goods); ?>
Чем больше массив анализируемых данных, тем труднее сконцентрировать внимание на их основных характеристиках. Чтобы лучше воспринять информацию, содержащуюся в наборе данных, их необходимо правильно организовать. Для этого используют либо упорядоченный массив, либо диаграмму «ствол и листья».
Упорядоченный массив
Упорядоченный массив (не обязательно одномерный) состоит из последовательности данных, расположенных по возрастанию. Например, таблица (рис. 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
Реализуйте следующие два решения оптимизации алгоритма сортировки пузырьком, который вы написали в предыдущем задании:
Обратите внимание, с каждым выполнением сортировки пузырьком наибольшее значения в массиве «пузырится» до конца. После первой итерации последний элемент массива уже отсортирован. После второй итерации отсортирован предпоследний элемент массива и т.д. С каждой новой итерацией нам не нужно перепроверять элементы, которые уже были отсортированы. Измените свой цикл так, чтобы не перепроверять элементы, которые уже были отсортированы.
Рано или поздно необходимость сортировать данные из массива возникает у любого программиста. Будь то вывод данных из базы в алфавитном порядке или сортировка имен файлов по дате последнего изменения, можно осуществить благодаря встроенным 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 руб.