diff options
author | iurii plugatarov <[email protected]> | 2024-07-28 21:29:10 +0200 |
---|---|---|
committer | iurii plugatarov <[email protected]> | 2024-07-28 21:29:10 +0200 |
commit | 2b4414f8d8496d72ff904606dcf7c600257d3bd8 (patch) | |
tree | c1489d65b5ae91c4d96184be0d86083557075c67 | |
parent | a679ae0a00adc299ab89efb69fad44ebab777d35 (diff) | |
download | dsazitty-2b4414f8d8496d72ff904606dcf7c600257d3bd8.tar.gz |
bench improve
Diffstat (limited to '')
-rw-r--r-- | src/benchmark.zig | 30 | ||||
-rw-r--r-- | src/sort/shell.zig | 26 |
2 files changed, 35 insertions, 21 deletions
diff --git a/src/benchmark.zig b/src/benchmark.zig index 4c30609..c44fb11 100644 --- a/src/benchmark.zig +++ b/src/benchmark.zig @@ -4,6 +4,7 @@ const time = std.time; const bubble = @import("sort/bubble.zig"); const selection = @import("sort/selection.zig"); const insertion = @import("sort/insertion.zig"); +const shell = @import("sort/shell.zig"); const testing = std.testing; fn benchmark(comptime T: type, comptime sort_fn: fn (type, []T) void, n: usize, runs: usize) !u64 { @@ -24,32 +25,19 @@ fn benchmark(comptime T: type, comptime sort_fn: fn (type, []T) void, n: usize, return total_time / runs; } -test "bubble sort benchmark" { +fn run_bench(comptime T: type, comptime sort_fn: fn (type, []T) void, name: []const u8) !void { const runs = 10; const sizes = [_]usize{ 100, 1000, 10000 }; - std.debug.print("\nBubble Sort Benchmark:\n", .{}); + std.debug.print("\n{s} Benchmark:\n", .{name}); for (sizes) |size| { - const avg_time = try benchmark(i64, bubble.sort, size, runs); + const avg_time = try benchmark(T, sort_fn, size, runs); std.debug.print("Average time for N={d}: {d} ms\n", .{ size, avg_time }); } } -test "selection sort benchmark" { - const runs = 10; - const sizes = [_]usize{ 100, 1000, 10000 }; - std.debug.print("\nSelection Sort Benchmark:\n", .{}); - for (sizes) |size| { - const avg_time = try benchmark(i64, selection.sort, size, runs); - std.debug.print("Average time for N={d}: {d} ms\n", .{ size, avg_time }); - } -} - -test "insertion sort benchmark" { - const runs = 10; - const sizes = [_]usize{ 100, 1000, 10000 }; - std.debug.print("\nInsertion Sort Benchmark:\n", .{}); - for (sizes) |size| { - const avg_time = try benchmark(i64, insertion.sort, size, runs); - std.debug.print("Average time for N={d}: {d} ms\n", .{ size, avg_time }); - } +test "sorting benchmarks" { + try run_bench(i64, bubble.sort, "Bubble Sort"); + try run_bench(i64, selection.sort, "Selection Sort"); + try run_bench(i64, insertion.sort, "Insertion Sort"); + try run_bench(i64, shell.sort, "Shell Sort"); } diff --git a/src/sort/shell.zig b/src/sort/shell.zig new file mode 100644 index 0000000..7a2b338 --- /dev/null +++ b/src/sort/shell.zig @@ -0,0 +1,26 @@ +const std = @import("std"); +const mem = std.mem; +const testing = std.testing; + +pub fn sort(comptime T: type, arr: []T) void { + var gap = arr.len / 2; + + while (gap > 0) : (gap /= 2) { + var i: usize = gap; + while (i < arr.len) : (i += 1) { + const temp = arr[i]; + var j: usize = i; + while (j >= gap and arr[j - gap] > temp) : (j -= gap) { + arr[j] = arr[j - gap]; + } + arr[j] = temp; + } + } +} + +test "insertion sort test" { + var arr = [_]i64{ 20, 3, 5, 1, 30, 4, 2 }; + sort(i64, &arr); + const expected = [_]i64{ 1, 2, 3, 4, 5, 20, 30 }; + try testing.expectEqualSlices(i64, &expected, &arr); +} |