Сортировка массива.

Теперь пускай нам необходимо отсортировать массив, например, по возрастанию. То есть в начале стоит самый маленький элемент, а в конце самый большой. Будем рассматривать самый простой алгоритм сортировки – сортировка обменом. Другое название этой сортировки - сортировка «пузырьком».

Рассмотрим, как говорит мой преподаватель по курсу «методы оптимизации», философию метода.

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

Давайте рассмотрим иллюстрирующую этот шаг алгоритма картинку.

Рис. 3. Пример первого шага сортировки одномерного массива методом обмена.

Как видите, самый тяжелый элемент – тонет, то есть опускается на самый низ. А более легкие элементы, как бы всплывают, как пузырьки в воде. Отсюда и название алгоритма. После одного прохода алгоритма, на последнее место. Получается, после одного шага алгоритма один элемент уже точно занимает свое место, и при следующем проходе, нам нет необходимости сравнивать предпоследний и последний элемент, так как последний элемент уже на своем месте и ничего менять не надо, так зачем лишнее действие?

Повторяя описанную процедуру n-1 раз (здесь n – размерность массива) получим полностью отсортированный массив.

На следующем рисунке проиллюстрирована работа алгоритма, на примере небольшого массива.

Рис. 4. Иллюстрация сортировки массива методом "пузырька".

Приведем код реализации алгоритма сортировки пузырьком, на языке Си. Обратите внимание на поясняющие комментарии.

Листинг 12.2

#include <stdio.h>

int main(){

int n=6, // размерность массива

arr[6]={5,14,7,4,11,2}; // массив для сортировки

for (int i=n-1;i>0;i--)

for (int j=0;j<i;j++)

if(arr[j]>arr[j+1]){ // если порядок нарушен

//меняем j и j+1 элементы массива местами

int temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=tmp;

}

//выводим массив на экран

for (int i=0;i<n; i++)

printf("%d\n", arr[i]);

return(0);

}

Помните, мы говорили, что на каждом шаге нам нужно сокращать длину основного цикла? Т.е. сначала проходим все элементы до n-1, на следующем шаге до n-2 и т.д. В приведенном выше алгоритме это реализовано внешним циклом. Обратите внимание, что мы впервые используем направление цикла «сверху вниз». Т.е. движемся не от единицы к n, а наоборот, от n-1 к 1.