삽입 정렬(Insertion Sort)

삽입정렬은 배열을 정렬된 부분, 정렬되지 않은 부분으로 나눈 후, 원소를 순차적으로 탐색하면서 해당 원소를 정렬이 된 부분에 끼워 넣는 정렬입니다.

맨 처음 원소(1)를 정렬되었다고 가정한 후, 정렬되지 않은 다음 원소(2)를 정해 최근에 정한 원소(1)와 비교한 후 크다면 (1)의 오른쪽에 그렇지 않다면 그 자리에 그대로 정렬합니다.

시간복잡도는 각 원소에 대해 적당한 위치를 찾아주어야 하므로 총 원소의 개수 O( N ), 순차적으로 삽입 위치를 찾는데 O( N )이 들므로 O(N²)으로 힙정렬이나 합병정렬에 비해 비효율적(O(N log N))으로 잘 쓰이지 않습니다.

다음은 C++로 나타낸 코드입니다.

#include <iostream>
#define MAX 5005
using namespace std;

int d[MAX], n;

int main() {

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}

	for (int i = 0; i < n; i++) {
		int temp = d[i];
		int j = i - 1;
		for (; j >= 0; j--) {
			if (d[j] < temp)
				break;
			d[j + 1] = d[j];
		}
		d[j + 1] = temp;
	}

	for (int i = 0; i < n; i++)
		cout << d[i] << “ “;

	return 0;
}

다음은 Java로 나타낸 코드입니다.

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] d = new int[5005];
        for (int i = 0; i < n; i++)
            d[i] = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            int temp = d[i];
            int j = i - 1;

            for (; j >= 0; j--) {
                if (d[j] < temp)
                    break;
                d[j + 1] = d[j];
            }

            d[j + 1] = temp;
        }

        for (int i = 0; i < n; i++)
            System.out.print(d[i] + " ");
    }
}

다음 시간엔 버블정렬에 대해 알아보겠습니다.