Попередня сторінка          Зміст           Наступна сторінка          Електронні посібники ВНТУ

 

ЛАБОРАТОРНА РОБОТА № 10

СОРТУВАННЯ І ПОШУК

 

Мета роботи

• Отримання практичних навичок в обробці масивів, у сортуванні елементів масивів різними методами та за різними реквізитами.
• Дослідження і вивчення методів пошуку ключових елементів у масивах.
• Здійснення порівняння та аналізу ефективності використовуваних методів сортування і пошуку.

 

 

        

       ТЕОРЕТИЧНІ ВІДОМОСТІ

 

Бульбашкове  сортування (сортування обміном)

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

   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);

Сортування методом вибору

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

     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;
        }

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

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

     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;
        }

Швидке сортування

Швидке сортування полягає в тому, що множина елементів В {k₁, …, k_n} перетворюється на множину B₁, {k₁}, B₂, де В₁ – підмножина В з елемен­та­ми, не більшими за k₁, а В₂ – підмножина В з елементами біль­шими k₁. При­чому k₁ після розбиття множини В буде перебувати на потріб­ному місці. Да­лі до множин B₁ і B₂ знову застосовують впорядкування швидким сорту­ванням. На практиці цей алгоритм виявляється одним із найшвидших.

     double * quick(double *s,int low,int hi)
       { double cnt,aux;
         int i,j;
         if (hi>low)
         { nbsp; 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);
     }

Сортування методом Шелла

Головний недолік простих методів – обмін ведеться в основному між сусідними елементами. Тому бажано робити якомога ширші обміни.

Метод Шелла – метод сортування включеннями з відстанями, що змен­шуються. Візьмемо для прикладу масив:

На першому етапі масив уявно ділиться на підмасиви з елементами, що, скажімо, відстоять один від одного на 4 елементи:

Кожен з них впорядковується окремо:

Сортування робиться у кожному підмасиві методом простого вклю­чення. На другому етапі підмасиви утворюються елементами через один:

Одержуємо:

Після цього весь масив сортується разом. За рахунок попередніх етапів він виявляється вже близьким до відсортованого, тому обмінів необхідно вже не так багато. Цей метод дає кращі результати, якщо розподіл на підмасиви роблять кроками, що не є степенями двійки, а, навпаки, не є множниками один одного.

Лінійний пошук

Лінійний пошук порівнює кожен елемент масиву з ключем пошуку. Оскільки масив не впорядкований, цілком імовірно, що відшукують зна­чення виявиться першим елементом масиву. Але в середньому програма повинна порівняти з ключем пошуку половину елементів масиву.

Метод лінійного пошуку добре працює для невеликих або для несор­то­ваних масивів. І хоча для великих масивів лінійний пошук неефектив­ний, він абсолютно надійний.

Двійковий пошук

Двійковий (бінарний) пошук – алгоритм пошуку елемента у відсорто­ва­ному масиві. Бінарний пошук знайшов собі застосування в математиці і інформатиці. Двійковий пошук можна використовувати тільки в тому ви­пад­ку, якщо є масив, всі елементи якого впорядковані (відсортовані).

Нехай x – елемент, пошук якого здійснюється; l (left) – ліва границя пошуку; r (right) – права границя пошуку.

 

Порядок виконання роботи

 

1. Засвоїти теоретичний матеріал. Розібратись у сутності кожного методу сортування та пошуку.
2. Розробити програму згідно індивідуального завдання. Для сортування і пошуку повинні бути розроблені окремі функції.
3. Підготувати звіт:
•  варіант і текст завдання;
•  схеми роботи функцій сортування і пошуку;
•  лістинг програми;
•  результати виконання і аналізу сортування (вигляди екрану, таблиця і графік);
•  висновки.

 

Варіанти індивідуальних завдань

 

1. Сгенерувати масив (масив оголошувати динамічно) і вивести його на екран (використати при цьому власну функцію для виведення масиву на екран).
2. Відсортувати масив, обравши вказані методи та параметри сор­тування.
3. Запускаючи програму не менше десяти разів для кожного методу (або передбачити це у програмі), задавати різну кількість n елементів маси­ву, отримати час t сор­ту­ван­ня. Побудувати залежність t=f(n)  на одному графіку для різних методів сортування (у табличному і графічному виглядах). 
4. Здійснити пошук вказаного (з клавіатури) елемента у масиві, вико­рис­товуючи вказаний метод пошуку).

 

Контрольні питання

 

1. Які групи методів сортування ви знаєте? В чому їхсутність?
2. Поясніть алгоритм методу сортування бульбашками.
3. Наведіть приклад приклад фрагмента коду, що здійснює сортування символів бульбашками у порядку зростання (починати сортування з першого елементу).
4. Наведіть схему роботи функції для реалізації бульбашкового сортування (сортування починати з кінця).
5. Поясніть алгоритм методу сортування вставками.
6. Наведіть схему роботи функції для реалізації сортування вставками (сортування починати з початку).
7. Наведіть приклад приклад фрагмента коду, що здійснює сортування цілих чисел вставками у порядку убування (починати сортування з першого елементу).
8. Поясніть алгоритм методу сортування вибором.
9. Наведіть схему роботи функції для реалізації сортування вибором (сортування починати з початку).
10. Наведіть приклад приклад фрагмента коду, що здійснює сортування дійсних чисел вибором у порядку убування (починати сортування з кінця).
11. Наведіть схему роботи функції для реалізації бульбашкового сорту­вання.
12. Як оцінюються методи сортування?
13. Які удосконалення методів сортування ви знаєте?
14. В чому сутність шейкерного сортування? Наведіть приклад.
15. В чому сутність методу швидкого сортування? Його переваги.
16. Наведіть алгоритм методу Шелла для сортування? Його переваги.