Міністерство Освіти України Національний університет "Львівська політехніка" М Е Т О Д И Ч Н А В К А З І В К А До лабораторної роботи № 1 На тему: “ Методи сортування. Алгоритм вибірки.” з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки" ЗАТВЕРДЖЕНО на засіданні кафедри програмного забезпечення протокол № від 2007 р. Львів – 2007 Методичні вказівки до лабораторних роботи з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки" Укладач: [ім’я автора приховано] [ім’я автора приховано] Відповідальний за випуск: Рецензенти: Тема роботи: Ознайомлення із методами сортування. Алгоритм вибірки. Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування вибірки. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу вибірки. 1. ТЕОРЕТИЧНІ ВІДОМОСТІ Будуватимемо готову послідовність, починаючи з лівого кінця масиву. Алгоритм складається з n послідовних кроків, починаючи від нульового і закінчуючи (n-1) -м. На i-м кроці вибираємо найменший з елементів а[i]... а[n] і міняємо його місцями з а[i]. Послідовність кроків при n=5 зображена на малюнку нижче.
Незалежно від номера поточного кроку i, послідовність а[0]...a[i] (виділена курсивом) є впорядкованою. Таким чином, на (n-1) -му кроці вся послідовність, окрім а[n] виявляється відсортованою, а а[n] стоїть на останньому місці по праву: всі менші елементи вже пішли вліво. template<class T> void selectSort(T a[], long size){ long i, j, k; T x; for( i=0; i < size-1; i++){ // i - номер поточного кроку k=i; x=a[i]; for( j=i+1; j < size; j++) // цикл вибору найменшого елементу if ( а[j]< x ) { k=j; x=a[j]; // k - індекс найменшого елементу } а[k]= а[i]; а[i]= x; // міняємо місцями найменший з а[i] } } aбо, for(i=0;i<size-1;i++) { min = i; for(j=i+1;j<size;j++) { if(a[j] < a[min]) min = j; } tmp = a[i]; a[i] = a[min]; a[min] = tmp; } Для знаходження найменшого елементу з n+1 розглянутий алгоритм здійснює n порівнянь. З урахуванням того, що кількість елементів, що розглядаються на черговому кроці, зменшується на одиницю, загальну кількість операцій: n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2). Таким чином, оскільки число обмінів завжди буде менше числа порівнянь, час сортування росте квадратично щодо кількості елементів. Алгоритм не використовує додаткової пам'яті: всі операції відбуваються "на місці". 2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм вибірки. Використовувати мову програмування C/C++. Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи. 3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ Отримати індивідуальне завдання у викладача; Уточнити завдання(можливі різні трактування завдання); Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу(алгоритму) на даній лабораторній роботі; Протестувати на наявність логічних помилок програми; Оформити звіт відповідно до стандарту; Захистити виконану роботу. 4. КОНТРОЛЬНІ ПИТАННЯ Які ви знаєте методи сортування? Який метод сортування був розглянений на даній лабораторній роботі? Від чого прямо – залежним являється швидкість сортування? Опишіть характеристики даного методу. Порівняєте даний метод із іншими методами сортування вам відомими. Наскільки являється ефективним даний метод сортування? Чи використовують даний метод на практиці, і наскільки часто? Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах? Чим оригінальним виділяється даний метод від інших? 5. ІНДИВІДУАЛЬНЕ ЗАВДАНЯ