Сортировки массивов.
план-конспект урока по информатике и икт (10 класс) на тему

Сортировка массива методом простого обмена (методом пузырька)

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

Метод основан на том, что в процессе исполнения алгоритма более "легкие" элементы массива постепенно "всплывают".

Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Выполняется несколько последовательных просмотров  массива от начала к концу. Если соседние элементы расположены "неправильно", то они меняются местами.

Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n–1 раз, каждый раз уменьшая диапазон просмотра на один элемент.

Ниже приведен текст программы сортировки массива по возрастанию методом пузырька.

Для упорядочения элементов массива по убыванию их значений необходимо при сравнении элементов массива знак ">" заменить на "<".

Метод простого выбора

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

  const N=10; {Количество элементов массива}

  var a: array[1..N] of integer; {массив}

  i,j: integer; {счётчики для цикла}

  c:   integer; {Переменная для промежуточного хранения}

  c2:  integer; {Переменная для промежуточного хранения}

  .......

for i:=1 to N-1 do begin 

  {цикл по первому обрабатываемому элементу массива}

  c2:=i; {индекс предполагаемого минимального элемента}

  for j:=i+1 to N do 

    {поиск минимального элемента}

    if a[c2]>a[j] then c2:=j; {если в c2 индекс не минимального элемента,

                            то в c2 записывается индекс меньшего элемента}

    c:=a[i];a[i]:=a[c2];a[c2]:=c; {Меняем местами элемент массива}

end;

Метод Шелла

Метод Шелла аналогичен методу сортировки "пузырьком", однако работает с далеко отстоящими друг от друга элементами массива.

  const N=10; {Количество элементов массива}

  var a:       array[1..N] of integer; {массив}

      p:       boolean; {флаг наличия перестановки}

      l,d,i,j: integer; {служебные переменные}

  ...........

d:=N div 2; {Расстояние между обрабатываемыми элементами массива, на каждом этапе алгоритма уменьшается в 2 раза вплоть до 0, когда происходит остановка алгоритма}

while d>0 do

begin

  for j:=1 to N-d do {Перебор всех пар элементов массива,

             расстояние между которыми равно d}

  begin

    l:=j                {запоминаем индекс текущего элемента}

    repeat

      p:=false;                {пока элементы не переставлялись}

      if a[l]then begin {если порядок нарушен, то}

        c:=a[l];a[l]:=a[l+d];a[l+d]:=c; {меняем местами элементы массива}

        l:=l-d;        перейдём к той паре, в которую

                        входит меньший из переставленных элементов}

        p:=true;                        {запомним, что была перестановка}

      end;

    until (l<=1) and p; {продолжаем, пока идут перестановки и

                                    не произошёл выход за пределы массива}

  end;

  d:=d div 2;        {Уменьшим расстояние между сравниваемыми элементами в 2 раза}

end;

ЗАДАЧИ НА УРОК:

1. Дан целочисленный массив из 10 элементов. Вывести на экран все его четные элементы, предварительно расположив их по убыванию методом пузырька.

2. Дан целочисленный массив из 10 элементов. Вывести на экран все его нечетные элементы, предварительно расположив их по возрастанию методом простого выбора.

3. Дан целочисленный массив из 10 элементов.  Выполнить сортировку элементов, записанных на нечетных местах.

4. Дан целочисленный массив из 10 элементов. Отсортировать отрицательные по убыванию, положительные – по возрастанию, оставив отрицательные на местах, принадлежащих отрицательным, а положительные – на местах, принадлежащих положительным. Вывести на экран исходный и полученный массивы. Дополнительных массивов не использовать.