diff options
Diffstat (limited to '')
-rw-r--r-- | src/benchmark.zig | 55 | ||||
-rw-r--r-- | src/main.zig | 3 | ||||
-rw-r--r-- | src/root.zig | 0 | ||||
-rw-r--r-- | src/sort/bubble.zig | 20 | ||||
-rw-r--r-- | src/sort/insertion.zig | 19 | ||||
-rw-r--r-- | src/sort/selection.zig | 22 |
6 files changed, 119 insertions, 0 deletions
diff --git a/src/benchmark.zig b/src/benchmark.zig new file mode 100644 index 0000000..4c30609 --- /dev/null +++ b/src/benchmark.zig @@ -0,0 +1,55 @@ +const std = @import("std"); +const Random = std.Random; +const time = std.time; +const bubble = @import("sort/bubble.zig"); +const selection = @import("sort/selection.zig"); +const insertion = @import("sort/insertion.zig"); +const testing = std.testing; + +fn benchmark(comptime T: type, comptime sort_fn: fn (type, []T) void, n: usize, runs: usize) !u64 { + var prng = std.rand.DefaultPrng.init(0); + var random = prng.random(); + var total_time: u64 = 0; + for (0..runs) |_| { + const list = try testing.allocator.alloc(T, n); + defer testing.allocator.free(list); + for (list) |*item| { + item.* = random.int(T); + } + const start = time.milliTimestamp(); + sort_fn(T, list); + const end = time.milliTimestamp(); + total_time += @intCast(end - start); + } + return total_time / runs; +} + +test "bubble sort benchmark" { + const runs = 10; + const sizes = [_]usize{ 100, 1000, 10000 }; + std.debug.print("\nBubble Sort Benchmark:\n", .{}); + for (sizes) |size| { + const avg_time = try benchmark(i64, bubble.sort, 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 }); + } +} diff --git a/src/main.zig b/src/main.zig new file mode 100644 index 0000000..13ab026 --- /dev/null +++ b/src/main.zig @@ -0,0 +1,3 @@ +const std = @import("std"); + +pub fn main() !void {} diff --git a/src/root.zig b/src/root.zig new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/src/root.zig diff --git a/src/sort/bubble.zig b/src/sort/bubble.zig new file mode 100644 index 0000000..5d868a2 --- /dev/null +++ b/src/sort/bubble.zig @@ -0,0 +1,20 @@ +const std = @import("std"); +const mem = std.mem; +const testing = std.testing; + +pub fn sort(comptime T: type, arr: []T) void { + for (0..arr.len - 1) |i| { + for (i + 1..arr.len) |j| { + if (arr[i] > arr[j]) { + mem.swap(T, &arr[i], &arr[j]); + } + } + } +} + +test "bubble_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.expectEqual(expected, arr); +} diff --git a/src/sort/insertion.zig b/src/sort/insertion.zig new file mode 100644 index 0000000..4aee57a --- /dev/null +++ b/src/sort/insertion.zig @@ -0,0 +1,19 @@ +const std = @import("std"); +const mem = std.mem; +const testing = std.testing; + +pub fn sort(comptime T: type, arr: []T) void { + for (1..arr.len) |i| { + var j = i; + while (j > 0 and arr[j - 1] > arr[j]) : (j -= 1) { + mem.swap(T, &arr[j - 1], &arr[j]); + } + } +} + +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); +} diff --git a/src/sort/selection.zig b/src/sort/selection.zig new file mode 100644 index 0000000..0629680 --- /dev/null +++ b/src/sort/selection.zig @@ -0,0 +1,22 @@ +const std = @import("std"); +const mem = std.mem; +const testing = std.testing; + +pub fn sort(comptime T: type, arr: []T) void { + for (0..arr.len - 1) |i| { + var min = i; + for (i + 1..arr.len) |j| { + if (arr[min] > arr[j]) { + min = j; + } + } + mem.swap(T, &arr[i], &arr[min]); + } +} + +test "selection 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.expectEqual(expected, arr); +} |