Методы сортировки массива


	1 занятие Сортировка массива. Способы сортировки массива. 2 занятие Сортировка вставкой. Сортировка выбором. 3 занятие Сортировка методом простого обмена. Рекурсивная сортировка. 4 занятие Сортировка методом слияний. 5 занятие Самостоятельное решение задач.

О проекте


	— Сертификат — Рецензии и отзывы

Преподавателям


	— Пояснительная записка — Учебно-тематический план — Программа курса — Содержание курса — Требования к уровню подготовки обучающихся

Тема: Сортировка методом простого обмена. Рекурсивная сортировка.

Принцип метода:

Слева направо поочередно сравниваются два соседних элемента, и если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент ("всплыл" первый "пузырек"). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента. И так далее. Всего требуется (n-1) проход.

Задание. В тетради начертите схему работы рассмотренного алгоритма произвольно выбранного массива.

Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

Procedure Obmen(Var a : Array1);
Var
  i,j,f,g:integer;
Begin
  for i:=n downto 2 do
    for j:=1 to i-1 do
      if a[j]>a[j+1]
        then
          begin
            f:=a[j];
            a[j]:=a[j+1];
            a[j+1]:=f;
          end;
End;

Задание. Составьте программу сортировки одномерного массива рассмотренным методом.

Сортировка массива с помощью рекурсии

Рассмотрим использование рекурсии для построения алгоритма сортировки значений массива.

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

Рассмотрите процедуру, упорядочивающую по возрастанию значения из массива Massiv в диапазоне индексов Left..Right.

Procedure QuickSort (Left, Right : integer; Massiv : Array1);
Var
  i, j, x, y : integer;
Begin
  i := Left;
  j := Right;
  x := Massiv[(Left+Right) div 2];{}
  repeat
    while Massiv[i]<x do 
      Inc(i);
    while Massiv[j]>x do 
      Dec(j);
    if i<=j
      then
        begin
          y := Massiv[i];
          Massiv[i] := Massiv[j];
          Massiv[j] := y;
          Inc(i);
          Dec(j);
        end;
until i>j;
if Left<j
  then
    QuickSort (Left, j);
if i<Right 
  then
    QuickSort (i, Right);
End;

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

Вернуться назад

Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.