% CVICENI - 9
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rychle algoritmy, trideni, vyhledáváni (1)

N = 100;
% pole delky N, nahodnych, navzajem ruznych prvku
arr = randi([1, N], 1, N);

% Bubble Sort
tic;
sortedBubble = bubbleSort(arr, false);
timeBubble = toc;

% Selection Sort
% tic;
% sortedSelection = selectionSort(arr,false);
% timeSelection = toc;

% Merge Sort
tic;
sortedMerge = mergeSort(arr);
timeMerge = toc;

% Insertion Sort
tic;
sortedInsertion = insertionSort(arr, false);
timeInsertion = toc;

% Quick Sort
tic;
sortedQuick = quickSort(arr);
timeQuick = toc;

% Casy trideni jednotlivych algoritmu
disp(['Bubble Sort Time: ', num2str(timeBubble), ' seconds']);
% disp(['Selection Sort Time: ', num2str(timeSelection), ' seconds']);
disp(['Merge Sort Time: ', num2str(timeMerge), ' seconds']);
disp(['Insertion Sort Time: ', num2str(timeInsertion), ' seconds']);
disp(['Quick Sort Time: ', num2str(timeQuick), ' seconds']);


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   FUNKCE   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% BUBBLE SORT
function sortedArray = bubbleSort(arr, anim)
    % nejjednodussi (naivni) algoritmus
    % prohazujeme po dvojicich
    % napr. pro i=1 nam 'probubla' nejvetsi prvek
    % na konec pole
    % pro i=2: 2-nejvetsi, atd.
    % slozitost(worst-case):
    %   O(n^2) - porovnavani prvku,
    %   O(n^2) - prohazovani prvku

    n = length(arr);

    % ---------------------------------
    if anim == true % pro ucely animace
        figure;
        axis([1 n min(arr) max(arr)]);
    end
    % ---------------------------------

    for i = 1:n-1
        swapped = false;
        for j = 1:n-i
            if arr(j) > arr(j+1)
                temp = arr(j);
                arr(j) = arr(j+1);
                arr(j+1) = temp;
                % ---------------------------------
                if anim == true % pro ucely animace
                    plot(arr, 'ok','MarkerFaceColor', 'k', 'MarkerSize', 4);
                    title(['Bubble Sort - Iteration ', num2str(i)]);
                    xlabel('Index');
                    ylabel('Value');
                    drawnow;
                end
                % ---------------------------------
                swapped = true;
            end
        end
        % Pokud nebyly prohozeny zadne elemnty => 
        % pole je uz setridene = ukonci
        if ~swapped
            break;
        end
    end
    sortedArray = arr;
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% SELECTON SORT
%
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% INSERTION SORT
function sortedArray = insertionSort(arr, anim)
    n = length(arr);
    % ---------------------------------
    if anim == true % pro ucely animace
        figure;
        axis([1 n min(arr) max(arr)]);
    end
    % ---------------------------------
    for i = 2:n
        key = arr(i);
        j = i - 1;
        while j > 0 && arr(j) > key
            arr(j+1) = arr(j);
            j = j - 1;
        end
        arr(j+1) = key;
        % ---------------------------------
        if anim == true % pro ucely animace
            plot(arr, 'ok','MarkerFaceColor', 'k', 'MarkerSize', 4);
            title(['Selection Sort - Iteration ', num2str(i)]);
            xlabel('Index');
            ylabel('Value');
            drawnow;
        end
        % ---------------------------------
    end
    sortedArray = arr;
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MERGE SORT
function sortedArray = mergeSort(arr)
    n = length(arr);
    if n <= 1
        sortedArray = arr;
        return
    end
    mid = floor(n / 2);
    left = mergeSort(arr(1:mid));
    right = mergeSort(arr(mid+1:n));
    sortedArray = merge(left, right);
end

function mergedArray = merge(left, right)
    mergedArray = [];
    while ~isempty(left) && ~isempty(right)
        if left(1) <= right(1)
            mergedArray = [mergedArray, left(1)];
            left(1) = [];
        else
            mergedArray = [mergedArray, right(1)];
            right(1) = [];
        end
    end
    mergedArray = [mergedArray, left, right];
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% QUICK SORT
function sortedArray = quickSort(arr)
    n = length(arr);
    if n <= 1
        sortedArray = arr;
        return
    end
    pivot = arr(end);
    left = [];
    right = [];
    for i = 1:n-1
        if arr(i) <= pivot
            left = [left, arr(i)];
        else
            right = [right, arr(i)];
        end
    end
    sortedArray = [quickSort(left), pivot, quickSort(right)];
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% IS SORTED ASCENDING
function isSorted = isSortedAscending(arr)
    n = length(arr);
    isSorted = true;
    for i = 1:n-1
        if arr(i) > arr(i+1)
            isSorted = false;
            break;
        end
    end
end
