diff options
author | iurii plugatarov <[email protected]> | 2024-07-29 18:01:59 +0200 |
---|---|---|
committer | iurii plugatarov <[email protected]> | 2024-07-29 18:01:59 +0200 |
commit | 276ab86e8fdbe512cb6d7651456f700f75cc23af (patch) | |
tree | b75b3f4b62a05e4dc66d8213e750766c63728df2 | |
parent | 880ec046b805cd4f0b4c087de9a0916cf54c7896 (diff) | |
download | dsazitty-276ab86e8fdbe512cb6d7651456f700f75cc23af.tar.gz |
merge sort
-rw-r--r-- | src/benchmark.zig | 39 | ||||
-rw-r--r-- | src/sort/merge.zig | 44 |
2 files changed, 80 insertions, 3 deletions
diff --git a/src/benchmark.zig b/src/benchmark.zig index c44fb11..6781b5a 100644 --- a/src/benchmark.zig +++ b/src/benchmark.zig @@ -5,15 +5,18 @@ 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 merge = @import("sort/merge.zig"); const testing = std.testing; +const Allocator = std.mem.Allocator; 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 prng = Random.DefaultPrng.init(0); var random = prng.random(); + var allocator = testing.allocator; var total_time: u64 = 0; for (0..runs) |_| { - const list = try testing.allocator.alloc(T, n); - defer testing.allocator.free(list); + const list = try allocator.alloc(T, n); + defer allocator.free(list); for (list) |*item| { item.* = random.int(T); } @@ -25,6 +28,25 @@ fn benchmark(comptime T: type, comptime sort_fn: fn (type, []T) void, n: usize, return total_time / runs; } +fn benchmark_merge(comptime T: type, n: usize, runs: usize) !u64 { + var prng = Random.DefaultPrng.init(0); + var random = prng.random(); + var total_time: u64 = 0; + var allocator = testing.allocator; + for (0..runs) |_| { + const list = try allocator.alloc(T, n); + defer allocator.free(list); + for (list) |*item| { + item.* = random.int(T); + } + const start = time.milliTimestamp(); + try merge.sort(T, list, &allocator); + const end = time.milliTimestamp(); + total_time += @intCast(end - start); + } + return total_time / runs; +} + 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 }; @@ -35,9 +57,20 @@ fn run_bench(comptime T: type, comptime sort_fn: fn (type, []T) void, name: []co } } +fn run_bench_merge(comptime T: type, name: []const u8) !void { + const runs = 10; + const sizes = [_]usize{ 100, 1000, 10000 }; + std.debug.print("\n{s} Benchmark:\n", .{name}); + for (sizes) |size| { + const avg_time = try benchmark_merge(T, 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"); + try run_bench_merge(i64, "Merge Sort"); } diff --git a/src/sort/merge.zig b/src/sort/merge.zig new file mode 100644 index 0000000..e93b2bd --- /dev/null +++ b/src/sort/merge.zig @@ -0,0 +1,44 @@ +const std = @import("std"); +const mem = std.mem; +const testing = std.testing; +const Allocator = std.mem.Allocator; + +fn sort_helper(comptime T: type, arr: []T, aux: []T, low: usize, high: usize) void { + if (high - low <= 1) return; + const mid = low + (high - low) / 2; + sort_helper(T, arr, aux, low, mid); + sort_helper(T, arr, aux, mid, high); + merge(T, arr, aux, low, mid, high); +} + +fn merge(comptime T: type, arr: []T, aux: []T, low: usize, mid: usize, high: usize) void { + @memcpy(aux[low..high], arr[low..high]); + var i = low; + var j = mid; + var k = low; + while (k < high) : (k += 1) { + if (i < mid and (j == high or aux[i] <= aux[j])) { + arr[k] = aux[i]; + i += 1; + } else { + arr[k] = aux[j]; + j += 1; + } + } +} + +pub fn sort(comptime T: type, arr: []T, allocator: *Allocator) !void { + const aux = try allocator.alloc(T, arr.len); + defer allocator.free(aux); + sort_helper(T, arr, aux, 0, arr.len); + std.debug.print("aux: {any}\n", .{aux}); + std.debug.print("arr: {any}\n", .{arr}); +} + +test "optimized merge sort - basic test" { + var arr = [_]i64{ 20, 3, 5, 1, 30, 4, 2 }; + var allocator = testing.allocator; + try sort(i64, &arr, &allocator); + const expected = [_]i64{ 1, 2, 3, 4, 5, 20, 30 }; + try testing.expectEqualSlices(i64, &expected, &arr); +} |