Необходимые определения и классификация сортировок.
Сортировка. Необходимые определения и классификация сортировок. Сортировки прямого включения и выбора. Их эффективность
Сортировка – это расположение данных в памяти в регулярном виде по их ключам. Так что при обработке данных важно знать информационное поле данных и размещение их в машине. Поэтому различают внутреннюю (сортировка в оперативной памяти) и внешнюю сортировки (сортировка во внешней памяти). Регулярность расположения элементов – это возрастание (убывание) значения ключа от начала к концу в массиве.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того чтобы их уменьшить, используют метод сортировки таблицы адресов . Этот метод применяют в таблице адресов ключей . Производят перестановку указателей, т.е. Сам массив не перемещается. При сортировке могут встретиться и одинаковые ключи. В этом случае одинаковые ключи желательно расположить после сортировки в том же порядке, что и в исходном файле. Этот принцип используется для устойчивой сортировки .
Эффективность сортировки можно рассматривать с нескольких критериев:
1) время, затрачиваемое на сортировку;
2) объем оперативной памяти, требуемой для сортировки;
3) время, затраченное программистом на написание программы.
Время, затраченное на сортировку, пропорционально количеству сравнений при выполнении сортировки и количеству перемещений элементов.
Считается, что порядок числа сравнения при сортировке может находиться в пределах от о(nlogn) до о(n 2) , где о(n) - идеальный и недостижимый случай.
Методы сортировки можно классифицировать примерно так:
1) строгие (прямые) методы (их эффективность примерно одинакова):
· прямого включения ;
· прямого выбора ;
· прямого обмена ;
2) улучшенные методы .
В жизни принцип данной сортировки присутствует при раскладывании пасьянсов, уборки квартиры, когда необходимо расположить кучу смешанных вещей в должном порядке и т.д. Очень естественный способ сортировки был применён и к упорядочиванию данных.
Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1 и исходную последовательность. В готовой последовательности элементы располагаются в заданном порядке (по убыванию или по возрастанию). А в исходной последовательности располагаются элементы, которые и нужно отсортировать. При каждом шаге элементы исходной последовательности уменьшаются на единицу, а готовая увеличивается на единицу. Это происходит из-за того, что из исходной последовательности извлекается i- й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место среди элементов готовой последовательности.
Рассмотрим пример сортировки методом прямого включения на последовательности элементов: 10, 3, 11, 8, 2, 15, 44, 9 (табл. 11.1). Необходимо её отсортировать по возрастанию.
Сначала готовая последовательность не имеет элементов. На первом шаге первый элемент исходной последовательности – это 10, становится первым элементом готовой последовательности. Далее второй шаг: элемент 3 из исходной последовательности помещается в готовую. Это происходит так. Если элемент больше 10, то он остаётся на своём месте, а если меньше, то 10 сдвигается на единицу вправо и на её место ставится элемент. Так как 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, то 11 остаётся на месте. Исходная последовательность теперь равна: 8, 2, 15, 44, 9. Последующие шаги производятся аналогичным образом.
Таблица 11.1
Принцип работы сортировки прямым включением
Число шагов в данной сортировке (табл. 11.1) равно числу элементов в сортируемой последовательности, т.е. 8 шагов = 8 элементов.
Существуют два способа реализации данного метода – это без барьера (рис. 11.1) и с барьером (рис. 11.2).
Метод: Метод косвенного измерения влажности веществ, основанный на зависимости диэлектрической проницаемости этих веществ от их влажности. Источник: РМГ 75 2004: Государственная система обеспечения еди …
КРОВЬ - КРОВЬ, жидкость, заполняющая артерии, вены и капиляры организма и состоящая из прозрачной бледножелтоват. цвета плаз мы и взвешенных в ней форменных элементов: красных кровяных телец, или эритроцитов, белых, или лейкоцитов, и кровяных бляшек, или … Большая медицинская энциклопедия
Недвижимость - (Real estate) Определение недвижимости, виды недвижимости, аренда и продажа недвижимости Информация о понятии недвижимость, виды недвижимости, аренда и продажа недвижимости, налогообложение и страхование Содержание - это вид имущества,… … Энциклопедия инвестора
У этого термина существуют и другие значения, см. C. См. также: Си (язык программирования) C++ Семантика: мультипарадигмальный: объектно ориентированное, обобщённое, процедурное, метапрограммирование Тип исполнения: компилируемый Появился в … Википедия
ОЦЕНКА СТОИМОСТИ НЕМАТЕРИАЛЬНЫХ АКТИВОВ - (англ. intangible assets appraisal) – определение стоимости объема прав предприятия на определенную группу объектов, не имеющих материально вещественного содержания и приносящих предприятию доход в течение периода, оговоренного национальным… … Финансово-кредитный энциклопедический словарь
ШКОЛА общеобразовательная - уч. воспитат. учреждение, базовый элемент образоват. системы. В этом качестве Ш. предмет исследования разл. дисциплин: пед., ист., демографич., социология, и др. Только в педагогике проблематика Ш. занимает вполне самостоят. место. Изученность… … Российская педагогическая энциклопедия
время - 3.3.4 время tE (time tE): время нагрева начальным пусковым переменным током IА обмотки ротора или статора от температуры, достигаемой в номинальном режиме работы, до допустимой температуры при максимальной температуре окружающей среды. Источник … Словарь-справочник терминов нормативно-технической документации
ГОСТ Р МЭК 60204-1-2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования - Терминология ГОСТ Р МЭК 60204 1 2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования оригинал документа: TN систем питания Испытания по методу 1 в соответствии с 18.2.2 могут быть проведены для каждой цепи… … Словарь-справочник терминов нормативно-технической документации
автоматический - 3.3.1 автоматический пробоотборник (automatic sampler): Устройство, используемое для извлечения представительной пробы жидкости, протекающей по трубопроводу. Примечание Автоматический пробоотборник обычно состоит из зонда (щупа), экстрактора… … Словарь-справочник терминов нормативно-технической документации
напряжение - 3.10 напряжение: Отношение растягивающего усилия к площади поперечного сечения звена при его номинальных размерах.
Для сортировки (упорядочения) по возрастанию или убыванию значений в массиве разработано множество методов [Вирт, Кнут. т 3].Рассмотрим три из них, считая, для определённости, что первые n, n=6, элементов массива Х
На каждом следующем i-том шаге, i=2, 3,…,n-1, значение из (i+1)-ой ячейки массива путем обмена положением с числом из предыдущей ячейки продвигают в сторону уменьшения индекса ячейки до тех пор, пока ни окажется, что в предыдущей ячейке находится меньшее число.
Из сказанного следует, что при реализации метода прямого включения внешний цикл должен выполняться n-1 раз, а максимально возможное число выполнений внутреннего цикла, в теле которого должны выполняться сравнения и перестановки чисел, будет увеличиваться от 1 до n-1. Однако внутренний цикл следует организовать так, чтобы он заканчивался или вообще не выполнялся при наступлении условия: значение в предыдущей ячейке массива меньше, чем в текущей.
В нашем примере:
При i=2 число 15 из ячейки Х 3 последовательно обменяется местами с числом 34 из ячейки Х 2 , а затем с числом 21 из ячейки Х 1 ,
При i=4 число 25 из ячейки Х 5 обменяется местами с числом 34 из ячейки Х 3 ,
Ниже представлен фрагмент программы упорядочения по возрастанию первых n элементов массива X методом прямоговключения (включения с сохранением упорядоченности) .
while (X
R:=X[j];
X[j]:=X;
X:=R;
for i:=1 to n-1 do
Для упорядочения чисел в массиве по убыванию достаточно на каждом шаге изменить условие перестановки чисел в соседних ячейках массива на обратное, а именно, обмен значениями соседних ячеек выполнят в случае, когда предыдущее меньше текущего.
Метод прямого обмена (метод пузырька).
Этот метод, как и предыдущий, основан на обмене значениями соседних ячеек массива, но с первого же шага в последовательном анализе, при движении от одного конца массива к другому, участвуют все пары соседних ячеек массива.
На первом шаге последовательно, для j = n, n-1, …,2, сравниваются значения соседних ячеек массива, и при выполнении условия Х j <Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .
В нашем примере после выполнения первого шага данные в массиве расположатся так:
На каждом следующем шаге число проверяемых пар ячеек будет уменьшаться на 1. В общем случае, на любом шаге i, i=1, 2, 3, …, n-1, процесс будет выполняться для j от n до i+1, в частности, при i= n-1 – только один раз для n-ой и (n-1)-вой ячеек.
Из сказанного следует, что при реализации метода прямого обмена внешний цикл должен выполняться n-1раз, а число выполнений внутреннего цикла, в теле которого должны выполняться сравнения и перестановки чисел, будет уменьшаться от n-1 до 1.
Происхождение термина “метод пузырька” объясняется так: если представить вертикальное расположение ячеек массива с ростом индекса сверху вниз, то самое маленькое число из рассматриваемых будет подниматься вверх подобно пузырьку в воде.
В нашем примере
При i=3 перестановки приведут к следующему состоянию массива
При использовании метода пузырька не имеет значения, в сторону увеличения или в сторону уменьшения индексов продвигается анализ пар чисел в массиве, а вид упорядочения (по возрастанию или убыванию) определяется только условием перестановки чисел (меньшее должно расположиться за большим или наоборот).
Модифицированный метод прямого обмена (модифицированный метод пузырька).
Как видно из приведенного выше числового примера массив оказался упорядоченным уже после четвёртого шага, то есть возможновыполнение внешнего цикла не n-1 раз, а меньше, когда станет известно, что массив уже упорядочен. Такая проверка основывается на следующем: если при выполнении внутреннего цикла не было ни одной перестановки, значит массив уже упорядочен и можно выйти из внешнего цикла. В качестве признака, выполнялась ли перестановка, используют переменную булевского типа: до входа во внутренний цикл ей дают одно значение, например, False, а при выполнении перестановки – другое, например, True.
Очевидно, эффект при использовании модифицированного метода пузырька по сравнению с не модифицированным методом в ускорении процесса сортировки будет наблюдаться, если исходная последовательность чисел близка к упорядоченности в нужном направлении. В предельном случае, когда массив уже упорядочен нужным образом тело внешнего цикла будет выполнено только один раз.
Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже «готовую» последовательность A 1 , A 2 ,…, A i -1 , и «оставшуюся» (не сортированную) часть: A i , A i +1 ,…, A N .
Суть метода заключается в том, что при каждом i-ом шаге (начиная с i = 2), из неотсортированной части извлекается i-ый элемент и помещается в «готовую» часть, при этом он вставляется на нужное место.
Текстовый алгоритм метода:
1. Начало.
2. Выполнить цикл, пока i имеет значения от 2 до N,
шаг = 1:
а) i-ый элемент (A(i)) поместить в ячейку A(0);
б) присвоить j = -1, то есть j равно номеру элемента, находящегося слева от испытуемого (i-го) и таким образом стоящего в «готовой» последовательности;
в) если А(0) ≥ А(j), то элемент А(0) поместить в ячейку А(j+1), иначе элемент А(j) поместить в ячейку А(j+1), уменьшить значение j на единицу и вновь выполнить пункт в).
На рис. 1 представлена блок-схема сортировки методом прямого включения.
Метод работает следующим образом: на i-ом шаге (начиная с i = 2) i-ый элемент помещается в свободную ячейку (например, А(0)). Этот элемент сравнивается со стоящим в «готовой» части слева от него элементом. Если элемент А(0) меньше, то происходит сдвиг вправо сравниваемого (j-го элемента) на одну позицию, после чего для сравнения берется следующий элемент. Если же элемент А(0) при сравнении оказывается не меньше, то он помещается на место, стоящее сразу за сравниваемым элементом.
Рис. 1. Блок-схема сортировки методом прямого включения
На рис. 2 приведен пример выполнения сортировки методом прямого включения.
| Исходная последовательность | |||||||||
| А (0) | |||||||||
| I = 2 |  | ||||||||
| I = 3 | |||||||||
| I = 4 | |||||||||
| I = 5 | |||||||||
| I = 6 | |||||||||
| I = 7 | |||||||||
| I = 8 | |||||||||
| Результат |
Рис. 2. Пример сортировки методом прямого включения
Сортировка прямым включением больше подходит для случая, когда сортируемые данные поступают последовательно (одно за другим).
Сортировка методом прямого выбора
Суть метода заключается в следующем. Выбирается наименьший элемент в «оставшейся» (неотсортированной) части и меняется местами с первым элементом (в этой же неотсортированной части). После этого длина неотсортированной части уменьшается на один элемент (на первый), и весь процесс продолжается уже с (n – 1) элементами, затем с (n – 2) элементами и т.д., до тех пор, пока не останется один, самый большой элемент.
Этот метод в некотором смысле противоположен методу прямого включения. В методе прямого включения на каждом шаге рассматривается только один очередной элемент и все элементы уже «готовой» части последовательности, среди которых отыскивается точка включения этого очередного элемента. А в методе прямого выбора для поиска одного (минимального) элемента просматривают все элементы неотсортированной части, и этот минимальный элемент помещается как очередной элемент в уже «готовую» часть.
Текстовый алгоритм метода:
1. Начало.
2. Выполнить цикл, пока i имеет значения от 1 до N – 1,
шаг = 1:
а) поместим текущий (i-ый) элемент в какую-нибудь ячейку памяти (Х) и запомним порядковый номер (i) текущего элемента (в переменной К);
б) выполнить цикл, пока j имеет значения от i + 1 (то есть от следующего за i элемента) до N, шаг = +1:
тело цикла: если Х > А(j), то помещаем в ячейку Х элемент А(j) и запоминаем его номер в ячейке К;
в) присвоить А(К) = А(i) и А(i) = Х.
На рис. 3 приведен пример выполнения сортировки методом прямого выбора.
| Исходная последовательность | 44 | 06 | ||||||
| I = 1 | 55 | 12 | ||||||
| I = 2 | 55 | 18 | ||||||
| I = 3 | 42 | 55 | ||||||
| I = 4 | 94 | 44 | ||||||
| I = 5 | 55 | 94 | ||||||
| I = 6 | 94 | 67 | ||||||
| I = 7 |
Рис. 3. Пример сортировки методом прямого выбора
Цель работы Исследовать сортировку массива методом прямого включения и оценить эффективность этого алгоритма.Общие сведения
Сортировка методом прямого включения, так же, как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов. Сортировка этим методом производится последовательно шаг за шагом. На k-м шаге считается, что часть массива, содержащая первые k-1 элемент уже упорядочена, то есть. Далее необходимо взять k-й элемент и подобрать для него место в отсортированной части массива такое, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое что. Затем надо вставить элемент a[k] на найденное место. С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг. Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента х. Поступим следующим образом: будем просматривать элементы, расположенные левее х (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы а[j], j изменяется от k-l до 1. Такой просмотр закончится при выполнении одного из следующих условий: найден элемент а[j]Пример Коротко опишем фрагмент алгоритма сортировки с помощью прямого включения: For k:= 2 to n do begin x:= a[k]; j:= k-1; { вставить х на подходящее место в a, …, a[k] } { для этого организуем цикл, которые выполняется, пока } { j > 0 и xКонтрольное задание
Написать программу вставки последнего элемента массива после первого отрицательного элемента этого же массива.Варианты заданий
ВНИМАНИЕ!!! Если явно не указано иное, входные данные (исходный массив) и выходные данные (отсортированный массив) формировать в виде текстового файла, содержащего целые числа! Для всех заданий предварительно написать процедуру сортировки массива методом прямого включения. 1. Дан ряд, содержащий n элементов. Отсортировать их в порядке возрастания, отбрасывая при этом все повторяющиеся элементы. 2. Определить моду данного ряда – значение, встречающееся среди его элементов чаще всего. 3. Исходный набор данных представляет собой последовательность записей, состоящих из фамилии, возраста и стажа работы. Распечатать этот список: 1) в алфавитном порядке; 2) в порядке увеличения возраста; 3) в порядке увеличения стажа работы. 4. Написать процедуру сортировки по убыванию. 5. Дан ряд целых чисел. Получить в порядке возрастания все различные числа, входящие в этот ряд. 6. Дан ряд из n различных целых чисел. Получить различные целые числа такие, что
7.
Даны целые Найти наибольшее значение в этой последовательности после выбрасывания из нее всех членов со значением
8.
Даны натуральные
Числа – это измеренные в сотых долях секунды результаты n спортсменов в беге на 100 м. Составить команду из четырех лучших бегунов для участия в эстафете 4х100, т. е. указать одну из четверок натуральных чисел i, j, k, l такую, что сумма 
имеет наименьшее значение.
9.
Дано n независимых случайных точек, с координатами (xi; yi), равномерно распределенных в круге радиуса 1 с центром в начале координат. Напишите программу, располагающую точки в порядке возрастания расстояния от центра.
10.
Даны n целых положительных двузначных чисел. Трактуя каждое число как пару цифр из интервала 0–9, отсортировать их (цифры) по возрастанию.
11.
Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся замкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.)
Подсказка. Возьмем самую левую точку (т.е. точку с наименьшей x-координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке) и возвращается по верхнему лучу.
12.
Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на вбитые в доску гвозди - их выпуклая оболочка.)
Указание. Упорядочим точки. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек.
