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

94 67

ЕЯ94

061 142

И 67

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

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

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

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

Элементы массива условно разделяются на готовую последовательность ах2, ..., а{.\ и входную последовательность аи а2, ..., апЛ [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. Число пересылок Mt равно Сг+2. Поэтому общее число сравнений и пересылок таковы [3]:

Ccp = {n2 + n- 2)1 A; Mcp = (n2+9n-\0)/4; Cmax = (n2 + n- 4)/4; Mmin = (n2 + Ъп- 4)/2.

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

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

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

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

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

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-2п). Число перестановок минимально

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

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

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

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

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