Sort Array exercise

README.md

Sort Array

Due semplici esercizi di ordinamento degli elementi di un array. Scopo dell'esercizio è testare il codice realizzato

Step 1

Dato in input un array di numeri interi, restituire l'array ordinato in modo crescente

Step 2

Dati in input due array di numeri interi, restituire un singolo array ordinato in modo crescente che sia il merge tra i due array senza numeri ripetuti

index.js

/**
 * Receives two arrays as input and retuns an array which is the sorted merge of both without
 * duplicates
 * @author Tommaso Visconti <[email protected]>
 * @param {Array} a1 - The first array to sort and merge
 * @param {Array} a2 - The first array to sort and merge
 * @returns {Array} - The sorted array without duplicates
 */
const mergeAndSort = (a1, a2) => {
    const array = a1.concat(a2);
    const sortedArray = quickSort(array);
    const result = [];
    for (el of sortedArray) {
        if (result.length !== 0 && result[result.length - 1] === el) {
            continue;
        }
        result.push(el);
    }
    return result;
}

exports.mergeAndSort = mergeAndSort;

const sortArray = (array) => {
    for (e of array) {
        if (typeof(e) != "number") {
            throw "Can only sort number arrays"
        }
    }

    return quickSort(array);
}

exports.sortArray = sortArray;

/**
 * Sort an array of numbers using quicksort algorithm
 * @author Tommaso Visconti <[email protected]>
 * @param {Array} array - The array to sort
 * @returns {Array} - The sorted array
 */
const quickSort = (array) => {
    if (array.length <= 1) {
        return array
    }

    const [middle, lower, higher] = getPartitions(array);

    const sortedLower = quickSort(lower);
    const sortedHigher = quickSort(higher);

    return sortedLower.concat([middle], sortedHigher);
}

exports.quickSort = quickSort;

/**
 * Get partitions for the quicksort
 * @author Tommaso Visconti <[email protected]>
 * @param {Array} array - The array to partition
 * @returns {Array} - A 3-element array with [pivot value, array of elements lower than pivot,
 *                    array of elements higher than pivot]
 */
const getPartitions = (array) => {
    const lower = [];
    const higher = [];

    const pivot = getMiddleElement(array.length);

    for (let i = 0; i < array.length; i++) {
        if (i === pivot) {
            continue;
        }

        if (array[i] <= array[pivot]) {
            lower.push(array[i]);
        } else {
            higher.push(array[i]);
        }
    }

    return [array[pivot], lower, higher];
}

exports.getPartitions = getPartitions;

/**
 * Calculates the middle element of an array lenght. Note that the return value is an index so
 * it will begin from 0.
 * For event length the middle element is the floor value.
 * @author Tommaso Visconti <[email protected]>
 * @param {number} n - The length of the array
 * @returns {number} - The middle index of the array
 */
const getMiddleElement = (n) => {
    const isOdd = n % 2 === 1;

    let v;
    if (isOdd) {
        v = Math.ceil(n / 2) - 1;
    } else {
        v = Math.floor(n / 2) - 1;
    }

    return v < 0 ? 0 : v;
}

exports.getMiddleElement = getMiddleElement;

test_index.js

const { getMiddleElement, getPartitions, mergeAndSort, quickSort } = require('./index');
const { isEqual, printConsole } = require('./test_utils');

(() => {
    console.log("\nGet middle element");
    // Examples. The first element is the length of the array, the second is the middle index
    const tt = [[5, 2], [4, 1], [1, 0], [0, 0], [2, 0], [3, 1]];
    for (t of tt) {
        const r = getMiddleElement(t[0]);
        if (r !== t[1]) {
            throw `For ${t[0]} => Got ${r}, expected ${t[1]}`;
        }
        printConsole(".", "green");
    }
})();

