Quicksort SWI-Prolog

[Katya]

Ребята, объясните пожалуйста программу Quicksort на SWI-Prolog, если можно построчно.  Заранее огромное спасибо. Вот код:


quicksort([],[]).   

quicksort([X|Tail], Sorted) :-         
   split(X, Tail, Small, Big),
    quicksort(Small, SortedSmall),
    quicksort(Big, SortedBig),
    append(SortedSmall, [X|SortedBig], Sorted).

split(X, [],[],[]).
split(X, [Y|Tail], [Y|Small], Big) :-
    X > Y,
    split(X, Tail, Small, Big).
split(X, [Y|Tail], Small, [Y|Big]) :-
    split(X, Tail, Small, Big).

[Finch]

С прологом я не знаком. Поэтому помочь не смогу. Но объяснить принцип алгоритма смогу.

1. Есть массив элементов в памяти.
2. Берется элемент из середины массива. Считаем что он средний элемент в массиве по своей значимости.
     Текушее местоположение данного элемента в бегунке Pos.
3. Есть два бегунка, которые выставляют на начало массива (Small) и на конец массива (Big).
4. Идем с начала массива и ишем элемент больший по значению, чем средний элемент. Если находится такой элемент. Меняем элементы местами ( [Small] <---> [Pos]; small <-----> Pos;) Данный пункт выполняется до первой переустановки или пока Small < Pos.
5. Идем с конца массива и ишем элемент меньший по значению, чем средний элемент. Если находится такой элемент. Меняем элементы местами ( [Pos] <---> [Big]; Pos <-----> Big;) Данный пункт выполняется до первой переустановки или пока Pos < Big.
6. Пока Small < Big перейти к пункту 4.
7. Получили, что средний элемент выставился на свое место в отсортированном массиве. Все элементы до позиции среднего элемента будут меньше среднего элемента. Все элементы которые стоят после позиции среднего элемента больше по значению.
9. Теперь надо отсортировать элементы до Pos и после Pos.
10. Берем массив от начала и до Pos. Элемент Pos не включается в данный массив. Если количество элементов в данном массиве больше двух, то выполнить программу рекурсивно начиная с пункта 1.
11. Берем массив от Pos и до конца массива. Элемент Pos не включается в данный массив. Если количество элементов в данном массиве больше двух, то выполнить программу рекурсивно начиная с пункта 1.
12. Конец.

Более подробное объяснение, с растановкой по всем полочкам можно получить в книге Д. Кнут "Исскуство программирования" Том 3.

[npak]

Katya,

неужели пока зачёт не грянул, вы не читали учебник по Prolog?  Возмите книгу Ивана Братко "Программирование на языке ПРОЛОГ для искусственного интеллекта" и прочтите главы 1 и 3.  Этого будет достаточно, чтобы понять программу quicksort.

C другой стороны, в упомянутых главах 60 страниц, "многа букоф, ниасилить", поэтому кратко объясню программу.  Но заранее предупреждаю, если с этим описанием вы пойдёте программу сдавать, без знания языка, то рискуете не ответить на элементарные дополнительные вопросы.

Сначала небольшое введение. Язык пролог описывает отношения между объектами.  В приведённой программе определяются два отношения - quicksort и split.  Отношение quicksort двухместное, split - четырёхместное.

quicksort(X, Y) даёт ответ yes, если список Y является результатом сортировки списка Y. Например, если в интерактивной сессии Prolog задать вопрос
?- quicksort([2,1], [1,2]).
то система ответит yes, а на вопрос
?- quicksort([2,1], [2,1]).
ответит no

Однако пролог может не только отвечать на вопросы "Объект Х находится в отношении quicksort с объектом Y", но и самостоятельно искать ответ на вопрос "Найди объект Y, который находится в отношении quicksort с объектом X".  Например, если задать вопрос
?- quicksort([2,1], Y).
то система ответит "Y = [1, 2]".  Как пролог-система ищет ответ - см. учебники.

Вернёмся к программе.
Предложение "quicksort([],[])." обозначает, что пустому списку соответствует пустой список".  Дальше определяется отношение quicksort для непустого списка на первом месте.
Предложение начинается с "quicksort([X|Tail], Sorted) :-", которое читается так: список Sorted quicksort-соответствует списку, у которого первый элемент X, а остальные элементы обозначаются как Tail, если
1.  Есть такие объекты Small и Big, которые находятся в отношении split с объектами X и Tail, и
2.  Есть такой объект SortedSmall, который находится в отношении quicksort с объектом Small, и
3.  Есть такой объект SortedBig, который находится в отношении quicksort с объектом Big, и
4.  Объект Sorted находится в отношении append с объектом SortedSmall и списком, полученным добавлением объекта X в голову объекта (из операции следует, что это список) SortedBig.

[npak]

Переведу это описание на русский язык.  Отношение quicksort(X, Y) можно читать так: "Y является результатом быстрой сортировки списка X".  Отношение split(X, Y, U, W) - "Х - объект, Y - список, тогда в списке U содержатся элементы из Y, которые меньше X, а в списке W все остальные".  Отношение append(X, Y, Z) - "X и Y - списки, тогда Z - список, полученный прикреплением списка Y к концу списка X".

Соотвественно, "quicksort([], [])." обозначает, что результат сортировки пустого списка - пустой список.
Если список не пуст, то обозначим первый элемент как X, все остальные как список Tail.  Тогда список Sorted является результатом сортировки, если он равен списку, полученному слиянием отсортированного списка элементов, меньших X, затем самого элемента X, и, наконец, отсортированного списка элементов, больших X.

Попробуйте самостоятельно разобрать отношение split по аналогии с quicksort.