1.4.8. Сортировка зна­чений одномерного массива по возрастанию (убыванию) методом попарного сравнения

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

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

Пример 10.9

Метод попарного сравнения. Сущность метода состоит в том, что со­седние записи (числа) сравниваются попарно и меняются местами, если порядок их расположения неправильный (с точки зрения задачи сортиров­ки). Сравнение начинается с записей 1 и 2; затем запись, оказавшая­ся на втором месте, сравнивается с записью 3 и т.д.

Первый цикл сравнений и перестановок дает частичное упорядочение массива. Второй цикл проводится аналогично. Сортировка заканчивается, когда за очередной цикл не будет произведено ни одной перестановки.

Данный метод не требует дополнительных затрат памяти ЭВМ, так как массив не переписывается. Затраты машинного времени сравнительно большие. Недостатком метода является то обстоятельство, что исходный массив не сохраняется (перестановка внутри массива).

Блок-схема алгоритма попарного сравнения для примера 10.7 приведена на рис. 10.4. Здесь переменная X используется для контроля за наличи­ем перестановок элементов массива а.

Программа на языке С++ может иметь следующий вид:

/*Сортировка методом попарного сравнения */

#include <stdio.h>

#include <conio.h>

#include <math.h>

#include <iostream.h>

#define m 19

int main()

{

int k, i,x;

float a[m],b, c;

// Ввод массива a

for (k=0; k<=m; k++)

{

cout <<"Введите " << k << "-ый элемент массива a: ";

cin >> a[k];

}

// Сортировка массива a по возрастанию

do

{

i = 0;x =0;

for (k=1; k<=m; k++)

{b = a[i]; c = a[k];

if (c < b) {a[i] = c; a[k] = b; x = x + 1;}

i= i + 1;

}

}

while (x>0);

// Вывод отсортированного массива a

for (k=0; k<=m; k++)

{

cout <<"k = " << k << " a[k] = " << a[k] << endl;

}

cout << "Нажмите любую клавишу..." ;

getch();

return 0;

}

Рис. 10.4. Блок-схема алгоритма сортировки методом попарного сравнения для примера 10.7

1.4.9. Сортировка зна­чений одномерного массива по возрастанию (убыванию) методом нахождения минимума (максимума)

Пример 10.10

Метод нахождения минимума (максимума). Идея его состоит в следую­щем. Пусть необходимо упорядочить массив по возрастанию значения признака (метод нахождения минимума). Для этого в исходном массиве отыскивается запись с минимальным значением признака и помещается на первое место в упорядоченном массиве. В оставшейся части массива сно­ва отыскивается запись с минимальным значением признака и помещается на второе место. Процесс поиска минимумов повторяется до полного упо­рядочения массива, т.е. m-1 раз (при наличии m элементов в масси­ве). Рассматриваемый метод по свойствам равноценен предшествующему. При сортировке в порядке убывания значения признака процедура оста­ется той же, но отыскивается запись с максимальным значением призна­ка. Блок-схема рассматриваемого алгоритма сортировки представлена на рис. 8.5. В ней использованы следующие обозначения: m - количество элементов в массиве; k - индекс максимального элемента; a_k - элемент, находящийся в k-й позиции; l - количество элементов в упорядоченной части; b - вспомогательная переменная.

Действия, которые должны быть выполнены ЭВМ при реализации этого алгоритма состоят в следующем:

1. Ввести значение m и значения элементов a_i (блоки 2 - 6).

2. Положить длину l в упорядоченной части массива равной 1 (блок 7).

3. Найти индекс k минимального элемента в неупорядоченной части массива (блоки 8 - 13). Здесь буквой j обозначен индекс очередно­го анализируемого элемента. Вначале в качестве минимального прини­мается l-й элемент (k = l), и все остальные элементы, начиная с l+1 (j = l + 1) сравниваются с l-ым. Как только найдется элемент а_j, значение которого меньше значения a_k (блок10), фиксируется его индекс (k = j , блок 11) и дальнейшие сравнения ведутся уже с этим элементом, и т.д. Таким обрезом, после того как завершится просмотр заданного число элементов (j превышает m, блок 13), k будет иметь значение индекса минимального элемента.

Рис. 10.5. Блок-схема алгоритма сортировки методом