Sorting algorithms visualized | Source

Sorting algorithms visualized_[source]

xml
<glacius:metadata>
    <title>Sorting algorithms visualized</title>
    <description>JavaScript animations of various sorting algorithms</description>
    <category>Programming</category>
    <category>JavaScript</category>
    <category>Algorithms</category>
</glacius:metadata>
<style>
    .sortable-container {
        position: relative;
        border: 1px solid rgba(255, 255, 255, 0.25);
        height: 300px;
        background-color: rgba(0, 0, 0, 0.2);
        max-width: 650px;
        border-radius: 2px;
        margin: 0 auto 1.25rem auto;
        box-shadow: 2px 2px 2px rgba(0, 0, 0, 0.5);
    }
    .sortable-item {
        transition: left 250ms ease-in-out;
        position: absolute;
        width: 20px;
        display: flex;
        flex-direction: column;
    }
    .sortable-bar {
        border: 1px solid rgba(255, 255, 255, 0.35);
        background-color: rgba(0, 0, 0, 0.25);
        flex: 1;
    }
    .sortable-label {
        text-align: center;
        font-size: 12px;
        font-weight: bold;
        font-family: monospace;
    }
</style>
<div class="sortable-container"></div>
<div style="display: flex; justify-content: center; gap: .625rem;">
    <select class="form-control sort-algo" style="width: auto">
        <option value="bubbleSort">Bubble sort</option>
        <option value="mergeSort">Merge sort</option>
        <option value="insertionSort">Insertion sort</option>
        <option value="quickSort">Quick sort</option>
        <option value="selectionSort">Selection sort</option>
    </select>
    <button class="btn btn-primary start-random">Sort random</button>
    <button class="btn btn-primary start-reversed">Sort reversed</button>
