1/alichraghi/zort v0.30
a lot of sorting algorithms written in zig
Zort
Implementation of 13 sorting algorithms in Zig
| Algorithm | Custom Comparison | Zero Allocation | | ----------------------- | ----------------- | --------------- | | Bubble | ✅ | ✅ | | Comb | ✅ | ✅ | | Heap | ✅ | ✅ | | Insertion | ✅ | ✅ | | Merge | ✅ | ❌ | | PDQ | ✅ | ✅ | | Quick | ✅ | ✅ | | Radix (no negative yet) | ❌ | ❌ | | Selection | ✅ | ✅ | | Shell | ✅ | ✅ | | Tail | ✅ | ❌ | | Tim | ✅ | ❌ | | Twin | ✅ | ❌ |
Usage
const zort = @import("zort");
fn asc(a: u8, b: u8) bool {
return a < b;
}
pub fn main() !void {
var arr = [_]u8{ 9, 1, 4, 12, 3, 4 };
try zort.quickSort(u8, &arr, asc);
}
Benchmarks
Raspberry Pi 4 with 8GB RAM (old)
gantt
title Sorting (ascending) 10000000 usize
dateFormat x
axisFormat %S s
section random
tim 0.622: 0,622
pdq 1.280: 0,1280
quick 2.557: 0,2555
radix 2.645: 0,2643
twin 3.156: 0,3156
std_block_merge 4.340: 0,4339
comb 5.004: 0,5004
shell 8.000: 0,8001
section sorted
tim 0.623: 0,623
pdq 0.021: 0,21
quick 0.928: 0,928
radix 2.680: 0,2681
twin 0.139: 0,139
std_block_merge 0.167: 0,167
comb 1.498: 0,1498
shell 1.607: 0,1607
section reverse
tim 0.611: 0,611
pdq 0.367: 0,367
quick 1.787: 0,1787
radix 2.313: 0,2311
twin 1.639: 0,1639
std_block_merge 2.428: 0,2429
comb 1.934: 0,1934
shell 1.834: 0,1834
section ascending saw
tim 0.617: 0,617
pdq 1.147: 0,1147
quick 16.875: 0,16887
radix 2.684: 0,2684
twin 0.672: 0,672
std_block_merge 1.472: 0,1472
comb 3.018: 0,3018
shell 2.107: 0,2107
section descending saw
tim 0.618: 0,618
pdq 1.153: 0,1153
quick SKIPPED: 0
radix 2.658: 0,2658
twin 1.757: 0,1757
std_block_merge 2.545: 0,2543
comb 3.057: 0,3056
shell 2.139: 0,2138
gantt
title Sorting (ascending) 10000000 isize
dateFormat x
axisFormat %S s
section random
tim 0.619: 0,619
pdq 1.289: 0,1289
quick 2.568: 0,2568
radix 0.019: 0,19
twin 3.215: 0,3214
std_block_merge 4.336: 0,4335
comb 4.926: 0,4924
shell 7.957: 0,7956
section sorted
tim 0.624: 0,624
pdq 0.021: 0,21
quick 0.814: 0,814
radix 0.019: 0,19
twin 0.100: 0,100
std_block_merge 0.167: 0,167
comb 1.498: 0,1498
shell 1.600: 0,1600
section reverse
tim 0.622: 0,622
pdq 0.184: 0,184
quick 1.831: 0,1831
radix 0.019: 0,19
twin 0.082: 0,82
std_block_merge 1.979: 0,1979
comb 1.950: 0,1950
shell 1.840: 0,1840
section ascending saw
tim 0.622: 0,622
pdq 1.147: 0,1147
quick 11.813: 0,11813
radix 0.019: 0,19
twin 0.654: 0,654
std_block_merge 1.471: 0,1471
comb 3.020: 0,3019
shell 2.111: 0,2113
section descending saw
tim 0.620: 0,620
pdq 1.145: 0,1145
quick SKIPPED: 0
radix 0.019: 0,19
twin 0.714: 0,714
std_block_merge 2.496: 0,2496
comb 3.072: 0,3072
shell 2.145: 0,2143
Intel(R) Core(TM) i5-6300U CPU @ 2.40GHz
gantt
title Sorting (ascending) 10000000 usize
dateFormat x
axisFormat %S s
section random
tim 0.179: 0,179
pdq 0.450: 0,450
quick 1.243: 0,1243
radix 0.945: 0,945
twin 1.412: 0,1412
std_block_merge 1.784: 0,1784
comb 1.797: 0,1797
shell 2.357: 0,2358
section sorted
tim 0.193: 0,193
pdq 0.007: 0,7
quick 0.294: 0,294
radix 0.956: 0,956
twin 0.043: 0,43
std_block_merge 0.059: 0,59
comb 0.471: 0,471
shell 0.253: 0,253
section reverse
tim 0.179: 0,179
pdq 0.097: 0,97
quick 0.542: 0,542
radix 1.097: 0,1097
twin 0.422: 0,422
std_block_merge 0.474: 0,474
comb 0.583: 0,583
shell 0.324: 0,324
section ascending saw
tim 0.180: 0,180
pdq 0.441: 0,441
quick 0.801: 0,801
radix 1.098: 0,1098
twin 0.272: 0,272
std_block_merge 0.469: 0,469
comb 0.897: 0,897
shell 0.576: 0,576
section descending saw
tim 0.180: 0,180
pdq 0.441: 0,441
quick SKIPPED: 0
radix 0.947: 0,947
twin 0.517: 0,517
std_block_merge 0.654: 0,654
comb 0.915: 0,915
shell 0.567: 0,567
gantt
title Sorting (ascending) 10000000 isize
dateFormat x
axisFormat %S s
section random
tim 0.181: 0,181
pdq 0.470: 0,470
quick 1.201: 0,1201
radix 0.004: 0,4
twin 1.402: 0,1402
std_block_merge 1.775: 0,1775
comb 1.727: 0,1727
shell 2.469: 0,2467
section sorted
tim 0.179: 0,179
pdq 0.008: 0,8
quick 0.205: 0,205
radix 0.004: 0,4
twin 0.029: 0,29
std_block_merge 0.059: 0,59
comb 0.499: 0,499
shell 0.252: 0,252
section reverse
tim 0.177: 0,177
pdq 0.039: 0,39
quick 0.441: 0,441
radix 0.004: 0,4
twin 0.014: 0,14
std_block_merge 0.313: 0,313
comb 0.596: 0,596
shell 0.318: 0,318
section ascending saw
tim 0.180: 0,180
pdq 0.461: 0,461
quick 2.180: 0,2181
radix 0.004: 0,4
twin 0.271: 0,271
std_block_merge 0.467: 0,467
comb 0.946: 0,946
shell 0.628: 0,628
section descending saw
tim 0.180: 0,180
pdq 0.475: 0,475
quick SKIPPED: 0
radix 0.004: 0,4
twin 0.278: 0,278
std_block_merge 0.637: 0,637
comb 0.968: 0,968
shell 0.648: 0,648
Thanks to
voroskoi and other contributors
Package Contents
- .gitattributes
- benchmark/run_bench.zig
- benchmark/generator.zig
- LICENSE
- build.zig
- benchmark.sh
- zigmod.yml
- src/insertion.zig
- src/msb_radix.zig
- src/tim.zig
- src/radix.zig
- src/bubble.zig
- src/merge.zig
- src/shell.zig
- src/tail.zig
- src/pdqsort.zig
- src/selection.zig
- src/main.zig
- src/test.zig
- src/heap.zig
- src/twin.zig
- src/quick.zig
- src/comb.zig
- README.md
- media/logo.png
- media/logo.fig
- .gitignore
History
Published On | Tree @ Commit | Size | |
---|---|---|---|
v0.36 | Sun, 08 Jan 2023 17:33:17 UTC | Tree | 122.073 KB |
v0.35 | Sat, 29 Oct 2022 19:29:33 UTC | Tree | 121.987 KB |
v0.34 | Thu, 22 Sep 2022 19:25:40 UTC | Tree | 114.859 KB |
v0.33 | Sat, 27 Aug 2022 03:47:22 UTC | Tree | 118.303 KB |
v0.32 | Mon, 22 Aug 2022 18:21:47 UTC | Tree | 117.782 KB |
v0.31 | Mon, 08 Aug 2022 21:38:40 UTC | Tree | 117.778 KB |
v0.30 | Sat, 06 Aug 2022 09:53:24 UTC | Tree | 88.812 KB |
v0.29 | Fri, 05 Aug 2022 12:07:15 UTC | Tree | 82.142 KB |
v0.28 | Fri, 05 Aug 2022 11:10:58 UTC | Tree | 56.816 KB |
v0.27 | Fri, 05 Aug 2022 11:08:02 UTC | Tree | 56.822 KB |
v0.26 | Mon, 01 Aug 2022 19:46:11 UTC | Tree | 54.825 KB |
v0.25 | Mon, 01 Aug 2022 06:11:13 UTC | Tree | 49.457 KB |
v0.24 | Mon, 01 Aug 2022 06:09:33 UTC | Tree | 49.668 KB |
v0.23 | Sat, 30 Jul 2022 22:35:53 UTC | Tree | 49.218 KB |
v0.22 | Sat, 30 Jul 2022 20:57:59 UTC | Tree | 49.386 KB |
v0.21 | Sat, 30 Jul 2022 20:43:16 UTC | Tree | 49.209 KB |
v0.20 | Thu, 28 Jul 2022 20:32:09 UTC | Tree | 44.887 KB |
v0.19 | Sun, 17 Jul 2022 06:36:58 UTC | Tree | 29.603 KB |
v0.18 | Thu, 19 May 2022 15:22:44 UTC | Tree | 27.198 KB |
v0.17 | Thu, 19 May 2022 15:17:40 UTC | Tree | 27.758 KB |
v0.16 | Thu, 19 May 2022 15:08:25 UTC | Tree | 27.285 KB |
v0.15 | Thu, 19 May 2022 14:10:51 UTC | Tree | 27.107 KB |
v0.14 | Sat, 07 May 2022 05:36:29 UTC | Tree | 29.861 KB |
v0.13 | Wed, 04 May 2022 14:45:20 UTC | Tree | 29.380 KB |
v0.12 | Mon, 02 May 2022 10:54:12 UTC | Tree | 61.833 KB |
v0.11 | Mon, 02 May 2022 10:49:59 UTC | Tree | 61.833 KB |
v0.10 | Sat, 23 Apr 2022 15:57:47 UTC | Tree | 52.633 KB |
v0.9 | Sun, 20 Mar 2022 18:47:44 UTC | Tree | 52.641 KB |
v0.8 | Sun, 20 Mar 2022 11:38:52 UTC | Tree | 52.973 KB |
v0.7 | Fri, 18 Mar 2022 16:32:02 UTC | Tree | 50.603 KB |
v0.6 | Fri, 18 Mar 2022 16:31:29 UTC | Tree | 50.733 KB |
v0.5 | Fri, 18 Mar 2022 16:27:12 UTC | Tree | 50.733 KB |
v0.4 | Fri, 18 Mar 2022 16:24:57 UTC | Tree | 50.765 KB |
v0.3 | Fri, 18 Mar 2022 16:21:29 UTC | Tree | 50.672 KB |
v0.2 | Thu, 17 Mar 2022 11:35:28 UTC | Tree | 19.215 KB |
v0.1 | Wed, 16 Mar 2022 16:50:48 UTC | Tree | 19.215 KB |