Yuan's blog

刘沛源的博客

0%

插入排序

发表于 更新于 Disqus：
本文字数： 335 阅读时长 ≈ 1 分钟

插入排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// insertion.c

#include <stddef.h>
#include <stdio.h>

void insertion_sort(int *arr, size_t arrsiz)
{
        printf("\n"); // 避免同一行刷新排序进度时覆盖其他程序输出
        for(int target_index=0; target_index < arrsiz; target_index++)
        {
                int target_value = arr[target_index];
                int compare_index = target_index - 1;
                while(compare_index >= 0 && target_value < arr[compare_index])
                {
                        arr[compare_index + 1] = arr[compare_index];
                        --compare_index;
                }
                arr[compare_index + 1] = target_value;
                printf("\r\033[k");
                printf("Progress: %d / %ld", target_index, arrsiz);
        }
        printf("\r\033[k"); // 同一行刷新排序进度
        printf("                                                                                                               ");
        printf("\r\033[k"); // 清空刷新内容，避免干扰后续输出
}

效率测试框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// sort.c

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

void sort(void (*func)(int*, size_t))
{
        const size_t lens[5] = {10, 100, 10000, 100000, 1000000};
        for (size_t ind = 0; ind < 5; ind++) {
                int arr[lens[ind]];
                srand(0);
                printf("[SORT array_size=%lu]\n", lens[ind]);
                time_t gen_start_time, gen_end_time, sort_start_time, sort_end_time;
                gen_start_time = time(NULL);
                for (size_t jnd = 0; jnd < lens[ind]; jnd++)
                {
                        arr[jnd] = rand() % lens[ind];
                }
                gen_end_time = time(NULL);
                printf("\tgen_time: %ld\n", gen_end_time - gen_start_time);

                // output the first origin array to ensure the alg is correct
                if(ind == 0) {
                        printf("\t\tORIGION ARRAY: [");
                        for (size_t jnd = 0; jnd < lens[ind]; jnd++)
                        {
                                printf(" %d,", arr[jnd]);
                        }
                        printf("\b]\n");
                }

                sort_start_time = time(NULL);
                func(arr, lens[ind]);
                sort_end_time = time(NULL);
                printf("\tsort_time: %ld\n", sort_end_time - sort_start_time);

                // output the first sorted array to ensure the alg is correct
                if(ind == 0) {
                        printf("\t\tSORTED ARRAY: [");
                        for (size_t jnd = 0; jnd < lens[ind]; jnd++)
                        {
                                printf(" %d,", arr[jnd]);
                        }
                        printf("\b]\n");
                }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// sort_test.c

#include <stddef.h>
#include <stdio.h>

void insertion_sort(int *arr, size_t arrsiz);
void sort(void (*func)(int*, size_t));

int main()
{
        printf(">>> INSERTION SORT >>>\n");
        sort(&insertion_sort); 
        printf(">>> INSERTION SORT >>>\n");
}

测试结果

>>> INSERTION SORT >>>
[SORT array_size=10]
    gen_time: 0
        ORIGION ARRAY: [ 3, 6, 7, 5, 3, 5, 6, 2, 9, 1]
    sort_time: 0                                                              
        SORTED ARRAY: [ 1, 2, 3, 3, 5, 5, 6, 6, 7, 9]

[SORT array_size=100]
    gen_time: 0
    sort_time: 0                                                                               

[SORT array_size=10000]
    gen_time: 0
    sort_time: 0                                                                         

[SORT array_size=100000]
    gen_time: 0
    sort_time: 7                                                                         

[SORT array_size=1000000]
    gen_time: 0
    sort_time: 750