about summary refs log tree commit diff
path: root/src
diff options
context:
space:
mode:
authoriurii plugatarov <[email protected]>2024-07-28 21:29:10 +0200
committeriurii plugatarov <[email protected]>2024-07-28 21:29:10 +0200
commit2b4414f8d8496d72ff904606dcf7c600257d3bd8 (patch)
treec1489d65b5ae91c4d96184be0d86083557075c67 /src
parenta679ae0a00adc299ab89efb69fad44ebab777d35 (diff)
downloaddsazitty-2b4414f8d8496d72ff904606dcf7c600257d3bd8.tar.gz
bench improve
Diffstat (limited to 'src')
-rw-r--r--src/benchmark.zig30
-rw-r--r--src/sort/shell.zig26
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);
+}