Методы программирования: Методическое пособие для выполнения лабораторных работ, страница 5

Метод 2. Сортировка простыми вставками

Условно разделить массив A на отсортированную и несор­ти­ро­ван­ную части. К сортированной части сначала относится только первый элемент.

цикл по i от 2 до N  с шагом 1 выполнять

// i – номер первого элемента в несортированной части

  // массива

   x:= A[i];                      

     j := i – 1;

     // Все элементы из отсортированной части, большие,

   // чем x, сдвинуть на одну позицию вправо:

   пока j>0 и A[j]>x выполнять

        A[j+1] := A[j];             

        j := j – 1;                 

     конец пока      

     // Элемент x поставить на свое место по порядку:

A[j+1] := x;                    

конец цикла                       

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

цикл по i от 2 до N с шагом 1 выполнять

// проход от конца массива к началу:

цикл по j от N до i с шагом -1 выполнять

   // если два рядом стоящих элемента нарушают

   // порядок по возрастанию, то их поменять местами.

      если A[j] < A[j–1] то Обмен(j, j–1);  

   конец цикла

конец цикла

Метод 3(2). Сортировка простыми обменами (шейкерная сортировка)

Пусть F — логическая переменная, принимающая истинное зна­че­ние, если во время прохода по массиву были обмены двух рядом стоя­щих элементов, left – левая граница несортированной части мас­си­ва, а right – ее правая граница.

left := 1;         

right := N;

F := истина; 

пока F выполнять

    F:= ложь;

    i:= left;

    //Проход по массивуот начала к концу:

  пока i < right выполнять  

       если A[i] > A[i + 1]

       то // переставить два рядом стоящих элемента,

           // нарушающие порядок:

    начало

      Обмен (i, i+1);   

            F := истина;

          конец

       i := i + 1;

  конец пока

  // Сдвинуть правую границу влево на одну позицию:

right := right – 1;           

// Если были обмены во время предыдущего прохода,

если F

то // совершить проход по массиву от конца

   // к началу:

  начало

     F := ложь;

     i:= right;                     

          пока i > left выполнять

             если A[i] < A[i – 1]

    то// переставить рядом стоящие элементы,

// нарушающие порядок:

            начало

               Обмен (i, i–1);       

               F := истина;

            конец

          i := i – 1;

        конец пока

     конец

   // Сдвинуть левую границу вправо на одну позицию:

   left := left + 1;

конец пока // Цикл повторять до тех пор, пока F не

         //останется равной значению ложь.

Метод 4. Сортировка подсчетом

Условно разделить массив A на отсортированную и несортированную части. Пусть i – номер первого элемента в несортированной части массива.

i := 1; 

пока i < N выполнять

   r:= 1;

// Посчитать количество элементов в массиве, меньших

   // i-го элемента и записать это число в переменную r

   цикл по j от 1 до N с шагом 1 выполнять

еслиA[i] > A[j]

то r := r + 1;

   конец цикла

   если r£ i  // i-й элемент стоит на своем месте,

   то  // увеличить сортированную часть на 1 элемент

      i := i + 1

   иначе

      начало

// вычислить позицию, куда нужно поставить

          // i-й элемент:

         покаA[r] = A[i]выполнять

            r:= r+1

   конец пока

   // поменять его местами с тем элементом,

   // который в этой позиции находится:

         Обмен (r, i)

конец;

конец пока

Язык реализации – С.

Лабораторная работа № 8.  Улучшенные сортировки

Задание

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

Использовать следующие алгоритмы, описанные в [1, 2]:

1.  быстрая сортировка,

2.  один из алгоритмов по выбору:

§  сортировка методом Шелла,

§  пирамидальная сортировка.

Входные данные

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

Выходные данные