Лабораторная работа № 6 . "СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ"

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

Цель работы: исследовать и изучить методы сортировки включением.


Задача работы: овладеть навыками написания программ для сортировки методом прямого включения на языке программирования ПАСКАЛЬ .


Порядок работы :

• 
  изучить описание лабораторной работы;

• 
  по заданию, данному преподавателем, разработать алгоритм программы решения задачи;

• 
  написать программу на языке ПАСКАЛЬ;

• 
  отладить программу;

• 
  решить задачу;

• 
  оформить отчет.

Краткая теория

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

Различают следующие типы сортировок:

• 
  внутренняя сортировка - это сортировка, происходящая в оперативной памяти машины

• 
  внешняя сортировка - сортировка во внешней памяти.

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

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

Эффективность сортировки можно рассмотреть с нескольких критериев:

• 
  время, затрачиваемое на сортировку

• 
  объем оперативной памяти, требуемой для сортировки

• 
  время, затраченное программистом на написание программы

Рассмотрим второй критерий подробнее: мы можем подсчитать количество сравнений при выполнении сортировки или количество перемещений.

Предположим, что число сравнений определяется формулой:

C = 0,01n² + 10n

Если n<1000, то второе слагаемое больше.

Если n>1000, то первое слагаемое больше.

То есть, при малых n порядок сравнения равен , а при больших n он равен n.

Различают следующие методы сортировки:

• 
  строгие (прямые) методы

• 
  улучшенные методы

Рассмотрим преимущества прямых методов:

1. Об этом говорит сайт https://intellect.icu . Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.

2. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.

3. Усложненные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.


Методы сортировки "на том же месте" можно разбить в соответствии с определяющими их принципами на 3 категории:

1. Сортировки с помощью включения (by insertion)

2. Сортировки с помощью выделения (by selection)

3. Сортировки с помощью обменов (by exchange)


сортировка методом прямого включения


Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже "готовую" последовательность a(1),...,a(i-1) и исходную последовательность. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

Алгоритм

Алгоритм сортировки прямым включением таков:

for x:=2 to n do

x:=a[i]

включение х на соответствующее место среди a[1]...a[i]

end

В реальном процессе поиска подходящего места удобно, чередуя сравнения 

сравнивается с очередным элементом a( j ), а затем либо х вставляется на свободное место, либо a( j ) сдвигается (передается) вправо и процесс "уходит" влево. Обратите внимание, что процесс просеивания может закончиться при выполнении одного из двух следующих различных условий:

1. Найден элемент a( j ) с ключом, меньшим, чем ключ у х.

2. Достигнут левый конец готовой последовательности.


Procedure StraightInsertion

Var

i,j:index; x:item;

begin

for i:=2 to n do

x:=a[i]; a[0]:=x; j:=1;

while x<a[j-1] do="" a[j-1]:="a[j-1];" j:="j-1;" end;<br=""> 
a[j]:=x

end

end StraightInsertion

Задания

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

Требуется (согласно варианту) :

1.Расположить по алфавиту имена владельцев и, соответственно, вывести информацию об их машинах.

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

3.Вывести по убыванию количество всех предыдущих ремонтов машин марки "Жигули".

4.Вывести по убыванию номера тех машин, количество предыдущих ремонтов которых равно 2.

5.Вывести по возрастанию даты конца ремонта всех машин, которые ранее не ремонтировались.

6.Вывести по алфавиту в обратном порядке владельцев автомобилей марки "Мерседес"

7.Вывести по алфавиту марки машин, которые должны быть отремонтированы раньше всех (дата конца ремонта меньше 01.08.96).

8.Вывести по возрастанию номера машин марки "Жигули".

9.Вывести по алфавиту имена владельцев, чьи машины не ремонтировались с прошлого года.

10.Вывести машины, которые надо отремонтировать к следующему месяцу по возрастанию даты их последнего ремонта.

11. Вывести по алфавиту в обратном порядке имена владельцев, количество предыдущих ремонтов машин которых больше трех.

12. Вывести по убыванию номера машин марки "Мерседес".

 

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

Из статьи мы узнали кратко, но содержательно про сортировка методом прямого включения