g30zAZLYUG

a[i].key= 10 + rand()%200; // Случайное число в интервале 10 - 210

strcpy(a[i].info,stars);		// "Звёздочки" во втором поле записи
}
cout << " До сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}

ShellSort();

cout << " После сортировки \n";

for (i=0; i<n; i++) {cout << a[i].key << " " << a[i].info << "\n";}

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

3. Программная реализация сортировки слиянием

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 // Максимальное количество элементов в массиве struct MY_NODE

{

int key;

char info[15]; };

MY_NODE a[MAX_SIZE]; int n;

// Слияние двух упорядоченных массивов

MY_NODE* merge( MY_NODE *array1, MY_NODE* array2, int length1, int length2)

{

MY_NODE* ret = new MY_NODE[length1+length2]; int k=0, k1=0, k2=0;

// Сливаем массивы, пока один не закончится while (length1 && length2)

{

if (array1[k1].key < array2[k2].key)

{

ret[k] = array1[k1]; k1++; length1--;

}

else

{

111

ret[k] = array2[k2]; k2++; length2--;

}

k++;

}

//Если закончился первый массив, перегружаем остаток из второго if (length1 == 0)

{

for (int i=0; i<length2; i++)

{

ret[k] = array2[k2]; k++; k2++;

}

}

//Если закончился второй массив, перегружаем остаток из первого else

{

for (int i=0; i<length1; i++ )

{

ret[k] = array1[k1]; k++; k1++;

}

}

return ret;

}

// Функция восходящего слияния void MergeSort()

{

int k = 1, l, rest; MY_NODE * newArray; while( k < n )

{

l=0;

while ( l < n )

{

if ( l+k >= n ) { break;

}

rest = ( l + k * 2 > n ) ? ( n - ( l + k ) ) : k; newArray = merge( a + l, a + l + k, k, rest ); for ( int i = 0; i < k + rest; i++ )

{

a[ l + i ] = newArray[ i ];

}

delete [] newArray;

112

l += k * 2;

}

k*=2;

}

}

int main ()

{

int i; char *stars="***"; setlocale(LC_ALL, "RUS"); cout << "Merge Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: ";

cin >> n;	cin.ignore();
srand ( time(NULL) ); // Инициализация генератора случайных чисел
for (i=0; i<n; i++)
{
a[i].key= 10 + rand()%200; // Случайное число в интервале 10 - 210
strcpy(a[i].info,stars);		// "Звёздочки" во втором поле записи
}
cout << " До сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}
MergeSort();
cout << " После сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n"; }

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

4. Программная реализация пузырьковой сортировки

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 struct MY_NODE

{

int key;

char info[15]; };

MY_NODE a[MAX_SIZE]; int n;

void BubbleSort()

113

