CamelAct

Overview

손안의 카드를 정렬하는 방법과 유사하다.
새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.
새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

장점
안정한 정렬 방법
레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

단점
비교적 많은 레코드들의 이동을 포함한다.
레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

Usecase

  - 오브젝트의 정렬이 필요할 때

  - Best T(n) = O(n)
  - Worst T(n) = O(n^2)

Structure

Code Example

package com.algorithm.basic;

public class MyInsertSort {
	void insertionSort(int[] input) {
		for (int i = 1; i < input.length; i++) {
			int temp = input[i]; 		// 7
			int j = i - 1; 				// 0

			while ((j >= 0) && (temp < input[j])) {		// j = 0 && 7 < 8
				input[j + 1] = input[j];
				j = j - 1;
			}
			input[j + 1] = temp;
		}
	}

	void printResult(int[] input) {
		int i;

		for (i = 0; i < input.length; ++i) {
			System.out.print(input[i] + " ");
		}
		System.out.println();
	}

	public static void main(String arg[]) throws Exception {
		MyInsertSort myInsertSort = new MyInsertSort();

		int[] input = { 8, 7, 9, 6, 0, 1, 2, 3, 5, 4 };

		myInsertSort.insertionSort(input);

		myInsertSort.printResult(input);
	}
}

Console Result

0 1 2 3 4 5 6 7 8 9

Conclusion

N/A