Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted

Inline

@@ Line 10,325: / Line 10,325: @@
 Full example with test/debug data for ZX Spectrum is at [[https://gist.github.com/ped7g/0c4e94796b474994ed88d0bdd1bf2f25 github]].
-=={{header|zig}}==
+=={{header|Zig}}==
+{{trans|Rust}}
+'''Works with:''' 0.10.x, 0.11.x, 0.12.0-dev.1390+94cee4fb2
 <syntaxhighlight lang="zig">const std = @import("std");
-pub fn quicksort(comptime t: type, arr: []t) void {
+pub fn quickSort(comptime T: type, arr: []T, comptime compareFn: fn (T, T) bool) void {
     if (arr.len < 2) return;
-    var pivot = arr[@as(usize, @intFromFloat(@floor(@as(f64, @floatFromInt(arr.len)) / 2)))];
-    var left: usize = 0;
-    var right: usize = arr.len - 1;
+    const pivot_index = partition(T, arr, compareFn);
-    while (left <= right) {
+    quickSort(T, arr[0..pivot_index], compareFn);
-        while (arr[left] < pivot) {
+    quickSort(T, arr[pivot_index + 1 .. arr.len], compareFn);
-            left += 1;
+}
-        }
-        while (arr[right] > pivot) {
+fn partition(comptime T: type, arr: []T, comptime compareFn: fn (T, T) bool) usize {
-            right -= 1;
-        }
+    const pivot_index = arr.len / 2;
+    const last_index = arr.len - 1;
-        if (left <= right) {
-            const tmp = arr[left];
-            arr[left] = arr[right];
+    std.mem.swap(T, &arr[pivot_index], &arr[last_index]);
-            arr[right] = tmp;
-            left += 1;
+    var store_index: usize = 0;
+    for (arr[0 .. arr.len - 1]) |*elem_ptr| {
-            right -= 1;
+        if (compareFn(elem_ptr.*, arr[last_index])) {
+            std.mem.swap(T, elem_ptr, &arr[store_index]);
+            store_index += 1;
         }
     }
-    quicksort(t, arr[0 .. right + 1]);
+    std.mem.swap(T, &arr[store_index], &arr[last_index]);
+    return store_index;
-    quicksort(t, arr[left..]);
+}</syntaxhighlight>
-}
+<syntaxhighlight lang="zig">const std = @import("std");
-pub fn main() !void {
-    const LIST_TYPE = i16;
-    var arr: [10]LIST_TYPE = [_]LIST_TYPE{ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 };
-    var i: usize = 0;
+pub fn main() void {
-    while (i < arr.len) : (i += 1) {
-        std.debug.print("{d} ", .{arr[i]});
+    const print = std.debug.print;
-    }
-    std.debug.print("\n", .{});
+    var arr = [_]i16{ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 };
-    i = 0;
-    quicksort(LIST_TYPE, &arr);
+    print("Before: {any}\n\n", .{arr});
-    while (i < arr.len) : (i += 1) {
-        std.debug.print("{d} ", .{arr[i]});
+    print("Sort numbers in ascending order.\n", .{});
+    quickSort(i16, &arr, struct {
-    }
+        fn sortFn(left: i16, right: i16) bool {
-    std.debug.print("\n", .{});
+            return left < right;
+        }
+    }.sortFn);
+    print("After: {any}\n\n", .{arr});
+    print("Sort numbers in descending order.\n", .{});
+    quickSort(i16, &arr, struct {
+        fn sortFn(left: i16, right: i16) bool {
+            return left > right;
+        }
+    }.sortFn);
+    print("After: {any}\n\n", .{arr});
 }</syntaxhighlight>
 {{out}}
 <pre>
-65 2 -31 0 99 2 83 782 1
+Before: { 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 }
--31 0 1 2 2 4 65 83 99 782
+Sort numbers in ascending order.
+After: { -31, 0, 1, 2, 2, 4, 65, 83, 99, 782 }
+Sort numbers in descending order.
+After: { 782, 99, 83, 65, 4, 2, 2, 1, 0, -31 }
 </pre>