정렬 알고리즘(삽입, 버블, 선택, 합병)의 초간단 이해

이 글에서 알 수 있는 것

• 데이터를 크기 순서대로 정리하는 정렬 알고리즘 알고리즘에 대해 알 수 있다.
• 삽입정렬, 버블정렬, 선택정렬, 합병정렬을 간단한 예제로 알 수 있다.
• 각 방법의 차이점을 직관적으로 알 수 있지만, 너무 간단하므로 각 알고리즘을 제대로 이해하는 데 충분하지 않을 수 있다.

정렬할 데이터 예시

• 다음 예시에 보이는 정렬 전 데이터를 다양한 삽입정렬, 버블정렬, 선택정렬, 합병정렬 알고리즘으로 오름차순 정렬한다.

색인	0	1	2	3	4
정렬 전 데이터	80	50	60	20	40

• 정렬 후의 데이터는 다음과 같은 모습을 기대할 수 있다.

정렬 후 데이터

20

40

50

60

80

삽입 정렬 insertion sort

1. 1-0 비교

   1<0 이라면 0에 삽입

   0번은 한칸뒤로

2. 2-0/2-1 비교

   나머지를 한칸씩 뒤로 이동

3. 3-0/3-1/3-2 비교
4. 4-0/4-1/4-2/4-1 비교

버블 정렬 bubble sort

1. 0-1/1-2/2-3/3-4 비교
2. 0-1/1-2/2-3 비교
3. 0-1/1-2 비교
4. 0-1 비교

선택 정렬 selection sort

1. 0-1/0-2/0-3/0-4 비교
2. 1-2/1-3/1-4 비교
3. 2-3/2-4 비교
4. 3-4 비교

합병 정렬 2-way merge sort

1. (0-1) / (2-3) / (4-5) / (6-7) 4묶음 안에서 비교
2. ( (0-1)-(2-3) ) / ( (4-5)-(6-7) ) 2묶음 안에서 비교
3. ( ( (0-1)(2-3) )-( (4-5)(6-7) ) 1묶음 안에서 비교