Sắp xếp bong bóng javascript es6

Ý tưởng của thuật toán là tìm ra giá trị nhỏ nhất trong đám mây, sau đó đưa nó về vị trí ban đầu, lặp lại cho các phần tử tiếp theo

Sắp xếp bong bóng javascript es6
Sắp xếp bong bóng javascript es6

function selectionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let minIndex;
    for (let i = 0; i < length - 1; i++) {
        minIndex = i;
        for (let j = i; j < length; j++) {
            if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            swap(arr, i, minIndex);
        }
    }
    return arr;
}

Sắp xếp bong bóng javascript es6
Sắp xếp bong bóng javascript es6

Sắp xếp chèn

  • Tình trạng tốt nhất. độ phức tạp = O(N)
  • Badest love. độ phức tạp = O(N^2)

Thuật toán này sẽ tạo ra một mảng mới, tìm kiếm và chèn từng phần tử vào đúng thứ tự. Will like after

  1. Cứ coi như phần tử đầu tiên là đúng vị trí
  2. Lấy phần tử đầu tiên này để so sánh với phần tử tiếp theo, nó có 2 vấn đề là ở yên vị trí đang ở, hay là chúng ta thêm phần tử thứ 2 vào trước phần tử đầu tiên.
  3. tái hiện lại tương tự

Sắp xếp bong bóng javascript es6
Sắp xếp bong bóng javascript es6

function insertionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let temp;
    for (let i = 1; i < length; i++) {
        let j = i;
        temp = arr[i];
        while (j > 0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}

Sắp xếp bong bóng javascript es6
Sắp xếp bong bóng javascript es6

Hợp nhất Sắp xếp

Độ phức tạp.

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};

function defaultCompare(a, b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
3

Là thuật toán chia để trị, chi nhỏ các phần tử ban đầu thành các nhóm nhỏ hơn để dễ xử lý từng cụm từ

Sắp xếp bong bóng javascript es6
Sắp xếp bong bóng javascript es6

function mergeSort(arr, compare = defaultCompare) {
    if (arr.length > 1) {
        const { length } = arr;
        const middle = Math.floor(length / 2);
        const left = mergeSort(arr.slice(0, middle), compare);
        const right = mergeSort(arr.slice(middle, length), compare);
        arr = merge(left, right, compare);
    }
    return arr;
}

function merge(left, right, compare) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

Sắp xếp bong bóng javascript es6
Sắp xếp bong bóng javascript es6

Sắp xếp nhanh chóng

  • Tình trạng tốt nhất. độ phức tạp = 
    const Compare = {
        LESS_THAN: -1,
        BIGGER_THAN: 1
    };
    
    function defaultCompare(a, b) {
        if (a === b) {
            return 0;
        }
        return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
    }
    3
  • Badest love. độ phức tạp = O(N^2)

Đây là thuật toán được sử dụng nhiều nhất, vẫn là phương pháp chia để trị

Có thể xem lại bài giới thiệu về Quick Sort của mình

Sắp xếp bong bóng javascript es6
Sắp xếp bong bóng javascript es6

function quickSort(arr, compare = defaultCompare) {
    return quick(arr, 0, arr.length - 1, compare);
}

function quick(arr, left, right, compare) {
    let i;
    if (arr.length > 1) {
        i = partition(arr, left, right, compare);
        if (left < i - 1) {
            quick(arr, left, i - 1, compare);
        }
        if (i < right) {
            quick(arr, i, right, compare);
        }
    }
    return arr;
}

function partition(arr, left, right, compare) {
    const pivot = arr[Math.floor((right, left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (compare(arr[i], pivot) === Compare.LESS_THAN) {
            i++;
        }
        while (compare(arr[j], pivot) === Compare.BIGGER_THAN) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}

Sắp xếp theo nhóm

  • Tình trạng tốt nhất. độ phức tạp = 
    const Compare = {
        LESS_THAN: -1,
        BIGGER_THAN: 1
    };
    
    function defaultCompare(a, b) {
        if (a === b) {
            return 0;
        }
        return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
    }
    6
  • Badest love. độ phức tạp = O(N^2)

Ý tưởng là sẽ chia đôi thành 2 mảng, rồi trên từng mảng đó, áp dụng một thuật toán sắp xếp trên đó, giống như sắp xếp chèn

Sắp xếp bong bóng javascript es6
Sắp xếp bong bóng javascript es6

function bucketSort(arr, bucketSize) {
    if (arr.length < 2) {
        return arr;
    }
    // create buckets and distribute the elements
    const buckets = createBuckets(arr, bucketSize);
    // sort the buckets using insertion sort and add all bucket elements to sorted result 
    return sortBuckets(buckets);
}

function createBuckets(arr, bucketSize) {
    // determine the bucket count
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;

    // initialize each bucket (a multidimensional array)
    const buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    // distribute elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }
    return buckets;
}

function sortBuckets(buckets) {
    const sortedArr = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]); // quick sort is another good option
            sortedArr.push(...buckets[i]);
        }
    }
    return sortedArr;
}

Lưu ý sắp xếp nhóm chạy tốt nhất khi có thể chia đều các phần tử cho các nhóm, việc chia thành 2 nhóm cũng không bắt buộc, có thể chia nhiều hơn nếu số lượng phần tử nhiều