Сортировка одномерных массивов

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

B[1] ≤ B[2] ≤ … ≤ B[n],

и в порядке убывания, если

B[1] ≥ B[2] ≥ … ≥ B[n].

В повседневной жизни процесс сортировки «массивов» используется очень часто. Например, список в журнале студенческой группы (сортиров­ка по алфавиту фамилий, а при необходимости и имен, и отчеств) или ито­говая таблица чемпионата страны по футболу (сортировка по набранным командой очкам).

Рассмотрим некоторые из алгоритмов сортировки. При этом будем рассматривать сортировку по возрастанию. Ключевым отличием сорти­ровки по убыванию будет то, что в проверке знак «больше» необходимо будет заменить на знак «меньше».

9.1.2.1 Сортировка методом «пузырька». Сортировка методом «пу­зырька» основана на выполнении в цикле операций сравнения и при необхо­димости обмена соседних элементов. Рассмотрим этот метод более подробно.

Сравним первый элемент массива со вторым, если первый окажется больше второго, то поменяем их местами. Затем сравним второй с третьим, если второй окажется больше третьего, то также поменяем их местами. Продолжаем сравнивать попарно соседние элементы до сравнения (n–1)-го и n-го элементов. В результате этих действий самый большой элемент ста­нет на последнее (n-е) место. Теперь повторим данный алгоритм сначала, с 1-го до (n–1)-го элемента. Последний n-й элемент не рассматривается, т. к. он уже занял свое место. После проведения данной операции самый большой элемент оставшейся части массива станет на свое (n–1)-е место. Так, уменьшая количество проверяемых элементов, повторяем до тех пор, пока не проверим последние (точнее первые) два элемента.

Пошаговый пример выполнения данного алгоритма сортировки представлен в таблице 9.1.

Таблица 9.1 – Сортировка методом «пузырька»

Номер элемента
Исходный массив
Первый просмотр
Второй просмотр
Третий просмотр
Четвертый просмотр

Ниже приведен текст фрагмента программы, предназначенный для сортировки одномерного массива B[n] методом «пузырька».

for (j= n-1; j>0; j--)

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

if (B[i]>B[i+1]) {t=B[i]; B[i]=B[i+1]; B[i+1]=t;}

9.1.2.2 Сортировка методом перестановки. Сортировка методом перестановки основана на поиске наибольшего элемента среди нескольких и последующего его перемещения на последнюю позицию. Рассмотрим этот метод более подробно.

Найдем в массиве самый большой элемент (при этом запоминаем и номер позиции, где стоит этот элемент) и поменяем его с последним n-м. Самый большой элемент массива станет на свое место. Найдем среди (n–1) первых элементов наибольший и поменяем его местами с (n–1)-м. Повто­ряем эти действия, уменьшая количество проверяемых элементов на еди­ницу до тех пор, пока количество рассматриваемых элементов не станет равным одному.

Пошаговый пример выполнения данного алгоритма сортировки представлен в таблице 9.2.

Таблица 9.2 – Сортировка методом перестановки

Номер элемента
Исходный массив
Первый просмотр
Второй просмотр
Третий просмотр
Четвертый просмотр

Ниже приведен текст фрагмента программы, предназначенный для сортировки одномерного массива B[n] методом перестановки.

for (j= n-1; j>0; j--)

{ max= B[0]; imax= 0;

for (i= 1; i<j+1; i++)

if (B[i]>max) {max= B[i]; imax= i;} t= B[imax]; B[imax]= B[j]; B[j]= t; }

9.1.2.3 Сортировка методом вставки. Сортировка методом вставки основана на поочередном переносе элементов исходного массива в другой, при этом в новый массив элементы добавляются уже в упорядоченном ви­де. Рассмотрим этот метод более подробно.

Данный метод удобнее рассмотреть на наглядном примере. Предпо­ложим, что вы перевозите многотомное собрание сочинений А. Дюма своей библиотеки на новую квартиру. Необходимо расставить хаотично упакованные в коробку (массив В) книги на книжную полку (массив С)

по порядку. Первую взятую книгу из коробки (первый элемент массива В) помещаем на полку в крайнюю левую позицию (на первую позицию в мас­сив С). Для второй, взятой из коробки, книги делаем проверку, учитывая номер тома (значение элемента массива). Если номер тома взятой книги больше, чем номер тома выставленной на полку книги, то вставляем новую книгу справа от уже стоящей, иначе – слева. Повторяем подобные опера­ции несколько раз. Взяв из коробки k-ю книгу, сравниваем ее (по номеру тома) с уже стоящими на полке справа налево. Если стоящая на полке крайняя правая книга больше по номеру тома, чем взятая из коробки, то сдвигаем книгу на полке правее и проверяем следующую книгу. Найдя по­зицию расположения взятой из коробки книги среди уже стоящих, встав­ляем ее на книжную полку. Повторяем данные операции, пока все книги не займут свои позиции на книжной полке.

Пошаговый пример выполнения данного алгоритма сортировки представлен в таблице 9.3.

Таблица 9.3 – Сортировка методом вставки

				Первый шаг
В
С
				Второй шаг
В
С
				Третий шаг
В
С
				Четвертый шаг
В
С
				Пятый шаг
В
С
				Шестой шаг
В
С
				и т.д.

Ниже приведен текст фрагмента программы, предназначенный для сортировки одномерного массива B[n] методом вставки.

C[0]= B[0];

for (i= 1; i< n; i++) { j= i;

while (j>=0 && B[i]<C[j-1]) { C[j]= C[j-1]; j--;} C[j]= B[i];}

9.1.2.4 Сортировка методом Шелла. Сортировка Шелла была назва­на в честь еѐ изобретателя – Дональда Шелла, который опубликовал этот алгоритм в 1959 году.

Сортировка Шелла (англ. Shell sort) – алгоритм сортировки, яв­ляющийся усовершенствованным вариантом сортировки методом «пу­зырька». Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определѐнном расстоянии друг от друга. Иными словами – это сортировка методом «пузырька» с предварительными «гру­быми» проходами.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d. После выполнения интервал уменьшается по формуле d(k) = [d(k + 1) – 1] / 2. После этого процедура повторяется для уменьшенных значений d, а за­вершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть обычной сортировкой методом «пузырька»).

Эффективность сортировки Шелла в определѐнных случаях обеспе­чивается тем, что элементы «быстрее» встают на свои места.

Ниже приведен текст фрагмента программы, предназначенный для сортировки одномерного массива B[n] методом Шелла.

d=n-1; while (d>0) {

for (j=1; j<n; j+=d)

{ for (i=0; i<n-j; i++) { if (B[i]>B[i+1])

{ t=B[i]; B[i]=B[i+1]; B[i+1]=t; } } } d=(d-1)*0.5; }

Дата добавления: 2015-07-13