8.1.5. Сортировка массива

8.1.5. Сортировка массива

Самый простой способ отсортировать массив — воспользоваться встроенным методом sort:

words = %w(the quick brown fox)

list = words.sort # ["brown", "fox", "quick", "the"]

# Или отсортировать на месте:

words.sort!       # ["brown", "fox", "quick", "the"]

Здесь предполагается, что все элементы массива сравнимы между собой. При сортировке неоднородного массива, например [1, 2, "tHRee", 4], обычно возникает ошибка.

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

а = [1, 2, "three", "four", 5, 6]

b = a.sort {|x,y| x.to_s <=> y.to_s}

# b равно [1, 2, 5, 6, "four", "three"]

Конечно, подобное упорядочение (в данном случае основанное на кодировке ASCII) может оказаться бессмысленным. При работе с неоднородным массивом нужно прежде всего задать себе вопрос, зачем вообще его сортировать. И почему приходится хранить в массиве объекты разных типов?

Описанная методика работает, потому что блок возвращает целое число (-1.0 или 1) при каждом вызове. Если возвращена -1, то есть x меньше у, то два элемента меняются местами. Чтобы отсортировать массив по убыванию, достаточно все го лишь изменить порядок сравнения:

x = [1, 4, 3, 5, 2]

y = x.sort {|a,b| b <=> а} # [5, 4, 3, 2, 1]

Блоки можно применять и для более сложных сортировок. Предположим, что нужно отсортировать названия книг и фильмов следующим способом: регистр игнорируется, полностью игнорируются пробелы, а также ряд знаков препинания и артикли. Ниже приведен простой пример (и преподаватели английского языка, и программисты будут удивлены таким способом упорядочения по алфавиту).

titles = ["Starship Troopers",

          "A Star is Born",

          "Star Wars",

          "Star 69",

          "The Starr Report"]

