Основні методи сортування масивів

Починаючи з даного розділу, розглянемо декілька методів впорядкування елементів масиву, які широко використовуються у практичному програмуванні.

1.12.1 Метод бульбашкового сортування
Метод "бульбашкового сортування" ґрунтується на перестановці сусідніх елементів. Для впорядкування елементів масиву здійснюються повторні проходи по масиву.
Переміщення елементів масиву здійснюється таким чином: масив переглядається зліва направо, здійснюється порівняння пари сусідніх елементів; якщо елементи в парі розміщені в порядку зростання, вони лишаються без змін, а якщо ні - міняються місцями.
В результаті першого проходу найбільше число буде поставлено в кінець масиву. У другому проході такі операції виконуються над елементами з першого до (N-1)-ого, у третьому - від першого до (N-2)-ого і т.д. Впорядкування масиву буде закінчено, якщо при проході масиву не виконається жодної перестановки елементів масиву. Факт перестановки фіксується за допомогою деякої змінної (у наступному прикладі - is), яка на початку має значення 0 і набуває значення 1 тоді, коли виконається перестановка в якій-небудь парі.

Масив до впорядкування			-1	-40		-75	-22
Перший перегляд масиву		-1	-40		-75	-22
Другий перегляд масиву	-1	-40		-75	-22
Третій перегляд масиву	-40	-1	-75	-22
Четвертий перегляд масиву	-40	-75	-22	-1
П'ятий перегляд масиву	-75	-40	-22	-1

Рис. 1.15. Бульбашкове сортування

const n=10;
int a[n], i, c, is;
/* … */
do {
is=0;
for (i=1;i<n;i++)
if (a[i-1]>a[i])
{
c=a[i];
a[i]=a[i-1];
a[i-1]=c;
is=1;
}
} while (is);

1.12.2 Сортування методом вибору
Даний метод сортування передбачає наступні дії: масив переглядається перший раз, знаходиться мінімальний елемент цього масиву, який міняється місцями з першим елементом. Другий раз масив переглядається, починаючи з другого елементу. Знову знаходиться мінімальний елемент, який міняється місцями з другим елементом масиву.
Даний процес виконується до тих пір, поки не буде поставлено на місце N-1 елемент.

Масив до впорядкування			-1	-40		-75	-22
Перший перегляд масиву	-75		-1	-40			-22
Другий перегляд масиву	-75	-40	-1				-22
Третій перегляд масиву	-75	-40	-22				-1
Четвертий перегляд масиву	-75	-40	-22	-1
П'ятий перегляд масиву	-75	-40	-22	-1
Шостий перегляд масиву	-75	-40	-22	-1

Рис. 1.16. Сортування методом вибору

const int n=20;
int b[n];
int imin, i, j, a;
/* … */
for (i=0;i<n-1;i++)
{
imin=i;
for (j=i+1;j<n;j++)
if (b[j]<b[imin]) imin=j;
a=b[i];
b[i]=b[imin];
b[imin]=a;
}

1.12.3 Сортування вставками
Даний метод сортування називається сортування вставками, так як на і-му етапі відбувається "вставка" і-ого елемента a[i] в потрібну позицію серед елементів a[1], a[2], …, a[i-1], які вже впорядковані. Після цієї вставки перші і елементів будуть впорядковані.
Саме таким способом звичайно сортують карти, тримаючи в лівій руці вже впорядковані карти, і взявши правою рукою чергову карту вставляють її в потрібне місце, порівнюючи її з іншими проходячи справа наліво.

Масив до впорядкування			-1	-40		-75	-22
Перший перегляд масиву			-1	-40		-75	-22
Другий перегляд масиву	-1			-40		-75	-22
Третій перегляд масиву	-40	-1				-75	-22
Четвертий перегляд масиву	-40	-1				-75	-22
П'ятий перегляд масиву	-75	-40	-1				-22
Шостий перегляд масиву	-75	-40	-22	-1

Рис. 1.17. Сортування вставками

Реалізувати сортування масиву вставками можна так:

