Rosetta Code

Sorting algorithms/Quicksort: Difference between revisions

Page Discussion

Sorting algorithms/Quicksort (view source)

Revision as of 04:53, 4 November 2023

656 bytes added ,  6 months ago
→‎{{header|zig}}: new version based on Rust, with generic comparator function, annotate versions
imported>Rcmlz
(→‎{{header|zig}}: new version based on Rust, with generic comparator function, annotate versions)
Line 10,325:
Full example with test/debug data for ZX Spectrum is at [[https://gist.github.com/ped7g/0c4e94796b474994ed88d0bdd1bf2f25 github]].
 
=={{header|zigZig}}==
 
{{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 quicksortquickSort(comptime tT: type, arr: []tT, 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;
▲ varconst right: usizelast_index = arr.len - 1;
if (left <= right) {▼
 
const tmp = arr[left];
std.mem.swap(T, &arr[leftpivot_index], = &arr[rightlast_index]);
 
arr[right] = tmp;
var store_index: usize left += 10;
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]);
▲ leftstore_index += 1;
}
}
 
quicksortstd.mem.swap(tT, &arr[0store_index], .. right + 1&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) {
const print = std.debug.print("{d} ", .{arr[i]});
}▼
std.debug.print("\n", .{});▼
 
▲ var arr: [10]LIST_TYPE = [_]LIST_TYPEi16{ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 };
i = 0;
quicksortprint(LIST_TYPE"Before: {any}\n\n", &.{arr});
 
while (i < arr.len) : (i += 1) {
print("Sort numbers in ascending stdorder.debug.print("{d} \n", .{arr[i]});
quickSort(i16, &arr, struct {
}
▲ iffn sortFn(left: <=i16, right: i16) bool {
std.debug.print("\n", .{});▼
▲ while ( return left <= right) {;
▲ }
}.sortFn);
▲ std.debug.print("After: {any}\n\n", .{arr});
 
print("Sort numbers in descending order.\n", .{});
quickSort(i16, &arr, struct {
fn sortFn(left: i16, right: i16) bool {
▲ rightreturn -=left 1> right;
▲ }
}.sortFn);
▲ std.debug.print("After: {any}\n\n", .{arr});
}</syntaxhighlight>
 
{{out}}
<pre>
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>
 
BratishkaErik
28

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/348469"