[用JS來寫演算法和了解資料結構] Day12 Algorithm - Sorting 排序

Sorting 排序

• 排序 Sorting:
  Comparison Sort

1. 氣泡排序 Bubble Sort - Time O(n) or O(n^2) / Space - O(1)

2. 選擇排序 Selection Sort - Time O(n^2) / Space - O(1)

3. 插入排序 Insertion Sort - Time O(n) or O(n^2) / Space - O(1)

4. 合併排序 Merge Sort - Time O(n log n) / Space - O(n)

5. 快速排序 Quick Sort - Time O(n log n) / Space - O(log n)

• 合併排序 Merge Sort 和 快速排序 Quick Sort 用 Divide and Conquer Recursion 方式

• Heap Sort

Non-Comparison Sort

• Counting Sort
• Radix Sort

• Sorting Algorithms Animations

• Sorting Dances Video

Array.sort()

• JavaScript中的Array.sort()方法使用的是 取決於瀏覽器 Chrome V8 主要用快速排序 QuickSort 也有一些Merge Sort 和 Insertion Sort
  sort() 會將元素轉換成 字串 來排序，預設排序為unicode 從 a 排到 z , 從 小 排到 大，若有十位數以上數字則會產生排序問題，因此需要用以下方法來解決。

let ary = [100, 1, 4, 50]; 

ary.sort();
console.log(ary);   //[1, 100, 4, 50]依造轉換成的字串的unicode來決定排序

ary.sort((a,b) => b - a);
console.log(ary);   // [100, 50, 4, 1] 倒序

ary.sort((a,b) => a - b);
console.log(ary);   // [1, 4, 50, 100] 正序

氣泡排序 Bubble Sort

Time - O(n) best or O(n^2) for average and worst
Space - O(1)

第一個與第二個比較大小是否交換順序，不用交換或交換完後跟下一個比大小是否交換順序，以此類推，整排結束後，再接下從第二個開始與第三個比，以此類推….最後完成排序

