Впорядкування масивів Максименко Марина Миколаївна вчитель інформатики вищої категорії, вчитель- методист Конотопської гімназії Конотопської міської ради Сумської області 2008 р.

Зміст Функція sizeof Функція sizeof Сортування простим пошуком Метод бульбашки Задачі Література

Сортування одновимірних масивів Функція sizeof Функція визначення розміру sizeof використовується для обчислення розміру значення виразу чи типу в байтах і має дві форми: sizeof(вираз) sizeof (тип) Наприклад: #include int main () { int little[5]={1,2, 3, 4, 5}; double x=1; cout<<sizeof(float)=<<sizeof(float)<<endl; cout<<sizeof(int)=<<sizeof(int)<<endl; cout<<sizeof(x)=<<sizeof(x)<<endl; cout<<sizeof(x+1)=<<sizeof(x+1)<<endl; cout<<sizeof(little)=<<sizeof(little)<<endl; getch(); return 0; } Результат роботи: sizeof(float)=4 sizeof(int)=4 sizeof(x)=8 sizeof(x+1)=8 sizeof(little)=20 //5*4

Сортування одновимірних масивів Сортування простим пошуком Алгоритм: Заповнити масив з n елементів Організувати перегляд масиву n-1 разів Знайти максимальний елемент у невідсортованій частини масиву; запам'ятати його номер Поміняти значення знайденого максимального елементу зі значення початкового елементу невідсортованої частини масиву Вивести отриманий масив

Сортування одновимірних масивів Сортування простим пошуком #include Int MaxEl(int a[], int m, int n) { int max=a[m]; int L=m; for (int i=m+1; i =max) {max=a[i]; L=i;} return L; } int main () { int c[]={1,6,21,4,3,5,8,9,7,90,123,1,3 45}; int mc=0; int nc=sizeof(c)/sizeof(int); int temp, Lc; while(mc<nc) { Lc=MaxEl(c, mc, nc); temp=c[mc]; c[mc]=c[Lc]; c[Lc]=temp; mc++} for (int i=0; i<nc;i++) cout<< <<c[i]; getch();return 0; } Буде правильно опрацьований масив будь-якого розміру nc=sizeof(c)/sizeof(c[0]) - робота оператора не залежатиме навідь від типу елементів масиву

Сортування одновимірних масивів Метод бульбашки Алгоритм: Заповнити масив з n елементів Організувати перегляд масиву n-1 разів Організувати порівняння значень кожної пари сусідніх елементів Якщо значення попереднього елементу більше, ніж наступного, переставити сусідні елементи місцями Вивести отриманий масив void bubl(int *mas[], int n) { int i.j; int rab; for(j=1; j *mas[i]) { rab=*mas[i-1]; *mas[i-1]=*mas[i]; *mas[i]=rab; } } ….bubl(&a, n); //виклик

Сортування одновимірних масивів Метод бульбашки (покращений варіант) void bubl(int *mas[], int n) {bool fl=false; int rab,j=1; do { fl=false; for (int i=0;i *mas[i+1]) {rab=*mas[i-1]; *mas[i-1]=*mas[i]; *mas[i]=rab; fl=true; } j++ } while (fl); } Може виявитися, що одного перегляду масиву буде досить для впорядкування. Скільки ж разів потрібно виконувати такий перегляд? Відповідь – стільки, скільки потрібно для повного сортування, тобто поки при повному перегляді від початку до кінця масиву жодна пара елементів не поміняється місцями. Для припинення сортування зручно скористатися логічною змінною, котрій спочатку присвоюється false, а потім присвоюється значення true при кожному обміні. Якщо при черговому перегляді не відбулося жодного обміну, значення цієї змінної залишається false і перегляд припиняється.

Задачі 1. Дослідити, чому у функції buble використовується вказівники. Що буде, якщо їх прибрати? 2. Випробуйте наведені методи сортування. Масиви впорядковуються за зростанням чи за спаданням. Змініть порядок сортування. 3. Вдоскональте програми, доповнивши їх двома функціями: для виведення масиву і для обміну двох значень (swap) 4. Підрахуйте, скільки різних чисел є значеннями елементів масиву 5. Визначте, яке число найчастіше зустрічається в масиві 6. Увести два масиви. Знайти числа, які зустрічаються в кожному з двох масивів 7. Увести два впорядкованих за зростанням масиви. Об'єднати їх в один масив так, щоб він виявився впорядкованим за зростанням

Література Лєхан С.Ф. Інформатика С++. Спецкурс класи. – Шепетівка; Аспект, Глинський Я.М., Анохін В.Є., Ряжська В.А. С++ і С++ Builder. Навчальний посібник. – Львів: СПД Глинський, Глушаков С.В., Смирнов С.В., Коваль А.В. Практикум по С++. – Харьков: Фолио, Павловская Т.А. С/С++. Программирование на языке высокого уровня. – СПб.: Питер, 2003 Лисенко Т.І. Поглиблене вивчення програмування в школі. – К.:ТОВ Редакція Комп'ютер, 2007.