Головна

алгоритми сортування

  1.  Алгоритми Clarans, CURE, DBScan
  2.  Алгоритми вибору для кільцевих архітектур
  3.  Алгоритми виділення ділянок пам'яті за запитом
  4.  Алгоритми генераторів псевдовипадкових чисел
  5.  Алгоритми генерування деяких випадкових величин найбільш часто використовуваних розподілів.
  6.  Алгоритми діагностування.
  7.  Алгоритми заміщення сторінок

Всі алгоритми сортування можна поділити на дві групи: сортування порівняннями і лексикографічна сортування. Ці два види алгоритмів відрізняються тим, що при сортуванні порівняннями невідома внутрішня структура об'єктів. При цьому вони взагалі можуть мати різну структуру, необхідно тільки вміти порівнювати об'єкти один з одним (наприклад, числа). Насправді тільки одного порівняння об'єктів недостатньо, він повинен мати ще деякими додатковими властивостями, наприклад транзитивності, тобто якщо a<b и b<c, То має бути a<c. Припустимо, що ми повинні порівнювати вектора фактично є парами чисел виду r= (x,y). Визначимо операцію порівняння двох об'єктів r1= (x1,y1) і r2= (x2,y2) Так: r1<r2 тоді і тільки тоді, коли x1<x2 або y1<y2. Чи задовольняє таке порівняння вищенаведеного умові? Візьмемо 3 вектора: a= (3,9), b= (4,7), c= (1,8). За описаним способом порівняння отримуємо: a<b, b<c, але a не менше c. Таким чином, при виборі цього відносини порядку не в кожному випадку можна впорядкувати задану послідовність елементів.

Лексикографічна сортування зазвичай застосовується при сортуванні об'єктів з відомою внутрішньою структурою. Наприклад, упорядкування текстових рядків за алфавітом. Внутрішня структура рядків відома: рядок складається з символів; кількість символів алфавіту обмежена.

 




 лекція 4 |  Строковий тип |  Процедури і функції |  Процедури і функції. Процедурні типи. Тип покажчик |  Локальність і область дії |  процедурні типи |  Тип покажчик |  нульовий покажчик |  Процедури і функції для роботи з текстовими файлами |  Стандартні текстові файли |

© um.co.ua - учбові матеріали та реферати