Skip to content

Latest commit

 

History

History
108 lines (91 loc) · 4.86 KB

README.md

File metadata and controls

108 lines (91 loc) · 4.86 KB
Raw

algs-playgrounds

learning and testing data structures, algorithms, leetcode, js api...

overview

  • my sorting test case

    • environment: node v14; ubuntu 20.04
    • auto-generated array of random numbers
    • array.length is 20000 / 200000
    • array contains negative and duplicated values

  • 排序算法测试小结

    • 👍🏻️ Array.prototype.sort官方api效率非常高，推荐使用，实现基于quickSort -> timSort
    • 较快的排序算法包括 quickSort, heapSort, mergeSort
    • n越大，一些算法就变得越慢，当n很大时排序时间 bubble > selection > insertion/shell >> merge、quick、heap

  • 说明

    • 当n大到20w时，能明显感到计算量变大、用时变长

      • 此时heapSort甚至比官方的array.sort还要快

    • 选择合适的比较/排序指标也很重要

  • common sort algorithms ing

    • selectionSort 选择排序
    • insertionSort 插入排序
    • shellSort 希尔排序
    • bubbleSort 冒泡排序
    • quickSort 快排 原地 递归
    • quickSortOutOfPlace 快排 非原地 递归
    • quickSort3Way 快排 三路 递归
    • mergeSort 归并 非原地 递归
    • mergeSortRecursive 归并 非原地 递归 辅助数组少
    • mergeSort3Way 归并 三路
    • mergeSortKWay
    • heapSort (max heap) 堆排序 原地 非递归
    • heapSort (min heap)
    • heapSortRecursive 堆排序 原地 递归

usage

  • no dependencies
  • npm install not required
git clone https://github.com/uptonking/algs-playgrounds

cd algs-playgrounds

node ./src/algs/sort-testing.mjs
  • view the tests result for 7 sort algorithms in the console

notes

  • when generating random array, config in ./src/algs/sort-testing.mjs can be changed

testing time for sorting algs is in nanoseconds

  • when array.length is 20000
    • 最慢的冒泡排序用时约为 0.65s
    • 普通递归原地快排quickSort为 0.009s
┌─────────┬───────────────────────────┬───────────┐
│ (index) │           name            │   time    │
├─────────┼───────────────────────────┼───────────┤
│    0    │ 'baselineFuncReturnOnly'  │   91258   │
│    1    │      'quickSort3Way'      │  4143739  │
│    2    │   'baselineJsArraySort'   │  6647251  │
│    3    │ 'mergeSortInsertForShort' │  7060690  │
│    4    │        'heapSort'         │  7351413  │
│    5    │   'quickSortOutOfPlace'   │  7448553  │
│    6    │    'heapSortRecursive'    │  8570473  │
│    7    │        'quickSort'        │  9935933  │
│    8    │   'mergeSortRecursive2'   │ 12057694  │
│    9    │      'mergeSort3Way'      │ 21504364  │
│   10    │        'mergeSort'        │ 25485743  │
│   11    │        'shellSort'        │ 122268829 │
│   12    │      'insertionSort'      │ 177277978 │
│   13    │      'selectionSort'      │ 466158271 │
│   14    │       'bubbleSort'        │ 652084456 │
└─────────┴───────────────────────────┴───────────┘
  • when array.length is 200000
    • 最慢的冒泡排序用时约为 77s
    • 普通递归原地快排quickSort为 0.03s
┌─────────┬───────────────────────────┬─────────────┐
│ (index) │           name            │    time     │
├─────────┼───────────────────────────┼─────────────┤
│    0    │ 'baselineFuncReturnOnly'  │   100687    │
│    1    │      'quickSort3Way'      │  29086530   │
│    2    │        'quickSort'        │  31534081   │
│    3    │        'heapSort'         │  38800232   │
│    4    │   'quickSortOutOfPlace'   │  43461417   │
│    5    │    'heapSortRecursive'    │  61064768   │
│    6    │   'mergeSortRecursive2'   │  63006206   │
│    7    │ 'mergeSortInsertForShort' │  64364868   │
│    8    │   'baselineJsArraySort'   │  65829406   │
│    9    │      'mergeSort3Way'      │ 1892612814  │
│   10    │        'mergeSort'        │ 3857869311  │
│   11    │      'insertionSort'      │ 13559555845 │
│   12    │        'shellSort'        │ 14974227838 │
│   13    │      'selectionSort'      │ 35763338813 │
│   14    │       'bubbleSort'        │ 77126959595 │
└─────────┴───────────────────────────┴─────────────┘