1/alichraghi/zort v0.33
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
gantt
title Sorting (ascending) 10000000 usize
dateFormat x
axisFormat %S s
section random
tim 3.646: 0,3646
pdq 1.323: 0,1323
quick 2.264: 0,2263
radix 2.590: 0,2590
msb_radix 1.271: 0,1271
twin 2.928: 0,2929
std_block_merge 3.982: 0,3982
comb 4.680: 0,4679
shell 7.617: 0,7616
section sorted
tim 0.021: 0,21
pdq 0.021: 0,21
quick 0.818: 0,818
radix 3.184: 0,3184
msb_radix 0.867: 0,867
twin 0.235: 0,235
std_block_merge 0.151: 0,151
comb 1.428: 0,1428
shell 1.562: 0,1562
section reverse
tim 1.461: 0,1461
pdq 0.353: 0,353
quick 1.623: 0,1623
radix 3.123: 0,3125
msb_radix 0.871: 0,871
twin 1.848: 0,1848
std_block_merge 2.365: 0,2366
comb 1.946: 0,1946
shell 1.766: 0,1766
section ascending saw
tim 0.645: 0,645
pdq 1.197: 0,1197
quick 4.809: 0,4809
radix 2.629: 0,2629
msb_radix 0.960: 0,960
twin 0.712: 0,712
std_block_merge 1.325: 0,1325
comb 2.896: 0,2895
shell 2.039: 0,2039
section descending saw
tim 1.580: 0,1580
pdq 1.182: 0,1182
quick SKIPPED: 0
radix 2.943: 0,2944
msb_radix 0.955: 0,955
twin 1.868: 0,1868
std_block_merge 2.396: 0,2395
comb 3.064: 0,3064
shell 2.090: 0,2090
gantt
title Sorting (ascending) 10000000 isize
dateFormat x
axisFormat %S s
section random
tim 3.695: 0,3697
pdq 1.314: 0,1314
quick 2.262: 0,2262
radix 0.019: 0,19
msb_radix 1.176: 0,1176
twin 2.936: 0,2936
std_block_merge 3.973: 0,3973
comb 4.879: 0,4880
shell 7.574: 0,7576
section sorted
tim 0.021: 0,21
pdq 0.021: 0,21
quick 0.707: 0,707
radix 0.019: 0,19
msb_radix 0.584: 0,584
twin 0.174: 0,174
std_block_merge 0.151: 0,151
comb 1.415: 0,1415
shell 1.439: 0,1439
section reverse
tim 0.097: 0,97
pdq 0.183: 0,183
quick 1.610: 0,1610
radix 0.019: 0,19
msb_radix 0.606: 0,606
twin 0.082: 0,82
std_block_merge 1.952: 0,1952
comb 1.955: 0,1955
shell 2.217: 0,2216
section ascending saw
tim 0.652: 0,652
pdq 1.204: 0,1204
quick 5.137: 0,5135
radix 0.019: 0,19
msb_radix 0.688: 0,688
twin 0.697: 0,697
std_block_merge 1.327: 0,1327
comb 3.039: 0,3039
shell 2.258: 0,2258
section descending saw
tim 0.708: 0,708
pdq 1.207: 0,1207
quick SKIPPED: 0
radix 0.019: 0,19
msb_radix 0.700: 0,700
twin 0.755: 0,755
std_block_merge 2.363: 0,2363
comb 3.014: 0,3014
shell 2.297: 0,2297
Intel(R) Core(TM) i5-6300U CPU @ 2.40GHz
gantt
title Sorting (ascending) 10000000 usize
dateFormat x
axisFormat %S s
section random
tim 2.072: 0,2073
pdq 0.447: 0,447
quick 1.114: 0,1114
radix 1.251: 0,1251
msb_radix 0.355: 0,355
twin 1.187: 0,1187
std_block_merge 1.556: 0,1556
comb 1.592: 0,1592
shell 2.240: 0,2240
section sorted
tim 0.008: 0,8
pdq 0.006: 0,6
quick 0.261: 0,261
radix 1.249: 0,1249
msb_radix 0.375: 0,375
twin 0.073: 0,73
std_block_merge 0.058: 0,58
comb 0.397: 0,397
shell 0.250: 0,250
section reverse
tim 0.396: 0,396
pdq 0.091: 0,91
quick 0.476: 0,476
radix 1.086: 0,1086
msb_radix 0.377: 0,377
twin 0.414: 0,414
std_block_merge 0.484: 0,484
comb 0.488: 0,488
shell 0.308: 0,308
section ascending saw
tim 0.349: 0,349
pdq 0.443: 0,443
quick 0.910: 0,910
radix 1.256: 0,1256
msb_radix 0.376: 0,376
twin 0.246: 0,246
std_block_merge 0.369: 0,369
comb 0.754: 0,754
shell 0.553: 0,553
section descending saw
tim 0.543: 0,543
pdq 0.441: 0,441
quick SKIPPED: 0
radix 1.247: 0,1247
msb_radix 0.376: 0,376
twin 0.478: 0,478
std_block_merge 0.573: 0,573
comb 0.788: 0,788
shell 0.551: 0,551
gantt
title Sorting (ascending) 10000000 isize
dateFormat x
axisFormat %S s
section random
tim 2.145: 0,2145
pdq 0.475: 0,475
quick 1.116: 0,1116
radix 0.004: 0,4
msb_radix 0.384: 0,384
twin 1.216: 0,1216
std_block_merge 1.572: 0,1572
comb 1.753: 0,1753
shell 2.443: 0,2444
section sorted
tim 0.008: 0,8
pdq 0.008: 0,8
quick 0.186: 0,186
radix 0.004: 0,4
msb_radix 0.252: 0,252
twin 0.059: 0,59
std_block_merge 0.056: 0,56
comb 0.398: 0,398
shell 0.274: 0,274
section reverse
tim 0.013: 0,13
pdq 0.039: 0,39
quick 0.399: 0,399
radix 0.004: 0,4
msb_radix 0.255: 0,255
twin 0.015: 0,15
std_block_merge 0.329: 0,329
comb 0.476: 0,476
shell 0.343: 0,343
section ascending saw
tim 0.362: 0,362
pdq 0.470: 0,470
quick 1.206: 0,1206
radix 0.004: 0,4
msb_radix 0.260: 0,260
twin 0.248: 0,248
std_block_merge 0.371: 0,371
comb 0.792: 0,792
shell 0.629: 0,629
section descending saw
tim 0.364: 0,364
pdq 0.468: 0,468
quick SKIPPED: 0
radix 0.004: 0,4
msb_radix 0.272: 0,272
twin 0.270: 0,270
std_block_merge 0.566: 0,566
comb 0.830: 0,830
shell 0.643: 0,643
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 |