(() => {
    console.log("\nQuicksort");
    const tt = [
        [[3,1,2],[1,2,3]],
        [[1,2],[1,2]],
        [[3,1,2],[1,2,3]],
        [[1],[1]],
        [[1,3,2,4],[1,2,3,4]],
        [[4,3,2,1],[1,2,3,4]],
        [[5,4,3,2,1],[1,2,3,4,5]],
        [[5,0,1,2,3],[0,1,2,3,5]],
        [[2,0,4,2,5,4],[0,2,2,4,4,5]],
    ];
    for (t of tt) {
        const r = quickSort(t[0]);
        if (!isEqual(r, t[1])) {
            throw `For ${t[0]} => Got ${r}, expected ${t[1]}`;
        }
        printConsole(".", "green");
    }
})();

(() => {
    console.log("\nGet partitions");
    // Examples. The first element is the length of the array, the second is the middle index
    const tt = [
        [
            [5,4,3,2,1],
            [3, [2,1], [5,4]]
        ],
        [
            [3,1,5,4],
            [1, [], [3,5,4]]
        ],
        [
            [1],
            [1, [], []]
        ],
    ];
    for (t of tt) {
        const r = getPartitions(t[0]);
        if (r[0] !== t[1][0]) {
            throw "Pivot element is wrong";
        }
        if (!isEqual(r[1], t[1][1])) {
            throw "Lower array is wrong"
        }
        if (!isEqual(r[2], t[1][2])) {
            throw "Higher array is wrong"
        }
        printConsole(".", "green");
    }
})();

(() => {
    console.log("\nMerge and sort");
    // Examples. The first element is the length of the array, the second is the middle index
    const tt = [
        [
            [3,1,4], [5,2],
            [1,2,3,4,5]
        ],
        [
            [3,1,4,2], [1,5,2],
            [1,2,3,4,5]
        ],
        [
            [1,1], [1,1,1],
            [1]
        ],
        [
            [4,2,9,1,2], [],
            [1,2,4,9]
        ],
    ];
    for (t of tt) {
        const r = mergeAndSort(t[0], t[1]);
        if (!isEqual(r, t[2])) {
            throw `Result is wrong: ${r}`;
        }
        printConsole(".", "green");
    }
})();

test_utils.js

const printConsole = (msg, color) => {
    if (color === "green") {
        console.log(`\x1b[32m${msg}\x1b[0m`);
    } else if (color === "red") {
        console.log(`\x1b[31m${msg}\x1b[0m`);
    } else {
        console.log(msg);
    }
}

exports.printConsole = printConsole;

const isEqual = function (value, other) {

	// Get the value type
	const type = Object.prototype.toString.call(value);

	// If the two objects are not the same type, return false
	if (type !== Object.prototype.toString.call(other)) return false;

	// If items are not an object or array, return false
	if (['[object Array]', '[object Object]'].indexOf(type) < 0) return false;

	// Compare the length of the length of the two items
	const valueLen = type === '[object Array]' ? value.length : Object.keys(value).length;
	const otherLen = type === '[object Array]' ? other.length : Object.keys(other).length;
	if (valueLen !== otherLen) return false;

	// Compare two items
	const compare = function (item1, item2) {

		// Get the object type
		const itemType = Object.prototype.toString.call(item1);

		// If an object or array, compare recursively
		if (['[object Array]', '[object Object]'].indexOf(itemType) >= 0) {
			if (!isEqual(item1, item2)) return false;
		}

		// Otherwise, do a simple comparison
		else {

			// If the two items are not the same type, return false
			if (itemType !== Object.prototype.toString.call(item2)) return false;

			// Else if it's a function, convert to a string and compare
			// Otherwise, just compare
			if (itemType === '[object Function]') {
				if (item1.toString() !== item2.toString()) return false;
			} else {
				if (item1 !== item2) return false;
			}

		}
	};

	// Compare properties
	if (type === '[object Array]') {
		for (let i = 0; i < valueLen; i++) {
			if (compare(value[i], other[i]) === false) return false;
		}
	} else {
		for (const key in value) {
			if (value.hasOwnProperty(key)) {
				if (compare(value[key], other[key]) === false) return false;
			}
		}
	}

	// If nothing failed, return true
	return true;

};

exports.isEqual = isEqual;