Sorting algorithms JS

#javascript #algorithms

I work with backend and frontend part of web applications everyday. But usually I solve typical routine issues like a new webform or creation of an additional field in a database. So, I try to not forget simple algorithms, like sorting.

So let's begin, I want to write a function that will return a sorted array. This code solve half of my issue:

class Sorting {
    constructor() {
        this.array = [54,26,1,93,100,17,15,77,57,31,44,55,11,20,94,94];
    }
    sort() {
        return this.array;
    }
}

Bubble sorting, this kind of sorting take two adjacent value, compare these and move biggest value to top

class BubbleSorting extends Sorting {
    sort() {
        for (let i = this.array.length - 1; i > 0; i--) {
            for (let j = 0; j < i; j++) {
                if (this.array[j] > this.array[j + 1]) {
                    const tmp = this.array[j + 1];
                    this.array[j + 1] = this.array[j];
                    this.array[j] = tmp;
                }
            }
        }

        return this.array;
    }
}

Selection sorting, this kind of sorting find a minimum value and move this into begin of array

class SelectionSorting extends Sorting {
    sort() {
        for (let i = 0; i < this.array.length - 1; i++) {
            let min = i;
            for (let j = i + 1; j < this.array.length; j++) {
                if (this.array[j] < this.array[min]) {
                    min = j;
                }
            }
            if (min !== i) {
                const tmp = this.array[i];
                this.array[i] = this.array[min];
                this.array[min] = tmp;
            }
        }

        return this.array;
    }
}

Insertion sorting, this kind of sorting take value in right part of array and put this to correct place in the left part of array

class InsertionSorting extends Sorting {
    sort() {
        for (let i = 1; i < this.array.length; i++) {
            let j = i;
            const tmp = this.array[i];
            while (j > 0 && tmp < this.array[j - 1]) {
                this.array[j] = this.array[j - 1];
                j--;
            }
            if (i !== j) {
                this.array[j] = tmp;
            }
        }

        return this.array;
    }
}

Merge sorting, this kind of sorting does separate an array by two parts, and recursive sorting these two parts, while array length will not be less than two values. After separating, the algorithm does compare values from these parts and merge into one sorted array.

class MergeSorting extends Sorting {
    sort(array = this.array) {
        if (array.length < 2) {
            return array;
        }
        const middle = Math.ceil(array.length / 2);
        const left = this.sort(array.slice(0, middle));
        const right = this.sort(array.slice(middle, array.length));

        let i = 0;
        let j = 0;
        const newArray = [];

        while(i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                newArray.push(left[i]);
                i++
            } else {
                newArray.push(right[j]);
                j++
            }
        }

        while (i < left.length) {
            newArray.push(left[i]);
            i++;
        }

        while (j < right.length) {
            newArray.push(right[j]);
            j++;
        }

        return newArray;
    }
}

Quick sorting, this kind of sorting selects one element and compares others with them. Values less that selected move into left, values bigger move into right. After separating both paths of the array, an algorithm applies recursive sorting and merge values into one array.

class QuickSorting extends Sorting {
    constructor() {
        super();
        this.index = 0;
    }
    sort(array = this.array) {
        if (array.length < 2) {
            return array;
        }

        let left = [];
        let right = [];
        for (let i = 0; i < array.length; i++) {
            if (i === this.index) {
                continue;
            }

            if (array[i] < array[0]) {
                left.push(array[i]);
            } else {
                right.push(array[i]);
            }
        }
        left.push(array[this.index]);

        left = this.sort(left);
        right = this.sort(right);

        return left.concat(right);
    }
}