</div>
<script>
//<![CDATA[
    (() => {
    const runSort = async (unsortedValues, onStep, sort) => {
        const sortables = unsortedValues.map((value, i) => { return {value, index: i} });
        let prev = null;
        const step = async () => {
            const sortedByIndex = sortables.concat([])
                .sort((a, b) => a.index === b.index ? 0 : (a.index < b.index ? -1 : 1));
            const hash = sortedByIndex.map(s => s.value).join(',');
            if (prev === hash) {
                return;
            }
            prev = hash;
            return await onStep(sortedByIndex);
        };
        await sort(sortables, step);
        return sortables;
    };
    const swap = (list, i, j) => {
        const temp = list[i];
        const oldIndex = temp.index;
        list[i].index = list[j].index;
        list[j].index = oldIndex;
        list[i] = list[j];
        list[j] = temp;
    };
    window.mergeSort = async (unsortedValues, onStep) => {
        const merge = async (left, right, step, offset, fullList) => {
            const sorted = [];
            const push = (list) => {
                const item = list.shift();
                sorted.push(item);
                const oldIndex = item.index;
                item.index = offset + sorted.length - 1;
                if (item.index > oldIndex) {
                    fullList.filter(x => x !== item && x.index > oldIndex && x.index <= item.index)
                        .forEach(item => item.index--);
                } else if (item.index < oldIndex) {
                    fullList.filter(x => x !== item && x.index < oldIndex && x.index >= item.index)
                        .forEach(item => item.index++);
                }
            }
            while (left.length && right.length) {
                push(left[0].value <= right[0].value ? left : right);
                await step();
            }
            while (left.length) {
                push(left);
                await step();
            }
            while (right.length) {
                push(right);
                await step();
            }
            await step();
            return sorted;
        };
        const mergeSort = async (list, step, fullList = null, offset = 0) => {
            if (list.length <= 1) {
                return list;
            }
            await step();
            fullList = fullList || list;
            const mid = Math.floor(list.length / 2);
            const left = await mergeSort(list.slice(0, mid), step, fullList, offset);
            const right = await mergeSort(list.slice(mid), step, fullList, offset + mid);
            return await merge(left, right, step, offset, fullList);
        };
        return runSort(unsortedValues, onStep, mergeSort);
    };
    window.insertionSort = async (unsortedValues, onStep) => {
        const insertionSort = async (list, step) => {
            for (let i = 1; i < list.length; i++) {
                let j = i;
                while (j > 0 && list[j - 1].value > list[j].value) {
                    const temp = list[j];
                    list[j].index = j - 1;
                    list[j - 1].index = j;
                    list[j] = list[j - 1];
                    list[j - 1] = temp;
                    j--;
                    await step();
                }
            }
            return list;
        };
        return runSort(unsortedValues, onStep, insertionSort);
    };
    window.bubbleSort = async (unsortedValues, onStep) => {
        const bubbleSort = async (list, step) => {
            let swapped;
            do {
                swapped = false;
                for (let i = 1; i < list.length; i++) {
                    if (list[i - 1].value > list[i].value) {
                        const temp = list[i];
                        list[i].index = i - 1;
                        list[i - 1].index = i;
                        list[i] = list[i - 1];
                        list[i - 1] = temp;
                        swapped = true;
                        await step();
                    }
                }
            } while (swapped);
        };
        return runSort(unsortedValues, onStep, bubbleSort);
    };
    window.quickSort = async (unsortedValues, onStep) => {
        const quickSort = async (list, step) => {
            const partition = async (list, lo, hi) => {
                const pivot = list[hi];
                let i = lo - 1;
                for (let j = lo; j <= hi - 1; j++) {
                    if (list[j].value <= pivot.value) {
                        i++;
                        swap(list, i, j);
                        await step();
                    }
                }
                i++;
                swap(list, i, hi);
                await step();
                return i;
            };
            const sort = async (list, lo, hi) => {
                if (lo >= hi || lo < 0) {
                    return;
                }
                await step();
                const pivot = await partition(list, lo, hi);
                await sort(list, lo, pivot - 1);
                await sort(list, pivot + 1, hi);
            };
            return sort(list, 0, list.length - 1);
        };
        return runSort(unsortedValues, onStep, quickSort);
    };
    window.selectionSort = async (unsortedValues, onStep) => {
        const selectionSort = async (list, step) => {
            await step();
            for (let i = 0; i < list.length - 1; i++) {
                let minIndex = i;
                for (let j = i + 1; j < list.length; j++) {
                    if (list[j].value < list[minIndex].value) {
                        minIndex = j;
                    }
                }
                if (minIndex !== i) {
                    // swap
                    swap(list, i, minIndex);
                    await step();
                }
            }
        };
        return runSort(unsortedValues, onStep, selectionSort);
    };
})();
//]]>
</script>
<script>
//<![CDATA[
    (() => {
        const startRandom = document.querySelector('.start-random');
        const startReversed = document.querySelector('.start-reversed');
        const sortableContainer = document.querySelector('.sortable-container');
        const algoSelector = document.querySelector('.sort-algo');
        const wait = ms => new Promise(resolve => setTimeout(resolve, ms));
        const containerHeight = sortableContainer.clientHeight;
        const doSort = (values) => {
            startRandom.disabled = true;
            startReversed.disabled = true;
            const sortableMap = new Map();
            const containerWidth = sortableContainer.clientWidth;
            const containerPadding = containerWidth / 60;
            const itemGutter = containerWidth / 120;
            const itemOuterWidth = (containerWidth - (containerPadding * 2)) / values.length;
            const step = async (sortables) => {
                const first = sortables[0];
                if (!sortableMap.has(first)) {
                    let min = Infinity;
                    let max = -Infinity;
                    for (const sortable of sortables) {
                        const el = document.createElement('div');
                        el.className = 'sortable-item';
                        el.style.left = containerPadding + (sortable.index * itemOuterWidth) + 'px';
                        el.style.width = itemOuterWidth + 'px';
                        el.style.padding = `0 ${itemGutter}px`;
                        sortableContainer.appendChild(el);
                        const bar = document.createElement('div');
                        bar.className = 'sortable-bar';
                        const label = document.createElement('div');
                        label.className = 'sortable-label';
                        label.appendChild(document.createTextNode(sortable.value.toString()));
                        el.appendChild(bar);
                        el.appendChild(label);
                        min = Math.min(min, sortable.value);
                        max = Math.max(max, sortable.value);
                        sortableMap.set(sortable, el);
                    }
                    for (const sortable of sortables) {
                        const range = Math.abs(max - min);
                        const pctOfRange = (sortable.value - min) / range;
                        const minItemHeight = 40;
                        const maxHeight = containerHeight - (containerPadding * 2) - minItemHeight;
                        const height = (pctOfRange * maxHeight) + minItemHeight;
                        const el = sortableMap.get(sortable);
                        el.style.height = height + 'px';
                        el.style.bottom = containerPadding + 'px';
                    }
                } else {
                    for (const sortable of sortables) {
                        const el = sortableMap.get(sortable);
                        el.style.left = containerPadding + (sortable.index * itemOuterWidth) + 'px';
                    }
                }
                await wait(250);
            };
            sortableContainer.innerHTML = '';
            const sortAlgoFn = window[algoSelector.value];
            if (typeof(sortAlgoFn) !== 'function') {
                throw new Error('unknown sort algo');
            }
            sortAlgoFn(values, step)
                .catch((err) => {
                    console.error(err);
                })
                .finally(() => {
                    startRandom.disabled = false;
                    startReversed.disabled = false;
                });
        };
        const shuffle = (arr) => {
            const remaining = arr.concat([]);
            let count = 0;
            while (remaining.length) {
                const index = Math.floor(Math.random() * remaining.length);
                const item = remaining[index];
                remaining.splice(index, 1);
                arr[count] = item;
                count++;
            }
            return arr;
        };
        const defaultValues = [];
        for (let i = 1; i <= 20; i++) {
            defaultValues.push(i);
        }
        startRandom.addEventListener('click', () => doSort(shuffle(defaultValues.concat([]))));
        startReversed.addEventListener('click', () => doSort(defaultValues.concat([]).reverse()));
    })();
