Міністерство Освіти України Національний університет "Львівська політехніка" М Е Т О Д И Ч Н А В К А З І В К А До лабораторної роботи № 6 На тему: “ Методи сортування. Злиття.” з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки" ЗАТВЕРДЖЕНО на засіданні кафедри програмного забезпечення протокол № від 2007 р. Львів – 2007 Методичні вказівки до лабораторних робіти з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки" Укладач: [ім’я автора приховано] [ім’я автора приховано] Відповідальний за випуск: Рецензенти: Тема роботи: Ознайомлення із методами сортування. Зокрема із методом злиття. Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із цифровим методом сортування. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу Шелла. ТЕОРЕТИЧНІ ВІДОМОСТІ Ключ, по якому відбувається сортування, необхідно розділити на частини, розряди ключа. Наприклад, слово можна розділити по буквах, число - по цифрах... До сортування необхідно знати два параметри: до і m, де к - кількість розрядів в щонайдовшому ключі m - розрядність даних: кількість можливих значень розряду ключа При сортуванні українських слів m = 33, оскільки буква може приймати не більше 33 значень. Якщо в щонайдовшому слові 10 букв, до = 10. Аналогічно, для шістнадцяткових чисел m=16, якщо як розряд брати цифру, і m=256, якщо використовувати побайтове ділення. Ці параметри не можна змінювати в процесі роботи алгоритму. У цьому - ще одна відмінність методу від вищеописаних. Сортування масивів Нехай в нас є масив source з n десяткових цифр ( m = 10 ). Наприклад, source[7]= { 7, 9, 8, 5, 4, 7, 7 }, n=7. Тут покладемо const k=1. Створити масив count з m елементів(лічильників). Привласнити count[i] кількість елементів source, рівних i. Для цього: проинициализовать count[] нулями пройти по source від початку до кінця, для кожного числа збільшуючи елемент count з відповідним номером. for( i=0; i<n; i++) count [ source[i]]++ У нашому прикладі count[] = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 } Привласнити count[i] значення, рівне сумі всіх елементів до даного: count[i]= count[0]+count[1]+...count[i-1]. У нашому прикладі count[] = { 0, 0, 0, 0, 1, 2, 2, 2, 5, 6 }Ця сума є кількістю чисел початкового масиву, менших i. Провести остаточну розстановку. Для кожного числа source[i] ми знаємо, скільки чисел менше його - це значення зберігається в count[ source[i]]. Таким чином, нам відоме остаточне місце числа у впорядкованому масиві: якщо є K чисел менше даного, то воно повинне стояти на на позиції K+1. Здійснюємо прохід по масиву source зліва направо, одночасно заповнюючи вихідний масив dest: for ( i=0; i<n; i++ ) { з = source[i]; dest[ count[c]]= з; count[c]++; // для чисел, що повторюються } Таким чином, число c=source[i] ставиться на місце count[c]. На цей випадок, якщо числа повторюються в масиві, передбачений оператор count[c]++, який збільшує значення позиції для наступного числа з, якщо таке буде. Цикли займають (n + m) часу. Стільки ж вимагається пам'яті. Отже, ми навчилися за (n + m) сортувати цифри. А від цифр до рядків і чисел - 1 крок. Хай у нас в кожному ключі до цифр ( m = 10 ). Аналогічно злучаю із списками відсортуємо їх в декілька проходів від молодшого розряду до старшого.
Загальна кількість операцій, таким чином, ( до(n+m)), при використовуваній додатково пам'яті (n+m). Реалізація програми: // Функція для останнього проходу при порозрядному сортуванні чисел з плаваючою крапкою template<class T> void floatRadixLastPass (short Offset, long N, T *source, T *dest, long *count) { T *sp; long s, з, i *cp; uchar *bp; long numNeg=0; for(i=128;i<256;i++) numNeg += count[i]; s=numNeg; cp = count; for (i = 0; i < 128; ++i, ++cp) { з = *cp; *cp = s; s += з; // зміни, що стосуються зворотного розташування негативних чисел. s = count[255]= 0; // cp = count+254; // for (i = 254; i >= 128; --i, --cp) {// *cp += s; // останнє - те ж, що в е р б s = *cp; // signedRadixLastPass bp = (uchar *)source + Offset; sp = source; for (i = N; i > 0; --i, bp += sizeof(T) ++sp) { cp = count + *bp; if (*bp<128) dest[ (*cp)++ ]= *sp; else dest[ --(*cp) ]= *sp; } 2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм Шелла. Використовувати мову програмування C/C++. Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи. 3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ Отримати індивідуальне завдання у викладача; Уточнити завдання(можливі різні трактування завдання); Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу(алгоритму) на даній лабораторній роботі; Протестувати на наявність логічних помилок програми; Оформити звіт відповідно до стандарту; Захистити виконану роботу. 4. КОНТРОЛЬНІ ПИТАННЯ Які ви знаєте методи сортування? Який метод сортування був розглянений на даній лабораторній роботі? Від чого прямо – залежним являється швидкість сортування? Опишіть характеристики даного методу. Порівняєте даний метод із іншими методами сортування вам відомими. Наскільки являється ефективним даний метод сортування? Чи використовують даний метод на практиці, і наскільки часто? Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах? Чим оригінальним виділяється даний метод від інших? 5. ІНДИВІДУАЛЬНЕ ЗАВДАНЯ