정렬(Sort)에서 삽입 정렬(Insertion Sort)와 버블 정렬(Bubble Sort)

● 정렬이란?

  - 어떠한 데이터를 키 값에 따라 오름차순 혹은 내림차순으로 재배치를 하는 것이며

    오름차순은 키 값이 작은 것에서 큰 것으로 오른다!라고 생각하면 이해가 쉽다.

    반대로 내림차순은 큰 것에서 작은 것으로 내린다!라고 생각하자. (정렬방향은 위에서 아래로)

 

● 정렬 방식에는 2가지가 있다.

   1. 내부 정렬

      - Insertion, Shell, Selection, Bubble, Quick, Heap, 2-Way Merge, Radix, Bucket

   2. 외부 정렬

      - Balanced merge sort, Cascade merge sort, Polyphase merge sort, Oscillation merge sort

 

여기서 Insertion과 Bubble 정렬에 대해 비교하고자 한다.

 

- 삽입 정렬(Insertion Sort)은 임의로 선택된 키 값을 앞에 키값과 비교하여 위치를 찾아가는 방식이다.

최 초	4	3	6	5	1	2
1 회	3	4	6	5	1	2
2 회	3	4	6	5	1	2
3 회	3	4	5	6	1	2

 초록색 부분이 비교하는 키값들이고 빨간색이 위치를 찾아간 것이다. 지금은 키 값이 앞으로 한 칸만 변경되었지만 두 칸도 가능하다.

 

- 버블 정렬(Bubble Sort)은 인접키와 비교 후 교환하여 정렬한다. 단계별로 수행한다.

최 초	4	8	5	9	3	10
1 회	4	8	5	9	3	10
2 회	4	5	8	9	3	10
3 회	4	5	8	9	3	10

 위와 마찬가지로 초록색 부분이 비교하는 키값이고 빨간색이 위치를 찾아간 것이다. 주의할 점은 좌우로 한 칸만 변경된다는 것이다.

 

예를 들어

최 초	7	2	6	4	10	1
1 회	2	7	6	4	10	1
2 회	2	6	7	4	10	1
3 회	2	6	4	7	10	1
3 - 1 회	2	4	6	7	10	1

  3회는 버블 정렬이고 3-1회는 삽입 정렬이다. 3-1회를 보면 4가 앞으로 두칸 위치를 이동한 것이 보인다. 이러한 부분이 체크를 못할 가

  능성이 있으니 확인이 필요하다.