const int n=20;
int b[n];
int i,j,c;
/* … */
for (i=1;i<n;i++)
{
c=a[i];
for (j=i-1;j>=0&&a[j]>c;j--)
a[j+1]=a[j];
a[j+1]=c;
}

1.12.4 Швидке сортування
Швидке сортування полягає в тому, що множина елементів В { k1, k2, …, kn } перетворюється на множину B1, {k1}, B2, де В1 - підмножина В з елементами, не більшими за k1, а В2 - підмножина В з елементами більшими k1. Причому елемент k1 після розбиття множини В буде перебувати на потрібному місці. Далі до множин B1 і B2 знову застосовують впорядкування швидким сортуванням.
Час роботи алгоритму швидкого сортування в гіршому випадку складає О(n2), але на практиці цей алгоритм виявляється одним із найшвидших.

double * quick(double *s,int low,int hi)
{
double cnt,aux;
int i,j;
if (hi>low)
{
i=low;
j=hi;
cnt=s[i];
while(i < j)
{
if (s[i+1]<=cnt)
{
s[i]=s[i+1];
s[i+1]=cnt;
i++;
}
else
{
if (s[j]<=cnt)
{
aux=s[j];
s[j]=s[i+1];
s[i+1]=aux;
}
j--;
}
}
quick(s,low,i-1);
quick(s,i+1,hi);
}
return(s);
}

1.13 Структури

