Описание матрицы

Сортировка Хоара (быстрая сортировка)

Метод предложен Ч.Э.Р.Хоаром в 1962 году. Эту сортировку называют быстрой потому, что она на практике оказывается самым быстрым методом из тех алгоритмов, которые оперируют сравнениями. Более того, он считается одним из лучших разработанных на сегодняшний день универсальных методов. Этот метод является ярким примером принципа «разделяй и властвуй».

Принцип метода. Алгоритм быстрой сортировки построен на основе идеи разбиения массива на разделы. В массиве выбирается некоторый элемент Х (барьерный элемент или компаранд), который разбивает массив на две части. Нашей целью является поставить его на свое место K, т.е. чтобы в одной части массива (например, слева) находились элементы, меньшие Х, а в другой (например, справа) – большие Х. Для этого все меньшие элементы переносятся в одну часть массива, а большие – в другую. В результате массив разделился на две неупорядоченные части, барьером между которыми является k-ый элемент. Следующий шаг – это независимо отсортировать левую и правую части массива. И так далее, пока эти части не окажутся состоящими из одного элемента.

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

Среднее число сравнений – n/6 log n, среднее число перестановок – n log n.

Двумерный массив (матрица)

Двумерный массив – это структура данных, моделирующая собой двумерную таблицу однотипных элементов. Другое название двумерного массива – матрица. Матрицы давно применяются в математике. Наиболее наглядный способ представления матрицы – это таблица прямоугольной или квадратной формы. Для двумерного массива А с размером M*N (M строк, N столбцов) таблица может быть такой:

Направление изменения второго индекса – номера столбца
Направление изменения первого индекса – номера строки	А					…	N
…
M

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

Положение элемента в матрице определяется двумя индексами – номером строки и номером столбца. Индексы указываются в квадратных скобках через запятую, причем то, что указано на первом месте считается номером строки, а то, что на втором – номером столбца.

Для описания массива можно использовать два способа:

Дата добавления: 2014-03-11; просмотров: 290; Нарушение авторских прав

Мы поможем в написании ваших работ!