const container = document.getElementById('container');
let arr = [];

function initializeBars() {
    container.innerHTML = '';
    for (let i = 0; i < 20; i++) {
        let value = Math.floor(Math.random() * 180) + 20;
        let bar = document.createElement('div');
        bar.className = 'bar';
        bar.style.height = `${value}px`;
        container.appendChild(bar);
        arr[i] = value;
    }
}

function setColor(index, color) {
    container.children[index].style.backgroundColor = color;
}

function swap(i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    container.children[i].style.height = `${arr[i]}px`;
    container.children[j].style.height = `${arr[j]}px`;
}

async function bubbleSort() {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            setColor(j, 'red');
            setColor(j + 1, 'red');
            await new Promise(r => setTimeout(r, 300));
            if (arr[j] > arr[j + 1]) {
                swap(j, j + 1);
            }
            setColor(j, 'lightblue');
            setColor(j + 1, 'lightblue');
        }
    }
}

async function selectionSort() {
    for (let i = 0; i < arr.length; i++) {
        let minIdx = i;
        for (let j = i + 1; j < arr.length; j++) {
            setColor(minIdx, 'red');
            setColor(j, 'red');
            await new Promise(r => setTimeout(r, 300));
            if (arr[j] < arr[minIdx]) {
                setColor(minIdx, 'lightblue');
                minIdx = j;
            } else {
                setColor(j, 'lightblue');
            }
        }
        if (minIdx !== i) {
            swap(i, minIdx);
        }
        setColor(minIdx, 'lightblue');
    }
}

async function insertionSort() {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        setColor(i, 'red');
        await new Promise(r => setTimeout(r, 300));
        while (j >= 0 && arr[j] > key) {
            setColor(j, 'red');
            arr[j + 1] = arr[j];
            container.children[j + 1].style.height = `${arr[j + 1]}px`;
            j = j - 1;
            await new Promise(r => setTimeout(r, 300));
            if (j + 1 !== i) {
                setColor(j + 1, 'lightblue');
            }
        }
        arr[j + 1] = key;
        container.children[j + 1].style.height = `${key}px`;
        setColor(i, 'lightblue');
    }
}

async function quickSort(arr, start, end) {
    if (start >= end) {
        return;
    }
    let index = await partition(arr, start, end);
    await Promise.all([
        quickSort(arr, start, index - 1),
        quickSort(arr, index + 1, end)
    ]);
}

async function partition(arr, start, end) {
    let pivotIndex = start;
    let pivotValue = arr[end];
    for (let i = start; i < end; i++) {
        setColor(i, 'red');
        await new Promise(r => setTimeout(r, 300));
        if (arr[i] < pivotValue) {
            swap(i, pivotIndex);
            setColor(pivotIndex, 'lightblue');
            pivotIndex++;
        } else {
            setColor(i, 'lightblue');
        }
    }
    swap(pivotIndex, end);
    for (let i = start; i <= end; i++) {
        if (i !== pivotIndex) {
            setColor(i, 'lightblue');
        }
    }
    return pivotIndex;
}

async function merge(arr, left, middle, right) {
    let n1 = middle - left + 1;
    let n2 = right - middle;

    let leftArray = new Array(n1);
    let rightArray = new Array(n2);

    for (let i = 0; i < n1; i++)
        leftArray[i] = arr[left + i];
    for (let j = 0; j < n2; j++)
        rightArray[j] = arr[middle + 1 + j];

    let i = 0;
    let j = 0;
    let k = left;

    while (i < n1 && j < n2) {
        setColor(k, 'red');
        await new Promise(r => setTimeout(r, 100));
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        container.children[k].style.height = `${arr[k]}px`;
        setColor(k, 'lightblue');
        k++;
    }

    while (i < n1) {
        arr[k] = leftArray[i];
        container.children[k].style.height = `${arr[k]}px`;
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArray[j];
        container.children[k].style.height = `${arr[k]}px`;
        j++;
        k++;
    }
}

async function mergeSort(arr, l, r) {
    if (l >= r) {
        return;
    }
    const m = l + Math.floor((r - l) / 2);
    await Promise.all([
        mergeSort(arr, l, m),
        mergeSort(arr, m + 1, r)
    ]);
    await merge(arr, l, m, r);
}

initializeBars();