2015-01-30
481
/*============СОРТИРОВКА ВКЛЮЧЕНИЕМ=============*/
/* функция сортировки включением */
void Sis(int A[],int nn)
{ int i,j,k;
for (j=1; j<nn; j++)
{ k = A[j];
i = j -1;
while (k < A[i] && i >= 0)
{ A[i+1] = A[i];
i -= 1; }
A[i+1] = k;
}
}
/*==============СОРТИРОВКА ВЫБОРОМ===============*/
/* функция сортировки выбором */
void StrSel(int A[],int nn)
{ int i,j,x,k;
for (i=0; i<nn-1; i++)
{ x = A[i]; k = i;
for (j=i+1; j<nn; j++)
if (A[j] < x)
{ k = j; x = A[k]; }
A[k] = A[i]; A[i] = x;
}
/*============СОРТИРОВКА ОБМЕНОМ=============*/
/* функция сортировки обменом */
void BblSort(int A[],int nn)
{ int i,j,k,p;
for (i=0; i<nn-1; i++)
{ p = 0;
for (j=nn-1; j>i; j--)
if (A[j] <A[j-1])
{ k = A[j]; A[j] = A[j-1]; A[j-1] = k; p = 1;}
/* Если перестановок не было, то сортировка выполнена */
if (p == 0)
break;
}
}
/*============СОРТИРОВКА МЕТОДОМ ШЕЛЛА=============*/
/* функция сортировки методом Шелла */
void ShellSort(int a [], int n){
int i,j,k,hh,t,s;
int h [1000];
t = round(ln(n)/ln(3))-1;
if (t < 1){
t = 1;
};
h[t] = 1;
for (k=t-1; k >= 1; k--) {
h[k-1] = 3*h[k]+1;
}
for (s=t-1;s>=0;s--){
hh = h[s];
for (j = hh;j<=n;j++){
i = j-hh;
k = a[j];
while ((k <= a[i])&&(i >= 0)){
a[i+hh] = a[i];
i = i-hh;
};
a[i+hh] = k;
} }}
/*============СОРТИРОВКА МЕТОДОМ ХОАРА=============*/
void QSort(int a [], int L, int R){
int x = a[L], i = L, j = R, t; // в качестве разделителя выбираем первый элемент
while (i<=j){
while (a[i]<x)
i++;
while (a[j]>x)
j--;
if (i<=j){
t = a[i];
a[i] = a[j];
a[j] = t;
i++;
j--;
} }
if (L<j)
QSort(a,L,j);
if (i<R)
QSort(a,i,R);
}
/* функция сортировки методом Хоара */
void HoarSort(int a[], int n){
QSort(a,1,n);
}
/*============ПИРАМИДАЛЬНАЯ СОРТИРОВКА=============*/
/* пирамидальнаяфункция сортировки */
void HeapSort(int A[],int nn)
{ int L,R,x,i;
L = nn/2; R = nn-1;
/* Построение пирамиды из исходного массива */
while (L>0)
{ L = L - 1;
Sift(A,L,R);
}
/* Сортировка: пирамида => отсортированный массив */
while (R>0)
{ x = A[0]; A[0] = A[R]; A[R] = x;
R--;
Sift(A,L,R);
} }
/* ============================================ */
void Sift(int A[],int L,int R)
{ int i,j,x,k;
i = L;
j = 2*L+1;
x = A[L];
if ((j<R) && (A[j]<A[j+1]))
j++;
while ((j<=R) && (x<A[j]))
{ k=A[i]; A[i] = A[j]; A[j]=k;
i = j;
j = 2*j+1;
if ((j<R) && (A[j]<A[j+1]))
j++;
} }
/* ***************************************************** */
К о н т р о ль н ы е в о п р о с ы
1. Что такое временная сложность алгоритма?
2. Почему функцию временной сложности нельзя использовать для оценки алгоритма?
3. Что такое порядок функции? Как определяется порядок функции, заданной многочленом?
4. Как можно определить порядок функции временной сложности алгоритма?
5. Что называется сортировкой?
6. В каком случае метод сортировки называется устойчивым?
7. Как выполняется сортировка включением?
8. Зависит ли время сортировки включением от упорядоченности массива?
9. Зависит ли порядок функции временной сложности сортировки включением от упорядоченности массива?
10. Выполните анализ сортировки включением.
11. Реализуйте алгоритм сортировки включением на языке программирования.
12. Как выполняется сортировка выбором?
13. Зависит ли время сортировки выбором от упорядоченности массива?
14. Зависит ли порядок функции временной сложности сортировки выбором от упорядоченности массива?
15. Выполните анализ сортировки выбором.
16. Реализуйте алгоритм сортировки выбором на языке программирования.
17. Как выполняется сортировка обменом?
18. Зависит ли время сортировки обменом от упорядоченности массива?
19. Зависит ли порядок функции временной сложности сортировки обменом от упорядоченности массива?
20. Выполните анализ сортировки обменом.
21. Реализуйте алгоритм сортировки обменом на языке программирования.
22. Как можно улучшить сортировку обменом?
23. Почему сортировка Шелла быстрее сортировки вставками?
24. Выполните итеративную реализацию сортировки Хоара.
25. Чем пирамидальная сортировка отличается от сортировки выбором?
Л а б о р а т о р н а я р а б о т а № 4
