Ранжирование числовых массивов

Числовые массивы ранжируются по направлениям (рис. 9.10).

Ранжирование числовых массивов - student2.ru

Рис. 9.10. Классификация направлений ранжирования

В математике разработаны различные методы сортировки числовых массивов. Основной (универсальный) метод формулируется следующим образом:

· определить в рассматриваемом массиве элемент с максимальным (минимальным) значением (кодом) и запомнить его индекс;

· поменять местами содержимое первого элемента и элемента с максимальным (минимальным) значением – отсортировать экстремальный элемент рассматриваемого массива;

· сформировать новый (текущий) массив уменьшением исходного (предыдущего) на единицу (без уже отсортированного первого элемента);

· повторять предыдущие пункты до тех пор, пока количество элементов в текущем массиве не станет меньше двух.

Графическая интерпретация метода представлена на рис. 9.11.

Ранжирование числовых массивов - student2.ru Исходный (рассматриваемый) массив X(n) Ранжирование числовых массивов - student2.ru
x1 x2 x3 . . . xj . . . xmax1   xn-1 xn
Ранжирование числовых массивов - student2.ru
Формируемый массив X(n) Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Текущий массив Х(n-1)
xmax1 x2 x3 . . . xj . . .   xmax2 xn-1 xn
Ранжирование числовых массивов - student2.ru
Формируемый массив X(n) Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Текущий массив Х(n-2)
xmax1 xmax2 x3 . . . xmax . . .     xn-1 xn
Ранжирование числовых массивов - student2.ru
Формируемый массив X(n) Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Текущий Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru массив
xmax1 xmax2 xmax3 . . . xmaxi . . .     xmax n-1 xmax n
Ранжирование числовых массивов - student2.ru

Рис. 9.11. Схема основного метода ранжирования

Частный случай – сортировка методом «всплывающего пузырька».

Методика – последовательное сравнение двух смежных элементов массива, начиная с последних (n и n-1). Если n-й элемент больше (при поиске максимума) или меньше (при поиске минимума) предыдущего – они меняются местами. Результат – больший (меньший) «всплыл» на элемент вверх.

Затем значение n уменьшается на единицу. Конечным становится n-1 элемент и сравнение двух последних (n-1 и n-2) повторяется по предыдущим правилам.

Указанные компоненты методики повторяются до полного «всплытия» максимального (минимального) значения в первый элемент массива. После чего исходный массив уменьшается на единицу, лишаясь первого (отсортированного) элемента. И весь процесс повторяется n-1 раз.

В конечном счете, осуществляется ранжирование по убыванию (возрастанию) всех элементов рассматриваемого массива.

Графическая интерпретация представлена на рис. 9.12.

Ранжирование числовых массивов - student2.ru   Ранжирование числовых массивов - student2.ru и М с Ранжирование числовых массивов - student2.ru а х с о Ранжирование числовых массивов - student2.ru с д и н Ранжирование числовых массивов - student2.ru в ы й   xmax1 Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru     Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru т е к у щ и й   xmax1 Ранжирование числовых массивов - student2.ru ф о р м и р Ранжирование числовых массивов - student2.ru у е м Ранжирование числовых массивов - student2.ru Ранжирование числовых массивов - student2.ru ы й xmax1 Ранжирование числовых массивов - student2.ru c о з д а н н ы й
Ранжирование числовых массивов - student2.ru x2 xmax2 xmax2
х3 х3 xmax3
    xmax4
xi xi xmax i
Ранжирование числовых массивов - student2.ru xmax1 xmax2
    xmax n-3
    xmax n-2
Ранжирование числовых массивов - student2.ru xn-1 xn-1 Ранжирование числовых массивов - student2.ru xn-1
xn xn xn

Рис. 9.12. Схема метода «всплывающего пузырька»

Предмашинная подготовка вычислительных процессов выполнения сортировок типовых совокупностей данных представлена ниже.

Ранжирование по убыванию основным методом

Рассмотрим ранжирование по убыванию на конкретной задаче (9.4) о числовом одномерном массиве Х.

Постановка задачи

Дан одномерный целочисленный массив Х. Максимально возможное количество элементов в нем не более 30.

Диапазон представления положительных численных значений элементов от 5 до 90.

Требуется отранжировать исходный массив по убыванию.

Наши рекомендации