Алгоритмы сортировки массивов

упорядоченность пары элементов;
перестановку, меняющую местами пару элементов;
собственно сортирующий алгоритм, который

осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

сортировка Хоара, сортировка слиянием
Внешняя сортировка
Примеры: сортировки слиянием (простое слияние и

естественное слияние); улучшенные сортировки (многофазная сортировка и каскадная сортировка).

Флойдом в 1964 году.

сортировка выбором

в худшем, в среднем и в лучшем случае (то

есть гарантированно) за Θ(n log n) операций при сортировке n элементов.
Количество применяемой служебной памяти не зависит от размера массива O(1)

T1(n)=O(nxlog n).
Построение пирамиды занимает T2(n)=O(n) операций, что реальное время выполнения

функции построения зависит от высоты уже созданной части пирамиды.
время сортировки (с учетом построения пирамиды) : T(n)=T1(n)+T2(n)=O(n)+O(nxlog n)=O(nxlog n).

выполняются неравенства xk > x2k, xk > xi (или xk

< x2k, xk < x2k+1 ). Элементы x2i и x2i+1 называются потомками элемента xi.

Массив чисел 12, 10, 7, 5, 8, 7, 3 является пирамидой

(построение пирамиды).

Пусть дан массив x[1],x[2],...,x[n].
Шаг 1. Устанавливаем k=n/2

i=k,k-1,...,1. Если неравенства xi > x2i, xi > x2i+1 не

выполняются, то повторяем перестановки xi с наибольшим из потомков. Перестановки завершаются при выполнении неравенств xi > x2i, xi > x2i+1.

Алгоритм сортировки пирамиды.
Рассмотрим массив размерности n, который представляет пирамиду x[1],x[2],...,x[n].
Шаг 1. Переставляем элементы x[1] и x[n].

из дальнейшего рассмотрения исключается элемент x[n].
Шаг 3. Рассматриваем массив x[1],x[2],...,x[n-1]

x[i]

> x[2i]
x[i] > x[2i+1]

пока не получим n=1. произвольный массив можно преобразовать в пирамиду

Sort_Piramid(k-1,x);}

//Построение пирамиды
void Build_Pyramid (int k, int r, int *x){
Sifting(k,r,x);

if (k > 0)
Build_Pyramid(k-1,r,x);}

//Сортировка пирамиды
void Sort_Piramid (int k, int *x){
Exchange (0,k,x);
Sifting(0,k-1,x);
if (k > 1)
Sort_Piramid(k-1,x);}

//"Просеивание" элементов
void Sifting (int left, int right, int *x){
int q, p, h;
q=2*left+1;
p=q+1;
if (q <= right){
if (p <= right && x[p] > x[q])
q = p;
if (x[left] < x[q]){
Exchange (left, q, x);
Sifting(q, right, x);
} }}
//процедура обмена двух элементов
void Exchange (int i, int j, int *x){
int tmp;
tmp = x[i];
x[i] = x[j];
x[j] = tmp;}

T1(n)=O(nxlog n).
Построение пирамиды занимает T2(n)=O(n) операций, что реальное время выполнения

функции построения зависит от высоты уже созданной части пирамиды.
время сортировки (с учетом построения пирамиды) : T(n)=T1(n)+T2(n)=O(n)+O(nxlog n)=O(nxlog n).

время O(n1.25)
для худшего случая O(n1.5)

пар (xi,xn/2+i) для 1

четырех элементов (xi,xn/4+i,xn/2+i,x3n/4+i) для 1

Шаг 3

Упорядочиваются элементы уже в n/4 группах из восьми элементов и т.д.

неизвестна последовательность hi,hi-1,hi-2,...,h1


hi+1=3hi+1, а h1=1.
Начинается процесс с hm, что hm>[n/9].
Иногда значение h вычисляют проще: hi+1=hi/2
h1=1
hm=n/2

h, i, j;
for (h = n/2 ; h >

0 ; h = h/2)
for (i = 0 ; i < n-h ; i++)
for (j = i ; j >= 0 ; j = j - h)
if (x[j] > x[j+h])
Exchange (j, j+h, x);
else j = 0;
}
//процедура обмена двух элементов
void Exchange (int i, int j, int *x){
int tmp;
tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}

году
Цитата: Преждевременная оптимизация — корень всех зол.

Худший случай O(n2)
В

среднем случае T(n) = O(1.4n log n) При оптимальном выборе ведущих элементов O(n log n)

(0, k-1, x);
}

void Quick_Sort(int left, int right, int *x)
{ int

i, j, m, h;
i = left;
j = right;
m = x[(i+j+1)/2];
do {
while (x[i] < m) i++;
while (x[j] > m) j--;
if (i <= j) {
Exchange(i,j,x);
i++;
j--;
} }
while(i <= j);
if (left < j)
Quick_Sort (left, j, x);
if (i < right)
Quick_Sort (i, right, x);
}

//процедура обмена двух элементов
void Exchange (int i, int j, int *x){
int tmp;
tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}

Нейманом в 1945 году

i, j, k, t, s, Fin1, Fin2;
int* tmp =

new int[n];
k = 1;
while (k < n){
t = 0;
s = 0;
while (t+k < n){
Fin1 = t+k;
Fin2 = (t+2*k < n ? t+2*k : n);
i = t;
j = Fin1;
for ( ; i < Fin1 && j < Fin2 ; s++){
if (x[i] < x[j]) {
tmp[s] = x[i];
i++;
}
else {
tmp[s] = x[j];
j++;
} }

for ( ; i < Fin1; i++, s++)
tmp[s] = x[i];
for ( ; j < Fin2; j++, s++)
tmp[s] = x[j];
t = Fin2;
}
k *= 2;
for (s = 0; s < t; s++)
x[s] = tmp[s];
}
delete(tmp);
}

