Skip to content

Latest commit

 

History

History
112 lines (91 loc) · 5.89 KB

README.md

File metadata and controls

112 lines (91 loc) · 5.89 KB

Hal - A lib of sorting & searching algorithms

Provided Sorting Algorithms (From Fast to Slowest In General)

  • Tim Sort
  • Quick Sort (Support two partition methods: Lomuto And Hoare)
  • Heap Sort
  • B-Tree Sort
  • Radix Sort
  • Insert Sort (Fast with small slice)

TO-DO (sorting)

  • Stooge Sort
  • Merge Sort
  • Shell Sort
  • Bucket Sort
  • Counting Sort
  • Pancake Sort
  • Bitonic Sort

TO-DO (other features)

  • Support string sort
  • Search algorithms

Benchmark

Test Bed Description

Hardware Platform MacBook Pro (15-inch, 2017)
OS macOS 10.14.4
Processor 2.9 GHz Intel Core i7, 4 Cores
Memory 16 GB 2133 MHz LPDDR3

Task

Sorting N Random Numbers, range from 1 to 2N. In my benchmark experiment, N is set to 100, 1000, 10000, 100000.

Results - 100 Random Numbers

  • Fast in speed: Tim Sort(run size=32),
  • Best in general (both speed and memory): Insert Sort

Algorithm Rounds Running Time Memory Allocations
Tim Sort(run size=32) 1157804 3102 ns/op 896 B/op 1 allocs/op
Tim Sort(run size=64) 1000000 3147 ns/op 896 B/op 1 allocs/op
Tim Sort(run size=128) 629481 5964 ns/op 2496 B/op 7 allocs/op
Quick Sort(Hoare) 482629 7420 ns/op 896 B/op 1 allocs/op
Quick Sort(Lomuto) 597049 5837 ns/op 896 B/op 1 allocs/op
Quick Sort(Golang Built-in) 384768 9351 ns/op 928 B/op 2 allocs/op
Heap Sort 366904 8802 ns/op 896 B/op 1 allocs/op
Insert Sort 730724 4890 ns/op 896 B/op 1 allocs/op

Results - 1000 Random Numbers

  • Fast in speed: Tim Sort(run size=128)
  • Best in general (both speed and memory): Quick Sort(Lomuto)

Algorithm Rounds Running Time Memory Allocations
Tim Sort(run size=32) 49072 73275 ns/op 48640 B/op 63 allocs/op
Tim Sort(run size=64) 45804 76612 ns/op 48640 B/op 31 allocs/op
Tim Sort(run size=128) 87736 41032 ns/op 32640 B/op 15 allocs/op
Quick Sort(Hoare) 43159 85893 ns/op 8192 B/op 1 allocs/op
Quick Sort(Lomuto) 45590 71234 ns/op 8192 B/op 1 allocs/op
Quick Sort(Golang Built-in) 27972 127098 ns/op 8224 B/op 2 allocs/op
Heap Sort 28760 124803 ns/op 8192 B/op 1 allocs/op
Insert Sort 20487 172544 ns/op 8192 B/op 1 allocs/op

Results - 10K Random Numbers

  • Fast in speed: Tim Sort(run size=128)
  • Best in general (both speed and memory): Quick Sort(Lomuto)

Algorithm Rounds Running Time Memory Allocations
Tim Sort(run size=32) 3559 927927 ns/op 774914 B/op 625 allocs/op
Tim Sort(run size=64) 5282 707896 ns/op 695044 B/op 313 allocs/op
Tim Sort(run size=128) 6616 559145 ns/op 615171 B/op 157 allocs/op
Quick Sort(Hoare) 3795 974970 ns/op 81920 B/op 1 allocs/op
Quick Sort(Lomuto) 4334 872705 ns/op 81920 B/op 1 allocs/op
Quick Sort(Golang Built-in) 2158 1629768 ns/op 81952 B/op 2 allocs/op
Heap Sort 2289 1504067 ns/op 81920 B/op 1 allocs/op
Insert Sort 235 14666689 ns/op 81920 B/op 1 allocs/op

Results - 100K Random Numbers

  • Fast in speed: Tim Sort(run size=128) (0.007 seconds)
  • Best in general (both speed and memory): Quick Sort(Lomuto)

Algorithm Rounds Running Time Memory Allocation Allocations
Tim Sort(run size=32) 285 11812962 ns/op 10349629 B/op 6249 allocs/op
Tim Sort(run size=64) 414 8985237 ns/op 9549867 B/op 3125 allocs/op
Tim Sort(run size=128) 495 7144921 ns/op 8750111 B/op 1563 allocs/op
Quick Sort(Hoare) 344 10669909 ns/op 802817 B/op 1 allocs/op
Quick Sort(Lomuto) 381 9409562 ns/op 802819 B/op 1 allocs/op
Quick Sort(Golang Built-in) 194 18554115 ns/op 802848 B/op 2 allocs/op
Heap Sort 186 19066672 ns/op 802822 B/op 1 allocs/op
Insert Sort 3 1470262444 ns/op 802816 B/op 1 allocs/op

Tim Sort(128) VS Quick Sort(Lomuto) - 100 Million Random Numbers

  • Tim Sort(run size=128): 11.5 seconds, 15GB per operation
  • Quick Sort(Lomuto): 14.4 seconds, 760MB per operation
Algorithm Rounds Running Time Memory Allocation Allocations
Tim Sort(run size=128) 1 11525982358 ns/op 16532869296 B/op 1562525 allocs/op
Quick Sort(Lomuto) 1 14375655148 ns/op 800006144 B/op 1 allocs/op