sorted = titles.sort do |x,y|

 # Удалить артикли

 a = x.sub(/"(a |an |the )/i, "")

 b = y.sub(/"(a |an |the )/i, "")

 # Удалить пробелы и знаки препинания

 a.delete!(" .,-?!")

 b.delete!(" .,-?!")

 # Преобразовать в верхний регистр

 a.upcase!

 b.upcase!

 # Сравнить а и b

 а <=> b

end

# Теперь sorted равно:

# [ "Star 69", "A Star is Born", "The Starr Report"

#   "Starship Troopers", "Star Wars"]

Данный пример не слишком полезен и, конечно, его можно было бы записать более компактно. Но идея в том, что для сравнения двух операндов в определенном порядке над ними можно выполнять произвольно сложный набор операций. (Отметим, однако, что мы не изменили исходные операнды, так как работали с их копиями.) Эта общая техника полезна во многих ситуациях, например для сортировки по нескольким ключам или по ключам, вычисляемым во время выполнения.

В последних версиях Ruby в модуль Enumerable добавлен метод sort_by (который, конечно, подмешивается к классу Array). Важно понимать, что он делает.

В методе sort_by применяется то, что программисты на Perl называют преобразованием Шварца — в честь Рэндала Шварца (Randal Schwartz), внесшего немалый вклад в развитие этого языка. Вместо того чтобы сортировать сами элементы массива, мы применяем к ним некоторую функцию и сортируем возвращаемые ей результаты.

В качестве искусственного примера рассмотрим список файлов, который необходимо отсортировать по размеру. Прямолинейный способ выглядит так:

files = files.sort {|x,y| File.size(x) <=> File.size(y) }

Однако тут есть две проблемы. Во-первых, слишком многословно. Надо бы сделать покомпактнее.

Во-вторых, при такой сортировке приходится многократно обращаться к диску, а это довольно дорогая операция (по сравнению с операциями в оперативной памяти). Хуже того, одна и та же операция может выполняться несколько раз.

Метод sort_by решает обе проблемы. Вот «правильный» способ:

files = files.sort_by {|x| File.size(x) }

Здесь каждый ключ вычисляется ровно один раз, а затем сохраняется в виде пары ключ-данные. Для небольших массивов производительность при таком подходе может даже снизиться, зато код получается более понятным.

Не существует метода sort_by!. Но при желании вы можете написать его самостоятельно.

А как обстоит дело с сортировкой по нескольким ключам? Предположим, что имеется массив объектов, который нужно отсортировать по трем атрибутам: имени, возрасту и росту. Из того, что массивы можно сравнивать, следует, что такое решение будет работать:

list = list.sort_by {|x| [x.name, x.age, x.height] }

Конечно, элементы массива могут быть и не такими простыми. Допустимы произвольно сложные выражения.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Свойства массива

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Свойства массива Некоторые замечания о классе.[x]. Подобные классы существуют для массивов большей размерности: ARRAY2 и т. д.[x]. Компонент Count может быть реализован и как атрибут и как функция, поскольку count = upper - lower+1. В реальном классе это выражается инвариантом, как


8.1.10. Рандомизация массива

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

8.1.10. Рандомизация массива Иногда нужно переставить элементы массива в случайном порядке. Первое, что приходит на ум, — тасование карточной колоды, но есть и другие применения — например, случайная сортировка списка вопросов.Для решения этой задачи пригодится метод rand из


8.1.18. Обход массива

Из книги Справочник по PHP автора

8.1.18. Обход массива Как и следовало ожидать, в классе Array есть стандартный итератор each. Но имеются и другие полезные итераторы.Метод reverse_each обходит массив в обратном порядке. Результат такой же, как если бы мы вызвали сначала метод reverse, а потом each, но работает быстрее.words =


8.1.20. Обращение массива

Из книги VBA для чайников автора Каммингс Стив

8.1.20. Обращение массива Чтобы переставить элементы массива в обратном порядке, воспользуйтесь методами reverse или reverse!:inputs = ["red", "green", "blue"]outputs = inputs.reverse # ["green","blue","red"]priorities = %w(eat sleep code)priorities.reverse! #


8.2.12. Создание хэша из массива

Из книги Язык программирования Си для персонального компьютера автора Бочков C. О.

8.2.12. Создание хэша из массива Простейший способ сделать это — прибегнуть к способу создания хэшей с помощью квадратных скобок. Следующий способ годится, если массив состоит из четного числа элементов.Array =[2,3,4,5,6,7]hash = Hash[*array]# hash равно: {2=>3, 4=>5,


Создание массива

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен

Создание массива arrayСоздание и инициализация массива.Синтаксис:array array([mixed ...])Функция возвращает созданный массив. Индексы и значения в массиве разделяются оператором =. Пары index=value разделяются запятыми, они определяют индекс и значение.Индекс может быть как числовым, так


Курсор массива

Из книги Искусство программирования на языке сценариев командной оболочки автора Купер Мендель

Курсор массива resetПроизводит сброс курсора массива.Синтаксис:mixed reset(array arr)Функция reset() устанавливает внутренний курсор массива arr на его начало и возвращает значение начального элемента.Пример использования функции reset():<?php$array = array("step one", "step two", "step three", "step four"); // by default,


Ссылка на элемент массива

Из книги Язык Си - руководство для начинающих автора Прата Стивен

Ссылка на элемент массива Каждый массив в VBA имеет имя, т.е. аналог заголовка списка на листе бумаги. Чтобы работать с отдельным элементом массива, нужно сослаться на него по имени массива и индексу - целому числу, соответствующему месту элемента в массиве. Например,


Данные массива

Из книги автора

Данные массива При работе с массивами нужно помнить следующее.* Можно создавать массивы данных любых типов. VBA с успехом хранит в массивах строки, даты, денежные значения и данные любых числовых типов.* В одном массиве могут храниться данные только одного типа. Нельзя


Нумерация элементов массива

Из книги автора

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


Объявление массива

Из книги автора

Объявление массива Синтаксис:[<спецификация типа]> <описатель> [<константное выражение>];[<спецификация типа]> <описатель> [];Квадратные скобки, следующие за описателем, являются элементом языка Си, а не признаком необязательности синтаксической


Когда использовать тип массива

Из книги автора

Когда использовать тип массива Использование массивов является подходящим, когда:* элементы данных естественно принимают вид множества данных одного типа;* весь набор элементов данных в одном столбце базы данных должен быть представлен и должен управляться как одно


Инициализация двумерного массива

Из книги автора

Инициализация двумерного массива      Для инициализации массива мы взяли пять заключенных в скобки последовательностей чисел, а все эти данные еще раз заключили в скобки. Данные, находящиеся в первых внутренних скобках, присваиваются первой строке массива, данные во


Описание массива структур

Из книги автора

Описание массива структур      Процесс описания массива структур совершенно аналогичен описанию любого другого типа массива: struct book libry [MAXBKS];Этот оператор объявляет libry массивом, состоящим из MAXBKS-элементов. Каждый элемент массива представляет собой структуру типа book.


Использование массива

Из книги автора

Использование массива      Предположим, у нас есть массив структур. Имя массива является синонимом его адреса, поэтому его можно передать функции. С другой стороны, функции будет необходим доступ к структурному шаблону. Чтобы показать, как такая программа работает (рис.