Функция сортировки прямым выбором

94 67

ЕЯ94

061 142

И 67

Начальные ключи

Сортировка с помощью прямого выбора

Функция сортировки с помощью метода прямого включения

Сортировка с помощью прямого включения

Элементы массива условно разделяются на готовую последовательность а_х,а₂,..., а_{.\ и входную последовательность а_и а₂,..., а_пЛ [1, 3, 9, 10, 13]. На каждом шаге z-й элемент помещается на подходящее место в готовую последовательность (рис. 3.2).

Начальные ключи i = 1 i = 2 i = 3 i=4 i = 5 i = 6 i = 7
44^12 42 94 18 06 67
♦
44| 14294 18 06 67
t
12|44 55^94 18 06 67
t
12|42|44 55g]18 06 67
T
12 42 44 55|94[Ц0667
^^^F
^f
12|ia|4244 55 94ГЯ67
г---------------- "---------- ~
0б|12 18 42 44 55 94 ГЯ
^^
06 12 18 42 44 55|67|94

Рис. З.2. Пример сортировки Алгоритм сортировки

for(i=l; i<n;	i++)
{
x=a [ i ];
включение х	на соответствующее место
среди a0,..	• i Si
}

В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать х, т. е. х сравнивается с очередным элементом о,-, а затем либо х вставляется на свободное место, либо щ сдвигается (передаётся) вправо и процесс «уходит» влево. Процесс просеивания закончится при выполнении одного из двух следующих условий:

1. Найден элемент о,- с ключом, меньшим, чем ключ у х.

2. Достигнут левый конец готовой последовательности.

void insertionSort(int numbers[], int array_size)

{

int i, j, index;

for (i=l; i < array_size; i++)

{

index = numbers[i];

j = i;

while ((j > 0) && (numbers[j-1] > index))

{

numbers[j] = numbers[j-1];

j = j - i; }

numbers[j] = index; } }

Анализ алгоритма. Число сравнений ключей С_г при г-м просеивании составляет самое большое /-1, самое меньшее 1. Если предположить, что все перестановки из п ключей равновероятны, то среднее число сравнений — г/2. Число пересылок M_t равно С_г+2. Поэтому общее число сравнений и пересылок таковы [3]:

C_cp = {n² + n- 2)1 A; M_cp = (n²+9n-\0)/4; C_max = (n² + n- 4)/4; M_min = (n² + Ъп- 4)/2.

Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки — когда элементы первоначально расположены в обратном порядке.

Резюме: сортировка методом прямого включения — не очень подходящий метод для ЭВМ, так как включение элемента с последующим сдвигом на одну позицию целой группы элементов неэффективно.

Метод сортировки основан на следующих правилах [1, 3, 9, 10, 13]:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом а₀.

3. Затем эти операции повторяются с оставшимися п-\ элементами, п-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.

На рис. 3.3 приведен процесс сортировки этим методом.

и

94 ЕЯ 44

Ш42"Э41Я

т

42 Ш 55 ЕЛ 67

441*194

I I

Рис. 3.3. Пример сортировки Алгоритм формулируется следующим образом

for(i=0; i<n-l; i++) {

присвоить к индекс наименьшего элемента из a[i]..а[п-1]; поменять местами a[i] и а[к];

}

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

void selectionSort(int numbers[], int array_size)

{

int i, j;

int min, temp;

for(i = 0; i < array_size-l; i++)

{

min = i;

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

{

if (numbers[j] < numbers[min]) min = j; }

temp = numbers[i]; numbers[i] = numbers[min]; numbers[min] = temp; } }

Анализ алгоритма [З]. Число сравнений ключей С не зависит от порядка ключей:

С=У(2п²-2п). Число перестановок минимально

M_min = 3(n-l) в случае изначально упорядоченных ключей и максимально

М_тах = п²1А + Ъ(п-\\ если первоначально ключи располагаются в обратном порядке. Среднее число пересылок

Мер ~ «(1П П + g),

где g = 0,577216... — константа Эйлера.

Резюме: как правило, алгоритм с прямым выбором предпочтительнее алгоритму прямого включения; однако, если ключи в начале упорядочены или почти упорядочены, прямое включение будет оставаться несколько более быстрым.

Дата добавления: 2014-11-29