程式語言 - LeetCode - C - 注意事項 - Sort

參考資訊：
https://cplusplus.com/reference/cstdlib/qsort/
https://stackoverflow.com/questions/17202178/c-qsort-with-dynamic-n-by-2-multi-dimensional-array

使用C語言刷題時，可以使用qsort()做排序，qsort()預設使用QuickSort演算法，時間複雜度是n*log(n)

一維陣列用

#include <stdio.h>
#include <stdlib.h>

int mysort(const void *a, const void *b)
{
    return (*(const int *)a - *(const int *)b);
}
 
int main(int argc, char *argv[])
{
    int i = 0;
    int len = 6;
    int buf[] = { 40, 10, 100, 90, 20, 25 };
 
    qsort(buf, len, sizeof(int), mysort);

    for (i = 0; i < len; i++) {
        printf("%d\n", buf[i]);
    }

    return 0;
}

排序結果

10
20
25
40
90
100

二維陣列用法

#include <stdio.h>
#include <stdlib.h>

int mysort(const void *pa, const void *pb)
{
    const int** a = (const int**)pa;
    const int** b = (const int**)pb;

    if (a[0][0] == b[0][0]) {
        return a[0][1] - b[0][1];
    }

    return a[0][0] - b[0][0];
}
 
int main(int argc, char *argv[])
{
    int i = 0;
    int len = 6;
    int **buf = NULL;
 
    buf = malloc(sizeof(int *) * len);
 
    for (i = 0; i < len; i++) {
        buf[i] = malloc(sizeof(int) * 2);
    }
 
    buf[0][0] = 1;
    buf[0][1] = 7;
    buf[1][0] = 1;
    buf[1][1] = 3;
    buf[2][0] = 3;
    buf[2][1] = 10;
    buf[3][0] = 3;
    buf[3][1] = 100;
    buf[4][0] = 5;
    buf[4][1] = 200;
    buf[5][0] = 5;
    buf[5][1] = 10;
 
    qsort(buf, len, sizeof(int *), mysort);

    for (i = 0; i < len; i++) {
        printf("buf[%d][0]=%d\n", i, buf[i][0]);
        printf("buf[%d][1]=%d\n", i, buf[i][1]);
    }

    return 0;
}

排序結果

buf[0][0]=1
buf[0][1]=3
buf[1][0]=1
buf[1][1]=7
buf[2][0]=3
buf[2][1]=10
buf[3][0]=3
buf[3][1]=100
buf[4][0]=5
buf[4][1]=10
buf[5][0]=5
buf[5][1]=200

如果遇到runtime error: signed integer overflow: -2147483646 - 2147483646 cannot be represented in type 'int'，則改成如下：

int mysort(const void *pa, const void *pb)
{
    long r = 0;
    const int **a = pa;
    const int **b = pb;

    r = (long)a[0][0] - b[0][0];
    if (r == 0) {
        r = (long)a[0][1] - b[0][1];
    }

    if (r < 0) {
        r = -1;
    }

    if (r > 0) {
        r = 1;
    }

    return r;
}