1.13.1 Оголошення структури
Структури дозволяють об'єднувати в єдиному об'єкті сукупність значень, які можуть мати різні типи. Оголошення структури здійснюється за допомогою ключового слова struct.
Синтаксис опису структури виглядає так:
struct [ім'я_структури]
{
тип1 елемент1;
тип2 елемент2;
........................
типN елементN;
} [список описів];
З метою ознайомлення з цим типом даних розглянемо найпростіший приклад представлення поняття "дата", що складається з декількох частин: число (день, місяць, рік), назва тижня та місяця:
struct date {
int day;
int month;
int year;
char day_name[15];
char mon_name[14];
} arr[100],*pd,data,new_data;
В даному прикладі оголошуються:
data, new_data - змінні типу структури date;
pd - покажчик на тип data
arr - масив із 100 елементів, кожний елемент якого має тип date.
Можливий і наступний опис структури з використанням typedef:
typedef struct mystruct {
int year;
char size;
float field;
} MYSTRUCT;
MYSTRUCT s; /* те саме, що й struct mystruct s; */
Пам'ять розподіляється у структурі покомпонентно, зліва-направо, від молодших до старших адрес пам'яті (рис. 1.18).
typedef struct dataTypes {
float aFloat;
int anInt;
char aString[8];
char aChar;
char aLong;
} DataTypes;
DataTypes data;

Потрібно відзначити, що на відміну від описів інших типів даних, опис структури не виділяє місця у пам'яті під елементи структури. Її опис визначає лише так званий шаблон, що описує характеристики змінних, що будуть розміщуватися у конкретній структурі. Щоб ввести змінні та зарезервувати для них пам'ять необхідно або після фігурної дужки, що завершує опис структури, вказати список ідентифікаторів, як це зроблено у вищенаведеному прикладі, або окремо оголосити змінні типу, як ми це робимо у звичайних випадках.
Доступ до окремого елемента структури забезпечується операторами вибору:. (прямий селектор) та -> (непрямий селектор), наприклад,
struct mystruct {
int i;
char str[21];
double d;
} s,*sptr=&s;
s.i =3;
sptr->d = 1.23;
Ініціалізація структури подібна до тієї, що у масивах, але з урахуванням розміщення даних різного типу.
struct person {
char frnm[20];
char nm[30];
int year;
char s;
};
struct person poet={"Taras", "Shevtchenko",1814, 'M'},classics[]={{"Alfred", "Aho", 1939, 'M'},{"Seimour", "Ginzburg",}, /* … */ {"Jeffrey", "Ulman", 1938, 'M'}};
У вищенаведеному прикладі ініціалізується змінна poet і масив структур classics. Значення classics[1].year і classics[1].s мають значення відповідно 0 і '\0'.
Для змінних одного і того ж самого структурного типу визначена операція присвоювання, при цьому здійснюється поелементне копіювання значень полів.
struct date {
int day;
int month;
int year;
char day_name[15];
char mon_name[14];
} data,new_data;
/*... */
data=new_data;
Але, для порівняння структур необхідно перевіряти рівність відповідних полів цих структур.
struct point
{
float x,y;
char c;
} point1,point2;
if (point1.x==point2.x&&point1.y==point2.y&&point1.c==point2.c)
{
/* … */
};
Звертання до окремих елементів структури теж не викликає труднощів:
data.year=2005;
printf("%d-%d-%d",data.day,data.month,data.year);
scanf("%d",data.day);
gets(arr[0].day_name);
Доцільним та корисним є зв'язок структур та покажчиків, який дозволяє обійти деякі складні моменти. Так опис date *pdate утворить покажчик на структуру типу date. Використовуючи цей покажчик, можна звернутися до будь-якого елемента структури шляхом застосування операції ->, тобто date ->year, або що еквівалентно операції (*pdate).year. Однак слід зауважити, що спільне використання цих типів потребує від програміста достатньо високої кваліфікації, аби використовувати можливості найбільш ефективно та безпомилково.
Приклад 1.
#include<stdio.h>
#include<conio.h>
#define MAXTIT 41
#define MAXAUT 31
struct book
{
char title[MAXTIT];
char author[MAXAUT];
float value;
};
void main()
{
struct book libry;
printf("Введiть назву книги.\n");
gets(libry.title);
printf("Тепер введiть прiзвище автора.\n");
gets(libry.author);
printf("Тепер введiть цiну.\n");
scanf("%f",&libry.value);
printf("\n%s '%s',%g grn.\n",libry.author,
libry.title,libry.value);
};
Кожний опис структури вводить унікальний тип структури, тому в наступному фрагменті програми:
struct A {
int i,j;
double d;
} a, a1;
struct B {
int i,j;
double d;
} b;
об'єкти a і a1 мають однаковий тип struct A, але об'єкти a і b мають різні типи структури. Структурам можна виконувати присвоювання тільки в тому випадку якщо і вихідна структура, і структура, які присвоюється мають один і той же тип.
a = a1; /*можна виконати, так як a і a1 мають однаковий тип */
a = b; /* помилка */

1.13.2 Масиви структур
Як і звичайними масивами простих типів, так само можна оперувати масивами структур, елементи якого мають структурований тип. Розглянемо наочний зразок, який ілюструє оголошення масиву структур:
typedef struct Date
{
int d; /* день */
int m; /* мiсяць */
int y; /* рiк */
} Date;
Date arr[100];
Вище було оголошено масив arr, що складається із 100 елементів, кожний з яких має тип Data. Кожний елемент масиву - це окрема змінна типу Data, що складається із трьох цілих елементів - d, m, y.
Доступ до полів структури аналогічний доступу до звичайних змінних, плюс використання індексу номеру елементу у квадратних дужках:
arr[25].d=24;
arr[12].m=12;
Запропонуємо програму, в якій реалізується концепція структурованого типу Data. Окремими функціями реалізуємо ініціалізацію елементів структури, додавання нового значення, виведення дати на екран, визначення високосного року.
#include<stdio.h>
#include<conio.h>
typedef struct Date
{
int d; /* день */
int m; /* мiсяць */
int y; /* рiк */
} Date;
void set_date_arr(Date *arr,Date value,int n)
{
int i;
for (i=0;i<n;i++)
{
arr[i].d=value.d;
arr[i].m=value.m;
arr[i].y=value.y;
}
}

void print_date_arr(Date *arr,int n)
{
int i;
for (i=0;i<n;i++)
{
printf("%d.%d.%d\n",arr[i].d,arr[i].m,arr[i].y);
}
}

void print_date(Date &d)
/* виведення на екран дати */
{
printf("%d.%d.%d\n",d.d,d.m,d.y);
}

void init_date(Date &d,int dd,int mm,int yy)
/* iнiцiалiзацiя структури типу Date */
{
d.d=dd;
d.m=mm;
d.y=yy;
}

int leapyear(int yy)
/* визначення, чи високосний рiк */
{
if ((yy%4==0&&yy%100!=0)||(yy%400==0)) return 1;
else return 0;
}

void add_year(Date &d,int yy)
/* додати yy рокiв до дати */
{
d.y+=yy;
}

void add_month(Date &d,int mm)
/* додати mm мiсяцiв до дати */
{
d.m+=mm;
if (d.m>12)
{
d.y+=d.m/12;
d.m=d.m%12;
}
}

void add_day(Date &d,int dd)
/* додати dd днiв до дати */
{
int days[]={31,28,31,30,31,30,31,31,30,31,30,31};
d.d+=dd;
if (leapyear(d.y)) days[1]=29;
while ((d.d>days[d.m-1]))
{
if (leapyear(d.y)) days[1]=29;
else days[1]=28;
d.d-=days[d.m-1];
d.m++;
if (d.m>12)
{
d.y+=d.m%12;
d.m=d.m/12;
}
}
}

void main(void)
{
Date date1,date2;
Date array[10]={{12,11,1980},{15,1,1982},{8,6,1985},{8,8,1993},{20,12,2002},{10,1,2003}};
clrscr();
init_date(date1,15,12,2002);
add_day(date1,16);
print_date(date1);
puts("");
init_date(date2,1,1,2003);
add_month(date2,10);
print_date(date2);
puts("");
print_date_arr(array,6);
}

1.13.3 Бітові поля
Бітові поля (bit fields) - особливий вид полів структури. Вони дають можливість задавати кількість бітів, в яких зберігаються елементи цілих типів. Бітові поля дозволяють раціонально використовувати пам'ять за допомогою зберігання даних в мінімально потрібній кількості бітів.
При оголошенні бітового поля вслід за типом елемента ставиться двокрапка (:) і вказується цілочисельна константа, яка задає розмір поля (кількість бітів). Розмір поля повинен бути константою в діапазоні між 0 і заданим загальним числом бітів, яке використовується для зберігання даного типу даних.
struct bit_field {
int bit_1: 1;
int bits_2_to_5: 4;
int bit_6: 1;
int bits_7_to_16: 10;
} bit_var;

1.14 Об'єднання (union)

Об'єднання дозволяють в різні моменти часу зберігати в одному об'єкті значення різного типу. В процесі оголошення об'єднання з ним асоціюється набір типів, які можуть зберігатися в даному об'єднанні. В кожний момент часу об'єднання може зберігати значення тільки одного типу з набору. Контроль за тим, значення якого типу зберігається в даний момент в об'єднанні покладається на програміста.
Синтаксис:
union [ім'я_об'єднання]
{
тип1 елемент1;
тип2 елемент2;
........................
типN елементN;
} [список описів];
Пам'ять, яка виділяється під змінну типу об'єднання, визначається розміром найбільш довгого з елементів об'єднання. Всі елементи об'єднання розміщуються в одній і тій же області пам'яті з однієї й тієї ж адреси. Значення поточного елемента об'єднання втрачається, коли іншому елементу об'єднання присвоюється значення.
Приклад 1:
union sign
{
int svar;
unsigned uvar;
} number;
Приклад 2:
union
{
char *a,b;
float f[20];
} var;
В першому прикладі оголошується змінна типу об'єднання з ім'ям number. Список оголошень елементів об'єднання містить дві змінні: svar типу int і uvar типу unsigned. Це об'єднання дозволяє запам'ятати ціле значення в знаковому або в без знаковому вигляді. Тип об'єднання має ім'я sign.
В другому прикладі оголошується змінна типу об'єднання з ім'ям var. Список оголошень елементів містить три оголошення: покажчика a на значення типу char, змінної b типу char і масиву f з 20 елементів типу float. Тип об'єднання не має імені. Пам'ять, що виділяється під змінну var, рівна пам'яті, необхідної для зберігання масиву f, так як це найдовший елемент об'єднання.

Дата добавления: 2014-01-07