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

Нужно выдать на экран элементы исходного массива, а затем с новой строки выдать элементы этого массива после применения к нему алгоритма сортировки

Методы

Ниже будут использоваться обозначения, введенные в описании лабораторной работы № 7.

Метод 1. Сортировка включениями с убывающими приращениями

(метод Шелла)

процедура Вставка(b, h)

 //  b — номер первого элемента последовательности

 //  h – величина шага

начало процедуры                 

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

  // части массива.

  i := b + h;

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

     x:= A[i];                 

     j := i – h;

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

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

     // x, сдвинуть на величину шага h вправо,

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

        j := j – h;            

     конец пока

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

     A[j+h] := x;             

     i := i + h;                    

  конец пока

конец процедуры

Основная программа:

// Выбор начального шага:

h := 1;

пока h < N/3 выполнять  

   h := 3*h + 1;

конец пока

// Сортировка:

пока h ³ 1 выполнять

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

      Вставка (i, h);

      h := (h – 1) / 3;

   конец цикла

конец пока

Метод 2. Пирамидальная сортировка

В данном методе используется следующая процедура:

процедура Просеивание (i, n)    

// i – номер элемента, который нужно просеять

          // n – номер последнего элемента массива

начало процедуры

   если 2*i <= n

   то начало  

        r := 2*i;                    

      если (r+1 £ n) и (A[r] < A[r+1])

то r := r + 1;                    

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

          // где он удовлетворяет свойству пирамиды:

          // A[i] ³ max(A[2*i], A[2*i + 1])

если A[i] < A[r]             

         то начало

               Обмен (i, r);                  

               Просеивание (r, n);

            конец

      конец

конец процедуры

Основная программа:

Шаг 1. Построение пирамиды:

i := N / 2;

пока i ³ 1 выполнять

{ Просеивание (i, N);

  i := i – 1;}

Шаг 2. Сортировка на пирамиде:

i := N;

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

   Обмен (1, i);

   i := i – 1;

   Просеивание (1, i);

конец пока

конец основной программы.

Метод 3. Быстраясортировка.

процедура Qsort ( left, right) 

// left— левая граница сортируемой области

// right– ее правая граница.

начало процедуры

   i := left;

   j := right;

   x := A[(i + j)/2];     

   // x — пилотируемый элемент, относительно которого

   //сортируются все остальные элементы массива:

   // в левую часть массива перемещаются все элементы,

   // меньшие либо равные x, а в правую — большие

   // либо равные x;

   пока (i £ j) выполнять                   

      пока A[i] < x выполнять

i := i + 1;

      конец пока

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

         j := j – 1;

      конец пока

      если i £ j

      то начало

            Обмен (i, j);         

            i := i + 1;         

            j := j – 1;         

         конец

   конец пока

   // Затем отдельно отсортировать методом быстрой

   // сортировки левую и правую части перестроенного

   // массива:

   если j > left то Qsort(left, j);

   если i < right то Qsort(i, right)

   конец процедуры

Основная программа:

Qsort(1, n);

конец основной программы

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

Лабораторная работа № 9.  Сортировка файлов

Задание

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

Использовать один из алгоритмов сортировки файлов слиянием, описанный в [1, 2].

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

На вход программе подаются имена входного и выходного файлов. Входной файл должен содержать последовательность целых чисел.

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

Нужно вывести в выходной файл элементы входного файла, отсортированные по возрастанию.

Метод. Двухпутевое сбалансированное слияние

процедура Слить2в1

( F1, F2, // – входные файлы

  F       // – выходной файл