на которые распределяются серии.

прочитаны и столько же раз записаны.

int a1, a2, k, i, j, kol, tmp;
FILE *f,

*f1, *f2;
kol = 0;
if ( (f = fopen(name,"r")) == NULL )
printf("\nИсходный файл не может быть прочитан...");
else {
while ( !feof(f) ) {
fscanf(f,"%d",&a1);
kol++;
}
fclose(f);
}
k = 1;
while ( k < kol ){
f = fopen(name,"r");
f1 = fopen("smsort_1","w");
f2 = fopen("smsort_2","w");
if ( !feof(f) ) fscanf(f,"%d",&a1);
while ( !feof(f) ){
for ( i = 0; i < k && !feof(f) ; i++ ){
fprintf(f1,"%d ",a1);
fscanf(f,"%d",&a1);
}
for ( j = 0; j < k && !feof(f) ; j++ ){
fprintf(f2,"%d ",a1);
fscanf(f,"%d",&a1);
}
}
fclose(f2);
fclose(f1);
fclose(f);

f = fopen(name,"w");
f1 = fopen("smsort_1","r");
f2 = fopen("smsort_2","r");
if ( !feof(f1) ) fscanf(f1,"%d",&a1);
if ( !feof(f2) ) fscanf(f2,"%d",&a2);
while ( !feof(f1) && !feof(f2) ){
i = 0;
j = 0;
while ( i < k && j < k && !feof(f1) && !feof(f2) ) {
if ( a1 < a2 ) {
fprintf(f,"%d ",a1);
fscanf(f1,"%d",&a1);
i++;
}
else {
fprintf(f,"%d ",a2);
fscanf(f2,"%d",&a2);
j++;
}
}
while ( i < k && !feof(f1) ) {
fprintf(f,"%d ",a1);
fscanf(f1,"%d",&a1);
i++;
}
while ( j < k && !feof(f2) ) {
fprintf(f,"%d ",a2);
fscanf(f2,"%d",&a2);
j++;
}
}
while ( !feof(f1) ) {
fprintf(f,"%d ",a1);
fscanf(f1,"%d",&a1);
}
while ( !feof(f2) ) {
fprintf(f,"%d ",a2);
fscanf(f2,"%d",&a2);
}
fclose(f2);
fclose(f1);
fclose(f);
k *= 2;
}
remove("smsort_1");
remove("smsort_2");
}

s2, a1, a2, mark;
FILE *f, *f1, *f2;
s1 =

s2 = 1;
while ( s1 > 0 && s2 > 0 ){
mark = 1;
s1 = 0;
s2 = 0;
f = fopen(name,"r");
f1 = fopen("nmsort_1","w");
f2 = fopen("nmsort_2","w");
fscanf(f,"%d",&a1);
if ( !feof(f) ) {
fprintf(f1,"%d ",a1);
}
if ( !feof(f) ) fscanf(f,"%d",&a2);
while ( !feof(f) ){
if ( a2 < a1 ) {
switch (mark) {
case 1:{fprintf(f1,"' "); mark = 2; s1++; break;}
case 2:{fprintf(f2,"' "); mark = 1; s2++; break;}
}
}
if ( mark == 1 ) { fprintf(f1,"%d ",a2); s1++; }
else { fprintf(f2,"%d ",a2); s2++;}
a1 = a2;
fscanf(f,"%d",&a2);
}
if ( s2 > 0 && mark == 2 ) { fprintf(f2,"'");}
if ( s1 > 0 && mark == 1 ) { fprintf(f1,"'");}
fclose(f2);
fclose(f1);
fclose(f);

cout << endl;
Print_File(name);
Print_File("nmsort_1");
Print_File("nmsort_2");
cout << endl;

f = fopen(name,"w");
f1 = fopen("nmsort_1","r");
f2 = fopen("nmsort_2","r");
if ( !feof(f1) ) fscanf(f1,"%d",&a1);
if ( !feof(f2) ) fscanf(f2,"%d",&a2);
bool file1, file2;
while ( !feof(f1) && !feof(f2) ){
file1 = file2 = false;
while ( !file1 && !file2 ) {
if ( a1 <= a2 ) {
fprintf(f,"%d ",a1);
file1 = End_Range(f1);
fscanf(f1,"%d",&a1);
}
else {
fprintf(f,"%d ",a2);
file2 = End_Range(f2);
fscanf(f2,"%d",&a2);
}
}
while ( !file1 ) {
fprintf(f,"%d ",a1);
file1 = End_Range(f1);
fscanf(f1,"%d",&a1);
}
while ( !file2 ) {
fprintf(f,"%d ",a2);
file2 = End_Range(f2);
fscanf(f2,"%d",&a2);
}
}
file1 = file2 = false;
while ( !file1 && !feof(f1) ) {
fprintf(f,"%d ",a1);
file1 = End_Range(f1);
fscanf(f1,"%d",&a1);
}
while ( !file2 && !feof(f2) ) {
fprintf(f,"%d ",a2);
file2 = End_Range(f2);
fscanf(f2,"%d",&a2);
}
fclose(f2);
fclose(f1);
fclose(f);
}
remove("nmsort_1");
remove("nmsort_2");
}
//определение конца блока
bool End_Range (FILE * f){
int tmp;
tmp = fgetc(f);
tmp = fgetc(f);
if (tmp != '\'') fseek(f,-2,1);
else fseek(f,1,1);
return tmp == '\'' ? true : false;
}