From a679ae0a00adc299ab89efb69fad44ebab777d35 Mon Sep 17 00:00:00 2001
From: iurii plugatarov <plugatariov@gmail.com>
Date: Sun, 28 Jul 2024 22:07:00 +0300
Subject: init

---
 src/benchmark.zig      | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++
 src/main.zig           |  3 +++
 src/root.zig           |  0
 src/sort/bubble.zig    | 20 ++++++++++++++++++
 src/sort/insertion.zig | 19 +++++++++++++++++
 src/sort/selection.zig | 22 ++++++++++++++++++++
 6 files changed, 119 insertions(+)
 create mode 100644 src/benchmark.zig
 create mode 100644 src/main.zig
 create mode 100644 src/root.zig
 create mode 100644 src/sort/bubble.zig
 create mode 100644 src/sort/insertion.zig
 create mode 100644 src/sort/selection.zig

(limited to 'src')

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
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);
+}
-- 
cgit 1.4.1-2-gfad0