{int i,j; MY_NODE buf;
for (i=0; i<n-1; i++)
{
for (j=0; j<n-1-i; j++)
{
if (a[j].key>a[j+1].key)
{
buf=a[j]; a[j]=a[j+1];	a[j+1]=buf;
};
};
};
};
int main ()
{
int i; char *stars="***";
setlocale(LC_ALL, "RUS");
cout << "Bubble Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: "; cin >> n; cin.ignore();

srand ( time(NULL) ); // Инициализация генератора случайных чисел for (i=0; i<n; i++)

{

a[i].key= 10 + rand()%300; // Случайное число в интервале 10 - 310

strcpy(a[i].info,stars);		// "Звёздочки" во втором поле записи
}
cout << " До сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}
BubbleSort();
cout << " После сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

5. Программная реализация быстрой сортировки

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 // Максимальное количество элементов в массиве struct MY_NODE

114

{

int key;

char info[15]; };

MY_NODE a[MAX_SIZE]; int n;

void QuickSort(int first, int last) {int f,l,y,m,i; MY_NODE buf; f=first; l=last;

srand(0);

m=first+rand()%(last-first); y=a[m].key; do

{while (a[f].key < y) {f++;}; while (a[l].key > y) {l--;}; if (f<=l)

{buf=a[f]; a[f]=a[l]; a[l]= buf; f++; l--;};

}

while (f<=l);

if (l>first) {QuickSort(first,l);}; if (f<last) {QuickSort(f,last);};

}

int main ()

{

int i; char *stars="***"; setlocale(LC_ALL, "RUS"); cout << "Quick Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: ";

cin >> n;	cin.ignore();
srand ( time(NULL) ); // Инициализация генератора случайных чисел
for (i=0; i<n; i++)
{
a[i].key= 10 + rand()%200; // Случайное число в интервале 10 - 210
strcpy(a[i].info,stars);		// "Звёздочки" во втором поле записи
}
cout << " До сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}
QuickSort(0,n-1);
cout << " После сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

115

6. Программная реализация сортировки извлечением (простым вы-

бором)

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 // Максимальное количество элементов в массиве struct MY_NODE

{

int key;

char info[15]; };

MY_NODE a[MAX_SIZE]; int n;

// Сортировка извлечением (простым выбором) void SelectSort()

{int i,j,k,min,p_min; MY_NODE buf; for (i=0; i<n-1; i++)

{ min=a[i].key; p_min=i; for (j=i+1; j<n; j++)

{if (a[j].key<min)

{min=a[j].key; p_min=j;

};

};

buf=a[i]; a[i]=a[p_min]; a[p_min]=buf; };

}

int main ()

{

int i; char *stars="***"; setlocale(LC_ALL, "RUS"); cout << "Select Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: "; cin >> n; cin.ignore();

srand ( time(NULL) ); // Инициализация генератора случайных чисел for (i=0; i<n; i++)

{

a[i].key= 10 + rand()%200; // Случайное число в интервале 10 - 210 strcpy(a[i].info,stars); // "Звёздочки" во втором поле записи

}

cout << " До сортировки \n";

116

for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}
SelectSort();
cout << " После сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

7. Программная реализация древесной сортировки

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 // Максимальное количество элементов в массиве struct MY_NODE

{

int key;

char info[15]; };

MY_NODE a[MAX_SIZE]; int n;

void Heap(int first, int last) /* peresipka */ { int k,k21,k22; MY_NODE buf;

if (2*first+1 <= last) /* first - ne kontsevaja */

{

k=first; k21=2*first+1; k22=k21+1; if (a[k].key<a[k21].key) {k=k21;};

if (k22<=last && a[k].key<a[k22].key) {k=k22;}; if (k!=first)

{buf=a[first]; a[first]=a[k]; a[k]=buf; Heap(k,last);};

}

}

void BuildSortTree() {int i;

for (i=n-1; i>=0; i--) {Heap(i,n-1);};

}

void HeapSort()

{int i,i0; MY_NODE buf; BuildSortTree();

for (i=n-1; i>0; i--)

117

{buf=a[0]; a[0]=a[i]; a[i]=buf; Heap(0,i-1); };

}

int main ()

{

int i; char *stars="***"; setlocale(LC_ALL, "RUS"); cout << "Tree Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: "; cin >> n; cin.ignore();

srand ( time(NULL) ); // Инициализация генератора случайных чисел for (i=0; i<n; i++)

{

a[i].key= 10 + rand()%200; // Случайное число в интервале 10 - 210

strcpy(a[i].info,stars);		// "Звёздочки" во втором поле записи a
}
cout << " До сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}

HeapSort();

cout << " После сортировки \n";

for (i=0; i<n; i++) {cout << a[i].key << " " << a[i].info << "\n";}

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

8. Программная реализация цифровой сортировки

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 // Максимальное количество элементов в массиве #define MAX_NUMBER 210 // Максимальный элемент в массиве

int n, a[MAX_SIZE]; void DigitSort()

{int i,j; int count[MAX_NUMBER+1];

for (j=0; j<=MAX_NUMBER; j++) {count[j]=0;}; for (i=0; i<n; i++) {count[a[i]]++;};

cout << " После сортировки \n"; for (j=0; j<=MAX_NUMBER; j++)

{ for(i=1; i<=count[j]; i++) {cout << j << "\n";}

}

118

}

int main ()

{

int i; char *stars="***"; setlocale(LC_ALL, "RUS"); cout << "Digit Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: "; cin >> n; cin.ignore();

srand ( time(NULL) ); // Инициализация генератора случайных чисел for (i=0; i<n; i++)

{

a[i] = 10 + rand()%200; // Случайное число в интервале 10 - 210

}

cout << " До сортировки \n";

for (i=0; i<n; i++) {cout << a[i] << " " << "\n";} DigitSort();

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

9. Программная реализация сортировки подсчётами

#include "stdafx.h" #include <iostream> #include <locale.h> #include <ctime> using namespace std;

#define MAX_SIZE 101 // Максимальное количество элементов в массиве #define MAX_NUMBER 210 // Максимальный элемент в массиве

struct MY_NODE

{

int key;

char info[15]; };

MY_NODE a[MAX_SIZE]; int n;

void CountSort()

{int i,j,k; int count[MAX_NUMBER+1]; MY_NODE b[MAX_SIZE];

for (j=0; j<=MAX_NUMBER; j++) {count[j]=0;};

for (i=0; i<n; i++)	{b[i]=a[i];};
for (i=0; i<n; i++)	{count[b[i].key]++;};

for (j=1; j<=MAX_NUMBER; j++) {count[j]+=count[j-1];};

119

for (i=0; i<n; i++) {k=count[b[i].key];

a[k-1]=b[i]; /* "a" c 0 pos!!! -> "-1" */ count[b[i].key]--;};

}

int main ()

{

int i; char *stars="***"; setlocale(LC_ALL, "RUS"); cout << "Count Sr\n";

cout << "Введите размерность массива n (n<=100) и нажмите <<Enter>>: ";

cin >> n;	cin.ignore();
srand ( time(NULL) ); // Инициализация генератора случайных чисел
for (i=0; i<n; i++)
{
a[i].key= 10 + rand()%200; // Случайное число в интервале 10 - 210
strcpy(a[i].info,stars);		// "Звёздочки" во втором поле записи
}
cout << " До сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}
CountSort();
cout << " После сортировки \n";
for (i=0; i<n; i++)	{cout << a[i].key << " " << a[i].info << "\n";}

cout << "Нажмите клавишу ENTER, чтобы закрыть программу \n"; getchar();

return 0;

}

120