sounio-benchmarks/030_insertion_sort.sio at main · Sounio-lang/sounio-benchmarks · GitHub

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//@ run-pass
// HumanEval 030: Insertion Sort
//
// Sort an integer array in ascending order using insertion sort.
// For each element, shift it left until it finds its correct position.
// Uses struct wrapper for &! mutation.

struct SortBuf { data: [i64; 256] }

fn insertion_sort(buf: &!SortBuf, n: i64) with Mut, Panic {
    var i: i64 = 1
    while i < n {
        let key = buf.data[i]
        var j = i - 1
        while j >= 0 && buf.data[j] > key {
            buf.data[j + 1] = buf.data[j]
            j = j - 1
        }
        buf.data[j + 1] = key
        i = i + 1
    }
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [5, 3, 1, 4, 2] -> [1, 2, 3, 4, 5]
    var b1 = SortBuf { data: [0; 256] }
    b1.data[0] = 5
    b1.data[1] = 3
    b1.data[2] = 1
    b1.data[3] = 4
    b1.data[4] = 2
    insertion_sort(&!b1, 5)
    assert(b1.data[0] == 1)
    assert(b1.data[1] == 2)
    assert(b1.data[2] == 3)
    assert(b1.data[3] == 4)
    assert(b1.data[4] == 5)

    // Test 2: already sorted [1, 2, 3] -> [1, 2, 3]
    var b2 = SortBuf { data: [0; 256] }
    b2.data[0] = 1
    b2.data[1] = 2
    b2.data[2] = 3
    insertion_sort(&!b2, 3)
    assert(b2.data[0] == 1)
    assert(b2.data[1] == 2)
    assert(b2.data[2] == 3)

    // Test 3: reverse sorted [5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
    var b3 = SortBuf { data: [0; 256] }
    b3.data[0] = 5
    b3.data[1] = 4
    b3.data[2] = 3
    b3.data[3] = 2
    b3.data[4] = 1
    insertion_sort(&!b3, 5)
    assert(b3.data[0] == 1)
    assert(b3.data[1] == 2)
    assert(b3.data[2] == 3)
    assert(b3.data[3] == 4)
    assert(b3.data[4] == 5)

    // Test 4: single element [42] -> [42]
    var b4 = SortBuf { data: [0; 256] }
    b4.data[0] = 42
    insertion_sort(&!b4, 1)
    assert(b4.data[0] == 42)

    // Test 5: duplicates [3, 1, 3, 1, 2] -> [1, 1, 2, 3, 3]
    var b5 = SortBuf { data: [0; 256] }
    b5.data[0] = 3
    b5.data[1] = 1
    b5.data[2] = 3
    b5.data[3] = 1
    b5.data[4] = 2
    insertion_sort(&!b5, 5)
    assert(b5.data[0] == 1)
    assert(b5.data[1] == 1)
    assert(b5.data[2] == 2)
    assert(b5.data[3] == 3)
    assert(b5.data[4] == 3)

    // Test 6: negative values [3, -1, 0, -5, 2] -> [-5, -1, 0, 2, 3]
    var b6 = SortBuf { data: [0; 256] }
    b6.data[0] = 3
    b6.data[1] = 0 - 1
    b6.data[2] = 0
    b6.data[3] = 0 - 5
    b6.data[4] = 2
    insertion_sort(&!b6, 5)
    assert(b6.data[0] == 0 - 5)
    assert(b6.data[1] == 0 - 1)
    assert(b6.data[2] == 0)
    assert(b6.data[3] == 2)
    assert(b6.data[4] == 3)

    // Test 7: two elements [10, 5] -> [5, 10]
    var b7 = SortBuf { data: [0; 256] }
    b7.data[0] = 10
    b7.data[1] = 5
    insertion_sort(&!b7, 2)
    assert(b7.data[0] == 5)
    assert(b7.data[1] == 10)

    // Test 8: larger array [9,7,5,3,1,2,4,6,8,0] -> [0,1,2,3,4,5,6,7,8,9]
    var b8 = SortBuf { data: [0; 256] }
    b8.data[0] = 9
    b8.data[1] = 7
    b8.data[2] = 5
    b8.data[3] = 3
    b8.data[4] = 1
    b8.data[5] = 2
    b8.data[6] = 4
    b8.data[7] = 6
    b8.data[8] = 8
    b8.data[9] = 0
    insertion_sort(&!b8, 10)
    assert(b8.data[0] == 0)
    assert(b8.data[1] == 1)
    assert(b8.data[2] == 2)
    assert(b8.data[3] == 3)
    assert(b8.data[4] == 4)
    assert(b8.data[5] == 5)
    assert(b8.data[6] == 6)
    assert(b8.data[7] == 7)
    assert(b8.data[8] == 8)
    assert(b8.data[9] == 9)

    println("030_insertion_sort: ALL TESTS PASSED")
    0
}