diff options
author | iurii plugatarov <[email protected]> | 2024-07-29 22:51:24 +0200 |
---|---|---|
committer | iurii plugatarov <[email protected]> | 2024-07-29 22:51:24 +0200 |
commit | feebd54e3a6546a7c8b400a31d07fe8042899c39 (patch) | |
tree | 3f614d184778f5d7030cdbba4dfb3ad2d20af758 /src/sort | |
parent | e53093139c07804b99ac05689ebc6695b47ff919 (diff) | |
download | dsazitty-feebd54e3a6546a7c8b400a31d07fe8042899c39.tar.gz |
quck
Diffstat (limited to '')
-rw-r--r-- | src/sort/merge.zig | 2 | ||||
-rw-r--r-- | src/sort/quick.zig | 35 |
2 files changed, 35 insertions, 2 deletions
diff --git a/src/sort/merge.zig b/src/sort/merge.zig index e93b2bd..d392acf 100644 --- a/src/sort/merge.zig +++ b/src/sort/merge.zig @@ -31,8 +31,6 @@ 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" { diff --git a/src/sort/quick.zig b/src/sort/quick.zig new file mode 100644 index 0000000..598331e --- /dev/null +++ b/src/sort/quick.zig @@ -0,0 +1,35 @@ +const std = @import("std"); +const testing = std.testing; +const mem = std.mem; + +fn partition(comptime T: type, arr: []T, low: usize, high: usize) usize { + const pivot = arr[high]; + var i: usize = low; + + for (low..high) |j| { + if (arr[j] <= pivot) { + mem.swap(T, &arr[i], &arr[j]); + i += 1; + } + } + mem.swap(T, &arr[i], &arr[high]); + return i; +} + +pub fn sort(comptime T: type, arr: []T, low: usize, high: usize) void { + if (low < high) { + const pivot_index = partition(T, arr, low, high); + + if (pivot_index > low) { + sort(T, arr, low, pivot_index - 1); + } + sort(T, arr, pivot_index + 1, high); + } +} + +test "quick sort" { + var arr = [_]i32{ 64, 34, 25, 12, 22, 11, 90 }; + sort(i32, &arr, 0, arr.len - 1); + const expected = [_]i32{ 11, 12, 22, 25, 34, 64, 90 }; + try testing.expectEqualSlices(i32, &expected, &arr); +} |