Лабораторная работа № 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-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

Алгоритм

К прямым методам относится метод прямого выбора.

Рассматриваем весь ряд массива и выбираем элемент меньший или больший элемента а(i), определяем его место в массиве - k, и затем меняем местами элемент а(i) и элемент а(k).

for i = 1 to n - 1

x = a(i)

k = i

for j = i + 1 to n

if x > a(j) then 

k = j

x = a(k)

endif

next j

a(k) = a(i)

a(i) = x

next i

return

for i := 1 to n - 1 do

begin

x := a[i];

k := i;

for j := i + 1 to n do

if x > a[j] then 

begin

k := j;

x := a[k];

end;

a[k] := a[i];

a[i] := x;

end; 


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

• 
  Количество сравнений

• 
  Количество перемещений, когда массив упорядочен

• 
  Количество перемещений когда массив обратно отсортирован

В худшем случае сортировка прямым выбором дает порядок n², как и для числа сравнений, так и для числа перемещений.

Задания

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

1. Фамилий студентов по алфавиту.

2. Фамилий студентов по алфавиту в обратном порядке.

3. Студентов по старшинству (начиная со старшего).

4. Студентов по старшинству (начиная с младшего).

5. Студентов по общему баллу (по возрастанию).

6. Студентов по общему баллу (по убыванию).

7. Студентов по результатам 1-го экзамена (по возрастанию).

8. Студентов по результатам 2-го экзамена (по убыванию).

9. Студентов по результатам 3-го экзамена (по возрастанию).

10. Студентов по результатам 4-го экзамена (по убыванию).

11. Имен в алфавитном порядке.

12. Имен в обратном алфавитном порядке.

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

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