From feebd54e3a6546a7c8b400a31d07fe8042899c39 Mon Sep 17 00:00:00 2001
From: iurii plugatarov <plugatariov@gmail.com>
Date: Mon, 29 Jul 2024 23:51:24 +0300
Subject: quck

---
 src/benchmark.zig  | 31 +++++++++++++++++++++++++++++++
 src/sort/merge.zig |  2 --
 src/sort/quick.zig | 35 +++++++++++++++++++++++++++++++++++
 3 files changed, 66 insertions(+), 2 deletions(-)
 create mode 100644 src/sort/quick.zig

(limited to 'src')

diff --git a/src/benchmark.zig b/src/benchmark.zig
index 6781b5a..b264b1c 100644
--- a/src/benchmark.zig
+++ b/src/benchmark.zig
@@ -6,6 +6,7 @@ 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 quick = @import("sort/quick.zig");
 const testing = std.testing;
 const Allocator = std.mem.Allocator;
 
@@ -47,6 +48,25 @@ fn benchmark_merge(comptime T: type, n: usize, runs: usize) !u64 {
     return total_time / runs;
 }
 
+fn benchmark_quick(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();
+        quick.sort(T, list, 0, list.len - 1);
+        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 };
@@ -57,6 +77,16 @@ fn run_bench(comptime T: type, comptime sort_fn: fn (type, []T) void, name: []co
     }
 }
 
+fn run_bench_quick(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_quick(T, size, runs);
+        std.debug.print("Average time for N={d}: {d} ms\n", .{ size, avg_time });
+    }
+}
+
 fn run_bench_merge(comptime T: type, name: []const u8) !void {
     const runs = 10;
     const sizes = [_]usize{ 100, 1000, 10000 };
@@ -73,4 +103,5 @@ test "sorting benchmarks" {
     try run_bench(i64, insertion.sort, "Insertion Sort");
     try run_bench(i64, shell.sort, "Shell Sort");
     try run_bench_merge(i64, "Merge Sort");
+    try run_bench_quick(i64, "Quick Sort");
 }
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);
+}
-- 
cgit 1.4.1-2-gfad0