개념

삽입 정렬

삽입 정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

Python

import random

n = 20
a = [random.randrange(0, 40) for _ in range(n)]
print(" < origin >")
print(*a)

# Insertion Sort
**for i in range(1, n):
    v = a[i]
    j = i-1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = v**

print("\\n< Insertion Sort >")
print(*a)

C

Generalization

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

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

**void insertion_sort(
    void* base, int nelem, int width,
    int (*fcmp)(const void*, const void*)) {
    int i, j;
    void* t = malloc(width);
    for (i = 1; i < nelem; i++) {
        memcpy(t, (char*)base + i * width, width);
        j = i;
        while (j > 0 && fcmp((char*)base + (j - 1) * width, t) > 0) {
            memcpy((char*)base + (j)*width, (char*)base + (j - 1) * width, width);
            j--;
        }
        memcpy((char*)base + j * width, t, width);
    }
}**

int main() {
    srand((unsigned int)time(NULL));
    int i;
    int n = 20;
    int* a = (int*)calloc(n, sizeof(int));
    for (i = 0; i < n; i++) {
        a[i] = rand() % 50;
    }

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

    insertion_sort(a, n, sizeof(int), cmp);

    printf("\\n\\nsorted :\\n");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

#define으로 base문 간략히

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

#define BASE(base, idx) (char*)base + (idx)*width

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

void insertion_sort(
    void* base, int nelem, int width,
    int (*fcmp)(const void*, const void*)) {
    int i, j;
    void* t = malloc(width);
    for (i = 1; i < nelem; i++) {
        memcpy(t, BASE(base, i), width);
        j = i;
        while (j > 0 && fcmp(BASE(base, j - 1), t) > 0) {
            memcpy(BASE(base, j), BASE(base, j - 1), width);
            j--;
        }
        memcpy(BASE(base, j), t, width);
    }
}
int main() {
    srand((unsigned int)time(NULL));
    int i;
    int n = 20;
    int* a = (int*)calloc(n, sizeof(int));
    for (i = 0; i < n; i++) {
        a[i] = rand() % 50;
    }

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

    insertion_sort(a, n, sizeof(int), cmp);

    printf("\\n\\nsorted :\\n");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

C++

#include <ctime>
#include <iostream>
#include <random>

using namespace std;

**template <typename T>
void insertion_sort(T* a, int n) {
    for (int i = 1; i < n; i++) {
        T v = a[i];
        int j = i;
        while (j > 0 && a[j - 1] > v) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = v;
    }
}**

int main() {
    mt19937 mt((unsigned int)time(NULL));
    uniform_int_distribution<int> gen(0, 49);

    int n = 20;
    int* a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = gen(mt);
    }
    cout << "origin : \\n";
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    insertion_sort(a, n);
    cout << "\\n\\nsorted : \\n";
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
}

back_to_top