const numbersArr = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function bubbleSortAscending(array) {
  for(let i = 0; i < array.length; i++){
    for(let j = 0; j < array.length; j++){
      if(array[j] > array[j + 1]){
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

function bubbleSortDescending(array) {
  for(let i = 0; i < array.length; i++){
    for(let j = 0; j < array.length; j++){
      if(array[j] < array[j + 1]){
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

console.log(bubbleSortAscending(numbersArr));
console.log(bubbleSortDescending(numbersArr));

選擇排序 Selection Sort

Time - O(n^2)
Space - O(1)

loop整個array去找出誰是最小值(最大值)，然後把它放到第一個，接著從第二個開始再loop找出誰是最小值(最大值)再放到第一個，以此類推….最後完成排序

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function selectionSortAscending(array) {
    for (let i = 0; i < array.length; i++) {
        let minIndex = i;
        let temp = array[i];
        for (let j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
    return array;
}

function selectionSortDescending(array) {

    for (let i = 0; i < array.length; i++) {
        let maxIndex = i;
        let temp = array[i];
        for (let j = i + 1; j < array.length; j++) {
            if (array[j] > array[maxIndex]) {
                maxIndex = j;
            }
        }
        array[i] = array[maxIndex];
        array[maxIndex] = temp;
    }

    return array;
}

console.log(selectionSortAscending(numbers));
console.log(selectionSortDescending(numbers));

插入排序 Insertion Sort

Time - O(n)(for already sorted array) O(n^2) for average and worst
Space - O(1)

• 最熟悉的例子就是玩接龍時，要先把手上的牌依照大小排列的插入法
  先從第二個與前一個比較，若較大或相等則不動，若較小則交換到第一個，接下來換第三個數字與前一個比較，若較大或相等則不動，若較小則交換到第一個，再與前一個比較，以此類推到第一個…再以此類推直到最後一個比較完

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function sort(array) {
    for (let i = 1; i < array.length; i++) {
        let current = array[i];
        for (let j = i - 1; j >= 0; j--) {
            if (current >= array[j]) {
                break;
            } else {
                array[j + 1] = array[j]
                array[j] = current;
            }
        }
    }
    return array;
}
console.log(insertionSort(numbers));

合併排序 Merge Sort

Time O(n log n)
Space - O(n)

把 數列陣列 拆開再拆開 到最後剩一下一個數值，然後兩個陣列各自從第一個數值比較，小的拉出放前，再來比較拿出後的下一個，小的拉出放前到陣列比較結束，合併成一個新陣列，再依序必較其他合併的陣列到最後合併成一個陣列，排序完成。

const numbers = [99, 44, 1, 2, 10];

function mergeSort(array) {
    if (array.length === 1) {
        return array
    }
    // Split Array in into right and left
    let middle = Math.floor(array.length / 2); //find the middle 5/2=2.5 => 2 
    let left = array.slice(0, middle); 
    let right = array.slice(middle); 

    return merge(mergeSort(left), mergeSort(right)); //recursion 
}

function merge(left, right) {
    console.log('left', left, 'right', right);
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while(leftIndex < left.length && rightIndex < right.length){
        if(left[leftIndex] < right[rightIndex]){
            result.push(left[leftIndex]);
            leftIndex++
        }else{
            result.push(right[rightIndex]);
            rightIndex ++
        }
    }

    return [...result, ...left.slice(leftIndex), ...right.slice(rightIndex)];
    // return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));    
}

console.log(mergeSort(numbers));

合併排序題目：輸出逆序數對的總數

//Given an array, please calculate the total number of inverted pairs. 逆序數對(左>右)
// For example, for the array A = [1, 9, 2, 7, 3], 
// there are inverted pairs: (9, 2), (9, 7), (9, 3), (7, 3), totaling 4 pairs.

// Input [5, 4, 3, 2, 1]
// Output 10

function countInvertedPairs(array){
  let count = 0;
  function mergeSort(arr){
    if (arr.length <= 1){
      return arr;
    }
  
    let middle = Math.floor(arr.length / 2);
    let left = arr.slice(0, middle);
    let right = arr.slice(middle);
  
    return merge(mergeSort(left), mergeSort(right));
  }
  
  function merge(left, right){
    let i = 0;
    let j = 0;
    let result = [];
  
    while(i < left.length && j < right.length){
      if(left[i]<= right[j]){
        result.push(left[i]);
        i++;
      }else{
        result.push(right[j]);
        // ex. 左[3, 4] 右[1, 2] 
        // 左 3 > 右 1 代表3後面的4也大於右 count算成 長度2 - 現在index 0 = 2
        count += left.length - i;
        j++;
      }
    }
    return [...result, ...left.slice(i), ...right.slice(j)];
  }

  mergeSort(array);
  return count;
}

快速排序 Quick Sort

Time - O(n log n)
Space - O(log n)

先隨機選一個數作為pivot 基準數，最左邊有一個pointer L，最右邊也有一個pointer R
跟pivot做比較，比pivot小的放在

const numbers = [8, 9, 2, 5, 1];    

function quickSort(arr, left, right) {
    if (left < right) {
        //找出pivot比較完後 放置好的index
        let partitionIndex = partition(arr, left, right); 
        // Sort left
        quickSort(arr, left, partitionIndex - 1); 
        // Sort right
        quickSort(arr, partitionIndex + 1, right); 
    }
    return arr;
}

//找出pivot比較完後 放置好的index
function partition(arr, left, right) {
    let pivot = right //從最右邊的第一個當作pivot
    let partitionIndex = left;

    for (let i = left; i < right; i++) { 
        if (arr[i] < arr[pivot]) {
            swap(arr, i, partitionIndex); 
            partitionIndex++;
        }
    }
    swap(arr, right, partitionIndex); 

    return partitionIndex; 
}

//array值互交換
function swap(arr, index1, index2) {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
}

console.log(quickSort(numbers, 0, numbers.length - 1));

• 用到比較多空間但是很簡易的解法

const numbers = [8, 9, 2, 5, 1];   

function quickSort(arr) {
    if (arr.length <= 1) return arr;

    const [pivot, ...ary] = arr;
    const left = []; 
    const right = []; 

    ary.forEach(item => {
        if (item < pivot) {
            left.push(item);
        } else {
            right.push(item);
        }
    })

    return [...quickSort(left), pivot, ...quickSort(right)]
}

console.log(quickSort(numbers));

• 其他解法

const numbers = [8, 9, 2, 5, 1];

function quickSort(array, left, right) {
    if (array.length <= 1) {
        return array;
    }

    let indexCounter = 0;

    for (let i = 0; i < array.length; i++) {
        if (array[i - indexCounter] > array[right - indexCounter]) { 
            array.push(array.splice(i - indexCounter, 1)[0]); 
            indexCounter++; 
        }
    }

    let leftArray = array.slice(left, right - indexCounter);
    let rightArray = array.slice(right - indexCounter + 1, array.length);

    return [...quickSort(leftArray, 0, leftArray.length - 1), array[right - indexCounter], ...quickSort(rightArray, 0, rightArray.length - 1)];
}

console.log(quickSort(numbers, 0, numbers.length - 1));

Counting Sort

//counting sort
//用於陣列中的數字有範圍 1000以內 或是更少10 或 100 以內
// [1, 2, 4, 5, 7, 9, 10....  ] 但可能有20萬個數字

const numbers = [10, 2, 4, 5, 1, 2, 1, 9];

function CountingSort(array) {
  let result = [];
  let collection = [...Array(10).fill(0)]; //create space
  //let collection = new Array(10).fill(0);

  array.forEach(item => {
    collection[item - 1]++
  });

  collection.forEach((item, i) => {
    for(let j = 1; j <= item; j++){
      result.push(i + 1);
    }
  })
 return result;
}

console.log(CountingSort(numbers));

Interview Question

1. Sort 10 schools around your house by distance:
   insertion sort

2. eBay sorts listings by the current Bid amount:
   radix or counting sort

3. Sport scores on ESPN
   quick sort

4. Massive database (can’t fit all into memory) needs to sort through past year’s user data
   merge sort

5. Almost sorted Udemy review data needs to update and add 2 new reviews
   insertion sort

6. Temperature Records for the past 50 years in Canada
   radix or counting sort
   quick sort if decimal places

7. Large user name database needs to be sorted. Data is very random.
   quick sort

8. You want to teach sorting for the first time
   bubble sort

學習與參考資料

• Master the Coding Interview: Data Structures + Algorithms