//]]>
</script>

	<glacius:metadata>
	<title>Sorting algorithms visualized</title>
	<description>JavaScript animations of various sorting algorithms</description>
	<category>Programming</category>
	<category>JavaScript</category>
	<category>Algorithms</category>
	</glacius:metadata>

	<style>
	.sortable-container {
	position: relative;
	border: 1px solid rgba(255, 255, 255, 0.25);
	height: 300px;
	background-color: rgba(0, 0, 0, 0.2);
	max-width: 650px;
	border-radius: 2px;
	margin: 0 auto 1.25rem auto;
	box-shadow: 2px 2px 2px rgba(0, 0, 0, 0.5);
	}

	.sortable-item {
	transition: left 250ms ease-in-out;
	position: absolute;
	width: 20px;
	display: flex;
	flex-direction: column;
	}

	.sortable-bar {
	border: 1px solid rgba(255, 255, 255, 0.35);
	background-color: rgba(0, 0, 0, 0.25);
	flex: 1;
	}

	.sortable-label {
	text-align: center;
	font-size: 12px;
	font-weight: bold;
	font-family: monospace;
	}
	</style>

	<div class="sortable-container"></div>

	<div style="display: flex; justify-content: center; gap: .625rem;">
	<select class="form-control sort-algo" style="width: auto">
	<option value="bubbleSort">Bubble sort</option>
	<option value="mergeSort">Merge sort</option>
	<option value="insertionSort">Insertion sort</option>
	<option value="quickSort">Quick sort</option>
	<option value="selectionSort">Selection sort</option>
	</select>
	<button class="btn btn-primary start-random">Sort random</button>
	<button class="btn btn-primary start-reversed">Sort reversed</button>
	</div>

	<script>
	//<![CDATA[
	(() => {
	const runSort = async (unsortedValues, onStep, sort) => {
	const sortables = unsortedValues.map((value, i) => { return {value, index: i} });
	let prev = null;

	const step = async () => {
	const sortedByIndex = sortables.concat([])
	.sort((a, b) => a.index === b.index ? 0 : (a.index < b.index ? -1 : 1));
	const hash = sortedByIndex.map(s => s.value).join(',');
	if (prev === hash) {
	return;
	}

	prev = hash;

	return await onStep(sortedByIndex);
	};

	await sort(sortables, step);
	return sortables;
	};

	const swap = (list, i, j) => {
	const temp = list[i];
	const oldIndex = temp.index;
	list[i].index = list[j].index;
	list[j].index = oldIndex;

	list[i] = list[j];
	list[j] = temp;
	};

	window.mergeSort = async (unsortedValues, onStep) => {
	const merge = async (left, right, step, offset, fullList) => {
	const sorted = [];
	const push = (list) => {
	const item = list.shift();
	sorted.push(item);
	const oldIndex = item.index;
	item.index = offset + sorted.length - 1;

	if (item.index > oldIndex) {
	fullList.filter(x => x !== item && x.index > oldIndex && x.index <= item.index)
	.forEach(item => item.index--);
	} else if (item.index < oldIndex) {
	fullList.filter(x => x !== item && x.index < oldIndex && x.index >= item.index)
	.forEach(item => item.index++);
	}
	}

	while (left.length && right.length) {
	push(left[0].value <= right[0].value ? left : right);
	await step();
	}

	while (left.length) {
	push(left);
	await step();
	}
	while (right.length) {
	push(right);
	await step();
	}

	await step();
	return sorted;
	};

	const mergeSort = async (list, step, fullList = null, offset = 0) => {
	if (list.length <= 1) {
	return list;
	}

	await step();

	fullList = fullList \|\| list;
	const mid = Math.floor(list.length / 2);

	const left = await mergeSort(list.slice(0, mid), step, fullList, offset);
	const right = await mergeSort(list.slice(mid), step, fullList, offset + mid);
	return await merge(left, right, step, offset, fullList);
	};

	return runSort(unsortedValues, onStep, mergeSort);
	};

	window.insertionSort = async (unsortedValues, onStep) => {
	const insertionSort = async (list, step) => {
	for (let i = 1; i < list.length; i++) {
	let j = i;
	while (j > 0 && list[j - 1].value > list[j].value) {
	const temp = list[j];
	list[j].index = j - 1;
	list[j - 1].index = j;

	list[j] = list[j - 1];
	list[j - 1] = temp;

	j--;
	await step();
	}
	}

	return list;
	};

	return runSort(unsortedValues, onStep, insertionSort);
	};

	window.bubbleSort = async (unsortedValues, onStep) => {
	const bubbleSort = async (list, step) => {
	let swapped;

	do {
	swapped = false;
	for (let i = 1; i < list.length; i++) {
	if (list[i - 1].value > list[i].value) {
	const temp = list[i];
	list[i].index = i - 1;
	list[i - 1].index = i;

	list[i] = list[i - 1];
	list[i - 1] = temp;

	swapped = true;
	await step();
	}
	}
	} while (swapped);
	};

	return runSort(unsortedValues, onStep, bubbleSort);
	};

	window.quickSort = async (unsortedValues, onStep) => {
	const quickSort = async (list, step) => {
	const partition = async (list, lo, hi) => {
	const pivot = list[hi];
	let i = lo - 1;

	for (let j = lo; j <= hi - 1; j++) {
	if (list[j].value <= pivot.value) {
	i++;

	swap(list, i, j);
	await step();
	}
	}

	i++;
	swap(list, i, hi);
	await step();

	return i;
	};

	const sort = async (list, lo, hi) => {
	if (lo >= hi \|\| lo < 0) {
	return;
	}

	await step();

	const pivot = await partition(list, lo, hi);
	await sort(list, lo, pivot - 1);
	await sort(list, pivot + 1, hi);
	};

	return sort(list, 0, list.length - 1);
	};

	return runSort(unsortedValues, onStep, quickSort);
	};

	window.selectionSort = async (unsortedValues, onStep) => {
	const selectionSort = async (list, step) => {
	await step();

	for (let i = 0; i < list.length - 1; i++) {
	let minIndex = i;
	for (let j = i + 1; j < list.length; j++) {
	if (list[j].value < list[minIndex].value) {
	minIndex = j;
	}
	}

	if (minIndex !== i) {
	// swap
	swap(list, i, minIndex);
	await step();
	}
	}
	};

	return runSort(unsortedValues, onStep, selectionSort);
	};
	})();
	//]]>
	</script>

	<script>
	//<![CDATA[
	(() => {
	const startRandom = document.querySelector('.start-random');
	const startReversed = document.querySelector('.start-reversed');
	const sortableContainer = document.querySelector('.sortable-container');
	const algoSelector = document.querySelector('.sort-algo');
	const wait = ms => new Promise(resolve => setTimeout(resolve, ms));

	const containerHeight = sortableContainer.clientHeight;

	const doSort = (values) => {
	startRandom.disabled = true;
	startReversed.disabled = true;

	const sortableMap = new Map();

	const containerWidth = sortableContainer.clientWidth;
	const containerPadding = containerWidth / 60;
	const itemGutter = containerWidth / 120;
	const itemOuterWidth = (containerWidth - (containerPadding * 2)) / values.length;

	const step = async (sortables) => {
	const first = sortables[0];
	if (!sortableMap.has(first)) {
	let min = Infinity;
	let max = -Infinity;
	for (const sortable of sortables) {
	const el = document.createElement('div');
	el.className = 'sortable-item';
	el.style.left = containerPadding + (sortable.index * itemOuterWidth) + 'px';
	el.style.width = itemOuterWidth + 'px';
	el.style.padding = `0 ${itemGutter}px`;
	sortableContainer.appendChild(el);

	const bar = document.createElement('div');
	bar.className = 'sortable-bar';

	const label = document.createElement('div');
	label.className = 'sortable-label';
	label.appendChild(document.createTextNode(sortable.value.toString()));

	el.appendChild(bar);
	el.appendChild(label);

	min = Math.min(min, sortable.value);
	max = Math.max(max, sortable.value);

	sortableMap.set(sortable, el);
	}

	for (const sortable of sortables) {
	const range = Math.abs(max - min);
	const pctOfRange = (sortable.value - min) / range;
	const minItemHeight = 40;
	const maxHeight = containerHeight - (containerPadding * 2) - minItemHeight;
	const height = (pctOfRange * maxHeight) + minItemHeight;

	const el = sortableMap.get(sortable);
	el.style.height = height + 'px';
	el.style.bottom = containerPadding + 'px';
	}
	} else {
	for (const sortable of sortables) {
	const el = sortableMap.get(sortable);
	el.style.left = containerPadding + (sortable.index * itemOuterWidth) + 'px';
	}
	}

	await wait(250);
	};

	sortableContainer.innerHTML = '';

	const sortAlgoFn = window[algoSelector.value];
	if (typeof(sortAlgoFn) !== 'function') {
	throw new Error('unknown sort algo');
	}

	sortAlgoFn(values, step)
	.catch((err) => {
	console.error(err);
	})
	.finally(() => {
	startRandom.disabled = false;
	startReversed.disabled = false;
	});
	};

	const shuffle = (arr) => {
	const remaining = arr.concat([]);
	let count = 0;
	while (remaining.length) {
	const index = Math.floor(Math.random() * remaining.length);
	const item = remaining[index];
	remaining.splice(index, 1);
	arr[count] = item;
	count++;
	}
	return arr;
	};

	const defaultValues = [];
	for (let i = 1; i <= 20; i++) {
	defaultValues.push(i);
	}

	startRandom.addEventListener('click', () => doSort(shuffle(defaultValues.concat([]))));
	startReversed.addEventListener('click', () => doSort(defaultValues.concat([]).reverse()));
	})();
	//]]>
	</script>

Sorting algorithms visualized[source]

Sorting algorithms visualized_[source]