:- initialization(main).
main :- write('Hello, World!').


%BUBBLE SORT START%
% Predicate to swap the first two elements of the list if they are in descending order
swap([X, Y|T], [Y, X | T]):-
    Y =< X. % Check if Y is less than or equal to X, indicating a swap is needed

% Recursive predicate to swap elements in the tail of the list
swap([H|T], [H|T1]):-
    swap(T, T1). % Recursively swap elements in the tail

% Bubble sort algorithm starts here.
% Predicate for bubble sort algorithm.
% bubbleSort/2 sorts a given list using the bubble sort algorithm.
% It repeatedly calls swap/2 predicate to perform swaps until the list is sorted.
% The cut operator (!) is used to ensure that only one swap is performed in each iteration.
bubbleSort(L, SL):-
    swap(L, L1), % Call swap/2 predicate to swap elements in the list
    !, % Cut operator to prevent backtracking and ensure only one swap is performed
    bubbleSort(L1, SL). % Recursively call bubbleSort with the updated list

% Base case: when no more swaps are needed, return the sorted list
bubbleSort(L, L). % Bubble sort algorithm ends here.
%BUBBLE SORT END%


%INSERTION SORT START%
% Predicate to check if a list is ordered
ordered([]).
ordered([_X]).
ordered([H1, H2|T]):-
    H1 =< H2,
    ordered([H2|T]).

% Predicate to insert an element into a sorted list
insert(X, [], [X]). % Base case: if the list is empty, X is the only element, forming a new list.
insert(E, [H|T], [E,H|T]):- % Insert E before H if the list is ordered and E is less than or equal to H.
    ordered(T),
    E =< H,
    !.
insert(E, [H|T], [H|T1]):- % Recursively insert E into the sorted tail of the list.
    ordered(T),
    insert(E, T, T1).

% insertionSort/2 sorts a given list using insertion sort algorithm.
insertionSort([], []). % Base case: an empty list is already sorted.
insertionSort([H|T], SORTED) :-
    insertionSort(T, T1), % Recursively sort the tail of the list.
    insert(H, T1, SORTED). % Insert the head element into the sorted tail to get the final sorted list.
%INSERTION SORT END%

%MERGE SORT BEGINS%
% mergeSort/2 sorts a given list using the merge sort algorithm.
mergeSort([], []). % Base case: The empty list is already sorted
mergeSort([X], [X]):-!. % Base case: A single-element list is already sorted

% split_in_half/3 splits a list into two halves.
intDiv(N, N1, R):- R is div(N, N1).
split_in_half([], [], []):-!, fail. % Base case: An empty list cannot be split
split_in_half([X], [X], []). % Base case: A single-element list is split into itself and an empty list
split_in_half(L, L1, L2):-
    length(L, N),
    intDiv(N, 2, N1),
    length(L1, N1),
    append(L1, L2, L). % Append the first N1 elements to L1 and the rest to L2

% merge/3 merges two sorted lists into a single sorted list.
merge([], L, L). % Base case: If the first list is empty, the merged list is the second list
merge(L, [], L). % Base case: If the second list is empty, the merged list is the first list
merge([H1|T1], [H2|T2], [H1|T]):-
    H1 < H2,
    merge(T1, [H2|T2], T). % If H1 is smaller, merge the remaining elements of the first list
merge([H1|T1], [H2|T2], [H2|T]):-
    H2 =< H1,
    merge([H1|T1], T2, T). % If H2 is smaller or equal, merge the remaining elements of the second list

%MERGE SORT ENDS%

%QUICK SORT BEGINS%
% Predicate to split a list into elements smaller or equal to X (SMALL) and elements greater than X (BIG)
split(_, [], [], []). % Base case: an empty list results in empty SMALL and BIG lists
split(X, [H|T], [H|SMALL], BIG):- % If H is smaller or equal to X, add it to SMALL and recurse with the rest of the list
    H =< X,
    split(X, T, SMALL, BIG).
split(X, [H|T], SMALL, [H|BIG]):- % If H is greater than X, add it to BIG and recurse with the rest of the list
    X =< H,
    split(X, T, SMALL, BIG).

/* Comment describing quickSort */
% Predicate to perform quicksort on a list
% quickSort(List, SortedList)
quickSort([], []). % Base case: an empty list is already sorted
quickSort([H|T], LS):- % Sort the list by partitioning it into SMALL and BIG, then recursively sorting and concatenating the results
    split(H, T, SMALL, BIG),
    quickSort(SMALL, S),
    quickSort(BIG, B),
    append(S, [H|B], LS).
%QUICK SORT ENDS%


%HYBRID SORT STARTS%
% Predicate to perform hybrid sort on a list based on the specified sorting algorithms and threshold
hybridSort(LIST, SMALL, _, THRESHOLD, SLIST):-
    length(LIST, N),
    N =< THRESHOLD, % If the list length is less than or equal to the threshold, use the specified SMALL sorting algorithm
    call(SMALL, LIST, SLIST).

% Hybrid sort using merge sort with a threshold for switching to insertion sort
hybridSort(LIST, SMALL, mergeSort, THRESHOLD, SLIST):-
    length(LIST, N),
    N > THRESHOLD, % If the list length is greater than the threshold, use merge sort
    split_in_half(LIST, L1, L2),
    hybridSort(L1, SMALL, mergeSort, THRESHOLD, S1),
    hybridSort(L2, SMALL, mergeSort, THRESHOLD, S2),
    merge(S1, S2, SLIST).

% Hybrid sort using quicksort with a threshold for switching to insertion sort
hybridSort([H|T], SMALL, quickSort, THRESHOLD, SLIST):-
    length([H|T], N),
    N > THRESHOLD, % If the list length is greater than the threshold, use quicksort
    split(H, T, L1, L2),
    hybridSort(L1, SMALL, quickSort, THRESHOLD, S1),
    hybridSort(L2, SMALL, quickSort, THRESHOLD, S2),
    append(S1, [H|S2], SLIST).

% Hybrid sort using quicksort with a threshold for switching to insertion sort (for single-element list)
hybridSort([H|T], SMALL, quickSort, THRESHOLD, SLIST):-
    length([H|T], N),
    N =< THRESHOLD, % If the list length is less than or equal to the threshold, use the specified SMALL sorting algorithm
    call(SMALL, [H|T], SLIST).
%HYBRID SORT ENDS%



:- dynamic randomList/1.
:- discontiguous measure_time/1.

randomList(N, LIST) :-
    randomListHelper(N, [], LIST).

randomListHelper(0, Acc, Acc) :- !.
randomListHelper(N, Acc, LIST) :-
    random(1, 100, RandomNumber),
    N1 is N - 1,
    randomListHelper(N1, [RandomNumber|Acc], LIST).

saveRandomList(N) :-
    randomList(N, RandomList),
    assertz(RandomList).

measure_time(Goal) :-
    statistics(walltime, [Start,_]),
    call(Goal),
    statistics(walltime, [End,_]),
    Time is End - Start,
    format('Execution time: ~3f seconds.~n', [Time]).