Code Review: String sorting

Help
, ,
1

Hello everyone,

I am new to the zig language and trying toy exercises like string_sorting etc.
I would like to get my below code reviewed, please feel free to let me know any and every improvement I can make to it.

const std = @import("std");

pub fn main() void {
    const str = "cbawdd";
    std.debug.print("unsorted: {s}\n", .{str});
    const sort_str = sort_string(str);
    std.debug.print("sorted: {s}\n", .{sort_str});
}

fn sort_string(ss: []const u8) [6]u8 {
    // Function to sort the given 6 characters string.
    // in an ascending order.

    // Make the immutable string into mutable string
    // so that it can be manipulated.
    var buf: [6]u8 = undefined;
    for (0..ss.len) |i| {
        buf[i] = ss[i];
    }

    // sort the string
    for (0..buf.len) |i| {
        for (0..i) |k| {
            const j = i - k;
            if (buf[j] < buf[j - 1]) {
                const tmp = buf[j];
                buf[j] = buf[j - 1];
                buf[j - 1] = tmp;
            }
        }
    }
    return buf;
}

I do have a few questions:

  1. The above only works for six character strings, how can I make it to work with a string of any length?
  2. In the sort_string function I have to first make []const u8 to a mutable [6]u8 type and to do so I read we can use allocator too, which method is better the above for loop or the allocator one?
  3. As the str const is a pointer to the actual bytes cbawdd, I would like to edit the actual string using the pointer instead of storing it in a new const (sort_str), how can I do so?

Please let me know your thoughts.

Cheers,
DD.

1 Like
2

Hello,
For sorting strings of an arbitrary length, you are gonna want to allocate memory on the heap (or write the string into a pre-reserved mutable buffer; it doesn’t really matter which).
std.mem.sortUnstable should be perfect for your purposes, since it always sorts in-place (and doesn’t preserve order of equal elements, unlike std.mem.sort).

Here’s an example test I wrote:

pub fn sort_chars(_: void, lhs: u8, rhs: u8) bool {
	return lhs < rhs;
}

test sort_chars {
	const str = try std.testing.allocator.dupe(u8, "cbawdd");
	defer std.testing.allocator.free(str);
    std.debug.print("unsorted: {s}\n", .{str});
	std.mem.sortUnstable(u8, str, {}, sort_chars);
    std.debug.print("sorted: {s}\n", .{str});
}

It’s also worth noting that you don’t need to use a for-loop to write your slice into a fixed buffer; you can just do this:

var buf: [6]u8 = undefined;
@memcpy(buf, ss[0..6]); // We slice the string to ensure it never copies out of bounds

This will automatically be optimised with SIMD instructions if possible.
Though, the compiler will probably vectorise your for-loop anyway, since it doesn’t have any side effects.

If you want to alter the sorting implementation such that uppercase characters are considered equal to lowercase characters, you can simply alter the sort_chars function from the test.

1 Like