Лабораторная работа № 8."СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ОБМЕНА"

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

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


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


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

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

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

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

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

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

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

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

Пузырьковая сортировка

Идея : (N-1) раз массив проходится снизу вверх (сверху вниз), при этом элементы попарно сравниваются, если нижний элемент меньше верхнего, то элементы переставляются.

Пример : массив - 4, 3, 7, 2, 1, 6.





Можно улучшить "пузырьковый" метод, если проходить массив элементов и вверх и вниз одновременно.

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



Количество перемещений :




Пример вычисления "пузырьковым" методом





На примере представлен массив из пяти элементов, это означает, что массив проходится снизу вверх (сверху вниз) 5-1=4 раза. Об этом говорит сайт https://intellect.icu . Так же на примере видно, что алгоритм "в пустую" обрабатывает массив начиная уже с третьего шага внутреннего цикла, а 4-й шаг можно уже не выполнять.

Преимущества данного метода :

1) Самый простой алгоритм

2) Простой в реализации

3) Не нужно дополнительных переменных

Недостатки:

1) Долго обрабатывает большие массивы

2) В любом случае количество проходов не уменьшается


Quiksort - метод быстрой сортировки

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

Пример :





После первого прохода выбранный элемент становится на свое место.


Улучшение "пузырькового" метода.

1) Если проходить массив не только сверху вниз, но и снизу вверх одновременно, то не только "легкие" элементы будут "всплывать", но и "тяжелые" "тонуть".

2. 
   Для отмены прохода массива "впустую" нужно в во внешний цикл вставить проверку на отсортированность массива.

Алгоритм

Алгоритм пузырькового метода

(ПСЕВДОКОД)

for i=2 to n

for j=n to i step -1

if A( j-1 ) > A( j ) then

x=A( j-1 )

A( j-1 )=A( j )

A( j )=x

end if

next j

next i 

Алгоритм метода Quiksort

(ПСЕВДОКОД)

Sub Sort(L,R)

i=l

j=r

x=A(( l+r ) div 2 )

while A( i ) < x do

i=i+1

end while

while A( j )>x do

j=j-1

end while

if i<=j then 

Y=A( i )

A( i )=A( j )

A( j )=Y

while i>j do

if l 
sort( l,j )

end if

if i 
sort( i,r )

end if

return

sub Quiksort 

sort ( 1, n )

return


Число перестановок и сравнений: (n* log( n )).

Задания

Варианты:

1. Составить программу вывода на экран самого большого (самого малого) элемента массива А.

2. Составить программу сортировки массива А по убыванию величин его элементов.


3. В массиве А находятся элементы. Составить программу, которая сформирует массив В, в котором расположить элементы масива В в порядке убывания.


4. Дан упорядоченный массив А - числа, расположенные в порядке возрастания, и число а, которое необходимо вставить в массив А, так, чтобы упорядоченность массива сохранилась.


5. Составить программу для быстрой перестройки данного массива А, в котором элементы расположены в порядке возрастания, так, чтобы после перестройки эти же элементы оказались расположенными в порядке убывания. 


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


7. Составить программу, которая будет из массива А брать одно число за другим и формировать из них массив В, располагая числа в порядке возрастания.


8. Дан список авторов в форме массива А. Составить программу формирования указателя авторов в алфавитном порядке и вывести его на экран.


9. Имеется n абонентов телефонной станции. Составить программу, в которой формируется список по форме: номер телефона, фамилия (номера идут в порядке возрастания). 


10. Имеется n слов различной длины, все они занесены в массив А. Составить программу упорядочения слов по возрастанию их длин.


11. Составить программу для сортировки массива А по возрастанию и убыванию модулей его элементов.


12. В отсортированный массив А между каждой соседней парой элементов вставить число больше левого и меньше правого элемента в массиве и вывести полученный массив на экран.

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

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