about summary refs log tree commit diff
path: root/src/sort
diff options
context:
space:
mode:
authoriurii plugatarov <[email protected]>2024-07-29 22:51:24 +0200
committeriurii plugatarov <[email protected]>2024-07-29 22:51:24 +0200
commitfeebd54e3a6546a7c8b400a31d07fe8042899c39 (patch)
tree3f614d184778f5d7030cdbba4dfb3ad2d20af758 /src/sort
parente53093139c07804b99ac05689ebc6695b47ff919 (diff)
downloaddsazitty-feebd54e3a6546a7c8b400a31d07fe8042899c39.tar.gz
quck
Diffstat (limited to 'src/sort')
-rw-r--r--src/sort/merge.zig2
-rw-r--r--src/sort/quick.zig35
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);
+}