[JAVA/알고리즘] 삽입정렬(Insert sort)

삽입정렬

- 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번쨰와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 

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

- 배열에 7, 4, 2, 6, 1 이 저장되어있다고 가정 -> 오름차순 정렬

 

1회전 :

2회전 :

3회전 :

4회전 :

결과 :

- 소스코드

package sort;

public class InsertSort
{
	public static void insertSort(int[] num)
	{
		int tmp = 0;
		for (int i = 0; i < num.length - 1; i++)
		{
			for (int j = i + 1; j > 0; j--)
			{
				if (num[j] < num[j - 1])
				{
					tmp = num[j - 1];
					num[j - 1] = num[j];
					num[j] = tmp;
				}

			}
			for (int k = 0; k < num.length; k++)
			{
				System.out.print(num[k] + " ");
			}
			System.out.println();
		}

	}

	public static void main(String[] args)
	{
		int num[] = { 7, 4, 2, 6, 1 };

		insertSort(num);

	}
}

 

- 시간복잡도

데이터의 개수를 n개라고 가정한다면,

(n -1) + (n - 2) + ... + 2 + 1 => n(n - 1)/2이 되므로, O(n^2)만큼의 시간이 걸린다. 

하지만 삽입 정렬은 모두 정렬이 되어있는 경우에는 한 번씩만 비교를 하게 되므로 O(n)의 시간복잡도를 가지게 된다.