Prolog insertion sort

11,741

I offer this simple solution:

Insert element in the sorted list

insert(X, [], [X]):- !.
insert(X, [X1|L1], [X, X1|L1]):- X=<X1, !.
insert(X, [X1|L1], [X1|L]):- insert(X, L1, L).

Use principe of insertion sort algorithm

insertionSort([], []):- !.
insertionSort([X|L], S):- insertionSort(L, S1), insert(X, S1, S).
Share:
11,741
Olga Dalton
Author by

Olga Dalton

Updated on June 04, 2022

Comments

  • Olga Dalton
    Olga Dalton over 1 year

    There is a simple Prolog insertion sort alghoritm:

    sorting([A|B], Sorted) :- sorting(B, SortedTail), insert(A, SortedTail, Sorted).
    sorting([], []).
    
    insert(A, [B|C], [B|D]) :- A @> B, !, insert(A, C, D).
    insert(A, C, [A|C]).
    

    It does well on normal lists:

    ?- sorting([5, 4, 9, 1, 3, 8], X).
    X = [1, 3, 4, 5, 8, 9].
    

    But I also need to sort sublist of list contains any of them:

    ?- sorting([2, 5, [5, 4, 3], [6, 3], 4, 8], X).
    X = [2, 4, 5, 8, [5, 4, 3], [6, 3]].
    

    Is what return now. And

    ?- sorting([2, 5, [5, 4, 3], [6, 3], 4, 8], X).
    X = [2, 4, 5, 8, [3, 4, 5], [3, 6]].
    

    what I need to return. So how can I sort sublist too? Thanks in advance!