Пример 25-6. Старая, добрая: "Пузырьковая" сортировка

Пример 25-6. Старая, добрая: "Пузырьковая" сортировка

#!/bin/bash

# bubble.sh: "Пузырьковая" сортировка.

# На каждом проходе по сортируемому массиву,

#+ сравниваются два смежных элемента, и, если необходимо, они меняются местами.

# В конце первого прохода, самый "тяжелый" элемент "опускается" в конец массива.

# В конце второго прохода, следующий по "тяжести" элемент занимает второе место снизу.

# И так далее.

# Каждый последующий проход требует на одно сравнение меньше предыдущего.

# Поэтому вы должны заметить ускорение работы сценария на последних проходах.

exchange()

{

# Поменять местами два элемента массива.

local temp=${Countries[$1]} # Временная переменная

Countries[$1]=${Countries[$2]}

Countries[$2]=$temp

return

}

declare -a Countries # Объявление массива,

#+ необязательно, поскольку он явно инициализируется ниже.

# Допустимо ли выполнять инициализацию массива в нескольки строках?

# ДА!

Countries=(Нидерланды Украина Заир Турция Россия Йемен Сирия

Бразилия Аргентина Никарагуа Япония Мексика Венесуэла Греция Англия

Израиль Перу Канада Оман Дания Уэльс Франция Кения

Занаду Катар Лихтенштейн Венгрия)

# "Занаду" -- это мифическое государство, где, согласно Coleridge,

#+ Kubla Khan построил величественный дворец.

clear # Очистка экрана.

echo "0: ${Countries[*]}" # Список элементов несортированного массива.

number_of_elements=${#Countries[@]}

let "comparisons = $number_of_elements - 1"

count=1 # Номер прохода.

while [ "$comparisons" -gt 0 ] # Начало внешнего цикла

do

index=0 # Сбросить индекс перед началом каждого прохода.

while [ "$index" -lt "$comparisons" ] # Начало внутреннего цикла

do

if [ ${Countries[$index]} > ${Countries[`expr $index + 1`]} ]

# Если элементы стоят не по порядку...

# Оператор > выполняет сравнение ASCII-строк

#+ внутри одиночных квадратных скобок.

# if [[ ${Countries[$index]} > ${Countries[`expr $index + 1`]} ]]

#+ дает тот же результат.

then

exchange $index `expr $index + 1` # Поменять местами.

fi

let "index += 1"

done # Конец внутреннего цикла

let "comparisons -= 1" # Поскольку самый "тяжелый" элемент уже "опустился" на дно,

#+ то на каждом последующем проходе нужно выполнять на одно сравнение меньше.

echo

echo "$count: ${Countries[@]}" # Вывести содержимое массива после каждого прохода.

echo

let "count += 1" # Увеличить счетчик проходов.

done # Конец внешнего цикла

exit 0

--

Можно ли вложить один массив в другой?

#!/bin/bash

# Вложенный массив.

# Автор: Michael Zick.

AnArray=( $(ls --inode --ignore-backups --almost-all

--directory --full-time --color=none --time=status

--sort=time -l ${PWD} ) ) # Команды и опции.

# Пробелы важны . . .

SubArray=( ${AnArray[@]:11:1} ${AnArray[@]:6:5} )

# Массив имеет два элемента, каждый из которых, в свою очередь, является массивом.

echo "Текущий каталог и дата последнего изменения:"

echo "${SubArray[@]}"

exit 0

--

Вложенные массивы, в комбинации с косвенными ссылками, предоставляют в распоряжение программиста ряд замечательных возможностей

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

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

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

Сортировка

Из книги Использование ListView в режиме виртуального списка автора Чадов Тимофей

Сортировка Трудности? Это еще что такое? Однако бесплатный сыр сами знаете где. Дело в том, что, так как сами элементы в списке не хранятся, придется самим заботится о сортировке. Не удастся воспользоваться функцией CListCtrl::SortItems, бесполезно писать CompareItems и т.п. Все, что у вас


Сортировка

Из книги Windows Vista автора Вавилов Сергей

Сортировка В отличие от предыдущих версий в Проводнике Windows Vista заголовки столбцов, с помощью которых можно проводить сортировку объектов и другие действия, доступны при любом способе отображения значков.Щелчком кнопки мыши на заголовке любого столбца вы можете


Старая и новая структуры задания

Из книги Основы AS/400 автора Солтис Фрэнк

Старая и новая структуры задания С появлением модели процессов ILE, описанной ранее, изменилась и структура задания в AS/400. Как именно — можно понять, сравнив ресурсы приложений, доступные в старой и новой структурах заданий, а также особенности их использования. Как


Кафедра Ваннаха: Добрая Вселенная в Мире Дарвина Ваннах Михаил

Из книги Цифровой журнал «Компьютерра» № 52 [17.01.2011 — 23.01.2011] автора Журнал «Компьютерра»

Кафедра Ваннаха: Добрая Вселенная в Мире Дарвина Ваннах Михаил Опубликовано 18 января 2011 года Разумная жизнь на нашей голубой планете есть следствие естественного отбора. Беспощадной эволюции с когтями и клыками. И прогресс общества — наследие


8.2.10. Сортировка хэша

Из книги Технология XSLT автора Валиков Алексей Николаевич

8.2.10. Сортировка хэша Хэши по природе своей не упорядочены ни по ключам, ни по значениям. Чтобы отсортировать хэш, Ruby преобразует его в массив, который затем сортирует. Понятно, что и результатом является массив.names = {"Jack"=>"Ruby","Monty"=>"Python",         "Blaise"=>"Pascal", "Minnie"=>"Perl"} list =


Сортировка

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

Сортировка При преобразовании документа элементами xsl:for-each и xsl:apply-templates, выбранные узлы по умолчанию обрабатываются в порядке просмотра документа, который зависит от выражения, использованного в атрибуте select этих элементов. XSLT позволяет изменять этот порядок


Шейкер-сортировка

Из книги Знакомьтесь, информационные технологии автора Воловник Аркадий Авральевич


«Старая» модель обработки сигнала

Из книги Linux программирование в примерах автора Роббинс Арнольд

«Старая» модель обработки сигнала В ранних версиях UNIX была принята единственная модель обработки сигналов, основанная на функции signal(), которая подразумевает семантику так называемых «ненадежных сигналов», принятую в этих ОС. Позже эта модель была подвержена


Единая экономика – «старая» и «новая»

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

Единая экономика – «старая» и «новая» Глобализация. Информационные технологии. Internet. Качественное изменение производства. Новые формы производственных отношений. Новый образ


6.2.1.1. Пример: сортировка сотрудников

Из книги Разработка ядра Linux автора Лав Роберт

6.2.1.1. Пример: сортировка сотрудников Для более сложных структур требуются более сложные функции. Например, рассмотрите следующую (довольно тривиальную) struct employee:struct employee {char lastname[30];char firstname[30];long emp_id;time_t start_date;};Мы могли бы написать функцию для сортировки сотрудников по


ПРИМЕР: СОРТИРОВКА СТРОК

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

ПРИМЕР: СОРТИРОВКА СТРОК      Возьмем реальную задачу сортировки строк в алфавитном порядке. Эта задача может возникнуть при подготовке списка фамилий, при создании алфавитного указателя и во многих других ситуациях. В такой программе одним из главных инструментов


Старая хеш-таблица страниц

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

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