10906：字符串列表多视图排序

题目

只重排字符串指针，分别支持字典次序、全文长度次序和首个单词长度次序，并保持等价项的原有相对次序。

解析

三个排序规则最终都归结为一个比较函数。长度不能通过相减后转换为 int 来比较，因为较大的 size_t 差值可能超出 int 范围；应分别判断大于和小于。

稳定插入排序只在左侧元素严格大于待插入元素时移动指针。比较结果为 0 时立即停止，因此等价项不会越过彼此。排序前先验证枚举值和全部字符串指针，失败分支不会改动数组。

解析

#include <stdbool.h>
#include <stddef.h>
#include <ctype.h>
#include <string.h>

typedef enum {
    LINE_ORDER_LEXICOGRAPHIC,
    LINE_ORDER_LENGTH,
    LINE_ORDER_FIRST_WORD_LENGTH
} LineOrder;

static int compare_size(size_t left, size_t right) {
    return (left > right) - (left < right);
}

static size_t first_word_length(const char *line) {
    const unsigned char *cursor =
        (const unsigned char *)line;

    while (*cursor != '\0' && isspace((int)*cursor)) {
        ++cursor;
    }

    size_t length = 0;
    while (*cursor != '\0' && !isspace((int)*cursor)) {
        ++length;
        ++cursor;
    }
    return length;
}

static int compare_lines(
    const char *left,
    const char *right,
    LineOrder order
) {
    if (order == LINE_ORDER_LEXICOGRAPHIC) {
        return strcmp(left, right);
    }

    if (order == LINE_ORDER_LENGTH) {
        int result = compare_size(
            strlen(left),
            strlen(right)
        );
        return result != 0 ? result : strcmp(left, right);
    }

    int result = compare_size(
        first_word_length(left),
        first_word_length(right)
    );
    if (result != 0) {
        return result;
    }

    result = compare_size(strlen(left), strlen(right));
    return result != 0 ? result : strcmp(left, right);
}

bool order_lines(
    const char *lines[],
    size_t count,
    LineOrder order
) {
    if (order != LINE_ORDER_LEXICOGRAPHIC
        && order != LINE_ORDER_LENGTH
        && order != LINE_ORDER_FIRST_WORD_LENGTH) {
        return false;
    }
    if (count > 0 && lines == NULL) {
        return false;
    }

    for (size_t i = 0; i < count; ++i) {
        if (lines[i] == NULL) {
            return false;
        }
    }

    for (size_t i = 1; i < count; ++i) {
        const char *line = lines[i];
        size_t position = i;

        while (
            position > 0
            && compare_lines(
                lines[position - 1],
                line,
                order
            ) > 0
        ) {
            lines[position] = lines[position - 1];
            --position;
        }
        lines[position] = line;
    }

    return true;
}