Доброго времени суток, уважаемые читатели нашего блога! На нашем сайте мы уже касались темы массивов и это был пример того, как сделать . Также уже была статья о том, для решения этой задачи тоже были использованы массивы. А сегодня речть пойдет о том, как отсортировать многомерный массив . Итак, приступим.
Возьмем массив «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 000 000 элементов, используя всего лишь 20 сравнений! Недостатком, конечно же, является то, что сортировка массива с таким огромным количеством элементов — дело сравнительно затратное, и оно точно не выполняется ради одного поискового запроса.

В некоторых случаях сортировка массива делает поиск ненужным. Например, мы ищем наилучший результат студента за тест. Если массив не отсортирован, то нам придётся просмотреть каждый элемент массива, чтобы найти наивысшую оценку. Если же массив отсортирован, то наивысшая оценка будет находиться либо на первой позиции, либо на последней (в зависимости от метода сортировки массива: в порядке возрастания или в порядке убывания), поэтому нам не нужно искать вообще!

Сортировка обычно выполняется путём повторного сравнения пар элементов массива и замены значений, если они отвечают определённым критериям. Порядок, в котором эти элементы сравниваются, зависит от того, какой алгоритм сортировки используется. Критерии состоят из того, как будет сортироваться массив (например, в порядке возрастания или в порядке убывания).

Чтобы поменять два элемента местами, мы можем использовать функцию std::swap() из стандартной библиотеки C++, которая определена в algorithm. В C++11 std::swap() был перенесён в заголовочный файл utility:

#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 // для std::swap. В C++11 используйте заголовок int main() { const int length = 5; int array = { 30, 50, 20, 10, 40 }; // Перебираем каждый элемент массива // (кроме последнего, он уже будет отсортирован к тому времени, когда мы до него доберёмся) for (int startIndex = 0; startIndex < length - 1; ++startIndex) { // В переменной smallestIndex хранится индекс наименьшего значения, которое мы нашли в этой итерации // Начинаем с того, что наименьший элемент в этой итерации - это первый элемент (индекс 0) int smallestIndex = startIndex; // Затем ищем элемент поменьше в остальной части массива for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex) { // Если мы нашли элемент, который меньше нашего наименьшего элемента, if (array < array) // то запоминаем его smallestIndex = currentIndex; } // smallestIndex теперь наименьший элемент // Меняем местами наше начальное наименьшее число с тем, которое мы обнаружили std::swap(array, array); } // Теперь, когда весь массив отсортирован - выводим его на экран for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

Наиболее запутанной частью этого алгоритма является внутри другого цикла (так называемый вложенный цикл). Внешний цикл (startIndex) перебирает элементы один за другим (поочерёдно). В каждой итерации внешнего цикла внутренний цикл (currentIndex) используется для поиска наименьшего элемента среди элементов, которые остались в массиве (начиная со startIndex + 1). smallestIndex отслеживает индекс наименьшего элемента, найденного внутренним циклом. Затем smallestIndex меняется значением со startIndex . И, наконец, внешний цикл (startIndex) передаёт этот элемент, и процесс повторяется.

Подсказка: Если у вас возникли проблемы с пониманием того, как работает программа выше, то попробуйте записать её выполнение на листке бумаги. Запишите начальные (неотсортированные) элементы массива горизонтально в строке в верхней части листа. Нарисуйте стрелки, указывающие, какие элементы являются startIndex , currentIndex и smallestIndex на данный момент. Прокрутите выполнение программы вручную и перерисуйте стрелки по мере изменения индексов. После каждой итерации внешнего цикла нарисуйте новую строку, показывающую текущее состояние массива (расположение его элементов).

Сортировка текста выполняется с помощью того же алгоритма. Просто измените тип массива из -а в и инициализируйте его с помощью соответствующих значений.

std::sort()

Поскольку операция сортировки массивов очень распространена, то стандартная библиотека C++ предоставляет встроенную функцию сортировки — std::sort() . Она находится в заголовочном файле algorithm и вызывается следующим образом:

#include #include // для std::sort int main() { const int length = 5; int array = { 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 > array)

Также smallestIndex следует переименовать в largestIndex:

#include #include // для std::swap. В C++11 используйте заголовок int main() { const int length= 5; int array = { 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 > array) // то это новый наибольший элемент в этой итерации largestIndex = currentIndex; } // Меняем местами наше стартовое число с обнаруженным наибольшим элементом std::swap(array, array); } for (int index = 0; index < length; ++index) std::cout << array << " "; 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 };

В конце программы выведите отсортированные элементы массива.

Подсказка: Если мы можем отсортировать только один элемент за одну итерацию, то это означает, что нам нужно будет повторить выполнение цикла столько раз, сколько есть чисел в нашем массиве (его длина), дабы гарантировать выполнение сортировки всего массива.

Ответ №3

#include #include // для std::swap. В C++11 используйте заголовок int main() { const int length(9); int array = { 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 > array) std::swap(array, array); } } // Выводим отсортированный массив на экран for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

Задание №4

Реализуйте следующие два решения оптимизации алгоритма сортировки пузырьком, который вы написали в предыдущем задании:

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

Инструкция

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

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().

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

Массив в алфавитном порядке PHP

Код 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 выглядит так:

// Устновка локалей для 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.

Спасибо за внимание! Надеюсь информация была полезна. Если есть вопросы, то пишите в комментариях.