сок розділиться на дві частини: ліву - з ключами, меншими х і праву - з ключами, великими х. Цей крок називається поділом. Х - центром. p align="justify"> До отримає частину рекурсивно застосовуємо ту ж процедуру. У результаті виходить дуже ефективна сортування. Середній швидкодію O (n * log (n)), але можливий випадок таких вхідних даних, на яких алгоритм буде працювати за O (n 2 ) операцій. Hа випадкових вхідних даних ймовірність такого надзвичайно мала.
Опис програми
Опис предикатів, використовуваних у програмі
Розглянемо тільки основні предикати, що реалізують зазначені в завданні дії.
Список всіх предикатів:
cmp (STRING, SLIST, SLIST, SLIST)% сортування (для порівняння елементів)
del (SYMBOL, S, S)% видалення елемента перед вказаним (SYMBOL)% перевірка введення користувача
tolist (S, INTEGER, WINDOW)% запис елементів в список (S, WINDOW)% запис елементів в лист (SYMBOL, S, S)% видалення конкретного елемента (SYMBOL, S)% пошук елемента у списку (S)% перевірка на наявність елементів у списку (SLIST, SLIST)% швидке сортування (SLIST, SLIST, SLIST)% допоміжний предикат для сортування (SYMBOL, S)% перевірка на видалення перед першим ел-му.
Основні предикати:
del (SYMBOL, S, S)% видалення елемента перед вказаним
В· 1-й аргумент - елемент, перед яким потрібно видалити інший елемент;
В· 2-й аргумент - вхідний список елементів;
В· 3-й аргумент - результуючий список елементів.
Дане правило використовує висхідну рекурсію для видалення елементів зі списку (2-й аргумент) і переміщення результату видалення елементів зі списку в результуючий список (3-й аргумент).
sort (SLIST, SLIST)% предикат швидкого сортування
В· 1-й аргумент - список рядків, який потрібно відсортувати;
В· 2-й аргумент - відсортований список рядків (результат).
Дане правило використовує висхідну рекурсію для сортування списку (1-й аргумент) і переміщення відсортованого списку в результуючий список (2-й аргумент).
Для кожного з розглянутих предикатів текст відповідних правил представлений у розділі "Текст програми".
Текст програми
= SYMBOL *% предікати_dialog_eh: EHANDLER% ідентифікатор вікна (STRING, SLIST, SLIST, SLIST)% сортування (SYMBOL)% перевірка введення користувача (S, INTEGER, WINDOW)% ЗАПБТ елементів у список
