4. Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Алгоритм состоит в том, что исходная последовательность разделяется на ряд групп, каждая из которых упорядочивается методом простой вставки. В процессе упорядочивания размеры групп возрастают до тех пор, пока все элементы не войдут в упорядоченную группу. Группой называется подмножество элементов последовательности, номера которых образуют арифметическую прогрессию с разностью d (d называется шагом группы).

void sort_Shell(int *mas,int n)

{

int i,j; //"бегунки"

int temp; //вспомогательная переменна

int h = n/2;

while(h>0)// проверяем, если h>0 то входим в тело цикла

{

for(i=0;i mas[j+h])

{

temp = mas[j];

mas[j] = mas[j+h];

mas[j+h] = temp; //перестановка элементов

j=j-h;

}

else

j=-1;// перестановки не было - "бегунок" уменьшим на 1

}

}

h=h/2;

}

}

5. Внутренняя сортировка данных методом «пузырька». Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

Наихудший случай:

Число сравнений в теле цикла равно: (N-1)*N/2.

Число сравнений в заголовках циклов равно: (N-1)*N/2.

Суммарное число сравнений равно: (N-1)*N.

Число присваиваний в заголовках циклов равно: (N-1)*N/2.

Число обменов равно: (N-1)*N/2, что в N/2 раз больше, чем в сортировке выбором.

void bubbleSort(int* arr, int size)

{

int tmp, i, j;

for(i = 0; i < size - 1; ++i) // i - номер прохода

{

for(j = 0; j < size - 1; ++j) // внутренний цикл прохода

{

if (arr[j + 1] < arr[j])

{

tmp = arr[j + 1];

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

arr[j] = tmp;

}

}

}

}

6. Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Идея:

- выбрать элемент, называемый опорным.

- сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.

- повторить рекурсивно для «меньших» и «больших».

Количество обменов в худшем случае: n^2

Количество шагов деления(глубина рекурсии): ~ log n

void qSort(int[] A, int low, int high) {

int i = low;

int j = high;

int x = A[(low+high)/2];

do {

while(A[i] < x) ++i;

while(A[j] > x) --j;

if(i int temp = A[i];

A[i] = A[j];

A[j] = temp;

i++; j--;

}

} while(i

if(low < j) qSort(A, low, j);

if(i < high) qSort(A, i, high);

}