[알고리즘] 삽입정렬

필요한 변수

int[6] arr = {6, 3, 4, 5, 1, 2}; // 정렬이 안된 배열

int tmp; // arr[i]를 임시로 담아둘 공간

int i = 1; // arr[i]를 탐색할 index번호. 0번은 비교 대사이 없으므로 1번부터 시작

int j; // arr[i]와 비교할 arr[j]의 index번호

슈도코드(오름차순)

아래 코드를 계속 반복

// step 1
tmp = arr[i] // 탐색 대상 임시저장

// step 2
for(j = i-1; j >= 0; j--){
    if(arr[j] > tmp) arr[j+1] = arr[j]; // 한 칸씩 오른쪽으로 이동
    else break;	
}

// step 3
arr[j+1] = tmp; // step 2에서 마지막으로 탐색한 자리에 tmp를 삽입

슈도코드(내림차순)

아래 코드를 계속 반복

// step 1
tmp = arr[i] // 탐색 대상 임시저장

// step 2
for(j = i-1; j >= 0; j--){
    if(arr[j] < tmp) arr[j+1] = arr[j]; // 한 칸씩 오른쪽으로 이동
    else break;	
}

// step 3
arr[j+1] = tmp; // step 2에서 마지막으로 탐색한 자리에 tmp를 삽입

전체코드(오름차순)

#include<iostream>

using namespace std;

int main() {
    int N = 6;
    int arr[6] = { 6, 3, 4, 5, 1, 2 }; // 정렬이 안된 배열

    // 1부터 시작(0번은 비교 대상이 없으므로)
    // arr[i]을 전부 탐색
    for (int i = 1; i < N; i++) {
        // step 1
        int tmp = arr[i]; // arr[i]를 임시로 담아둘 공간

        // step 2
        int j{};
        for (j = i - 1; j >= 0; j--) { // arr[i]와 비교할 arr[j]의 index번호
            if (arr[j] > tmp) arr[j + 1] = arr[j]; // 한 칸씩 오른쪽으로 이동
            else break;
        }

        // step 3
        arr[j + 1] = tmp; // step 2에서 마지막으로 탐색한 자리에 tmp를 삽입
    }

    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}

전체코드(내림차순)

#include<iostream>

using namespace std;

int main() {
    int N = 6;
    int arr[6] = { 6, 3, 4, 5, 1, 2 }; // 정렬이 안된 배열

    // 1부터 시작(0번은 비교 대상이 없으므로)
    // arr[i]을 전부 탐색
    for (int i = 1; i < N; i++) {
        // step 1
        int tmp = arr[i]; // arr[i]를 임시로 담아둘 공간

        // step 2
        int j{};
        for (j = i - 1; j >= 0; j--) { // arr[i]와 비교할 arr[j]의 index번호
            if (arr[j] < tmp) arr[j + 1] = arr[j]; // 한 칸씩 오른쪽으로 이동
            else break;
        }

        // step 3
        arr[j + 1] = tmp; // step 2에서 마지막으로 탐색한 자리에 tmp를 삽입
    }

    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}

예제(오름차순)

1. i = 1일 때 : arr[1] = 3

step 1 : tmp = 3 // tmp = arr[i]

step 2 : for(j = 0 ~ 0) // for(j = i-1; j >= 0; j--)

j = 0일 때 : arr[0] == 6
- (6 > 3)이므로 arr[0+1] = arr[0] // if(arr[j] > tmp) arr[j+1] = arr[j];
- j = -1 // j--

step 3 : 현재 j = -1

arr[0] = tmp(=3) // arr[j+1] = tmp;

2. i = 2일 때 : arr[2] = 4

step 1 : tmp = 4 // tmp = arr[i]

step 2 : for(j = 1 ~ 0) // for(j = i-1; j >= 0; j--)

j = 1일 때 : arr[1] == 6
- (6 > 4)이므로 arr[1+1] = arr[1] // if(arr[j] > tmp) arr[j+1] = arr[j];
j = 0일 때 : arr[0] == 6
- (3 > 4)이 아니므로 break // else break;

step 3 : 현재 j = 0

arr[1] = tmp(=4) // arr[j+1] = tmp;

3. i = 3일 때 : arr[3] = 5

step 1 : tmp = 5 // tmp = arr[i]

step 2 : for(j = 2 ~ 0) // for(j = i-1; j >= 0; j--)

j = 2일 때 : arr[2] == 6
- (6 > 5)이므로 arr[2+1] = arr[2] // if(arr[j] > tmp) arr[j+1] = arr[j];
j = 1일 때 : arr[1] == 4
- (4 > 5)이 아니므로 break // else break;