[정보처리기사] 2024 2차 실기 대비 - 자료 구조 정렬(Sort)

1️⃣ 삽입 정렬(Insertion Sort)

8

5

6

2

4

위와 같이 5개의 데이터를 저장하는 배열이 있다고 가정하고, 해당 배열을 삽입 정렬 방식으로 정렬해
보도록 하자. 삽입 정렬은 0번 인덱스가 아닌 1번 인덱스부터 시작한다는 점을 기억하도록 하자.
시험에서는 특정 정렬을 n회전 수행했을 경우 배열의 상태를 물어보는 경우가 대부분이기 때문에
정렬이 완료되기까지의 모든 과정을 살펴보도록 하겠다.

1회전
1번 인덱스(5)와 0번 인덱스(8)을 비교. 5가 더 작으니 8과 5를 교환.

5

8

6

2

4

 

2회전
1회전에서 1번 인덱스의 비교를 진행하였으니, 2번 인덱스(6)과 0번 인덱스(5)를 비교한다.
해당 비교에서 교환이 없으니 2번 인덱스(6)와 1번 인덱스(8)을 비교 후 6이 더 작으니 교환한다.

5

6

8

2

4

 

3회전
3번 인덱스(2)와 0번 인덱스(5)를 비교한다. 이때, 2가 5보다 작으니 교환을 해야 한다고 생각할 수 있지만
2번 인덱스까지는 정렬이 완료된 상태라는 점을 떠올리자. 즉, 현재 0번 인덱스인 5는 2번 인덱스까지 저장된
값들과 비교했을 때 가장 작은 값이라는 의미이다. 그러니 5보다 작은 2를 0번 인덱스에 저장하고, 나머지
값들을 한 칸씩 뒤로 밀기만 하면, 자동으로 정렬이 완료될 것이다.

2

5

6

8

4

 

4회전
마지막 인덱스인 4도 위 과정과 동일하게 끼워넣으면 해당 배열을 삽입 정렬 방식으로 정렬이 완료된다.

2

4

5

6

8

 

2️⃣ 선택 정렬(Selection Sort)

선택 정렬도 아래의 배열을 예로 들어가며, 이해해 보도록 하겠다.

8

5

6

2

4

선택 정렬은 교환이 일어나더라도 중단하지 않고, 해당 인덱스부터 마지막 인덱스까지 전부 비교를 한다.

1회전
즉, 현재 0번 인덱스인 8부터 마지막 인덱스인 4까지 비교를 진행하는 것인데, 직접 살펴보도록 하겠다.
0번과 1번 비교, 5가 8보다 작으니 교환하여 {5, 8, 6, 2, 4}와 같은 형태가 된다.
새롭게 0번이 된 5와 2번 인덱스인 6을 비교한다. 해당 과정에선 교환이 일어나지 않는다.
0번(5)과 3번(2)를 비교한다. 교환이 일어나 {2, 8, 6, 5, 4}가 된다.
0번(2)와 4번(4)를 비교한다. 교환이 일어나지 않고, 1회전의 최종 배열 상태는 아래와 같아진다.

2

8

6

5

4

 

2회전
1회전에서 배열의 0번 인덱스에 최소값이 저장되었으니, 1번 인덱스부터 위 과정을 반복한다.
선택 정렬은 각 회전 당 0번 인덱스부터 순차적으로 최소값이 저장되기에 별로 어려울 것이 없다.
1번(8)과 2번(6) 비교 후 교환 발생 {2, 6, 8, 5, 4}
1번(6)과 3번(5) 비교 후 교환 발생 {2, 5, 8, 6, 4}
1번(5)와 4번(4) 비교 후 교환 발생 {2, 4, 8, 6, 5}

2

4

8

6

5

 

3회전
2번(8)과 3번(6) 비교 후 교환 발생 {2, 4, 6, 8, 5}
2번(6)과 4번(5) 비교 후 교환 발생 {2, 4, 5, 8, 6}

2

4

5

8

6

 

4회전
3번(8)과 4번(6) 비교 후 교환 발생. 마지막 교환이 일어나며 선택 정렬 방식으로의 정렬도 완료됐다.

2

4

5

6

8

3️⃣ 버블 정렬(Bubble Sort)

0번 인덱스부터 최소값을 순차적으로 저장하는 삽입 정렬과 선택 정렬과는 달리 버블 정렬은
마지막 인덱스에 최대값부터 역순으로 저장되는 정렬 방식이다. 예시를 통해 살펴보자.

8

5

6

2

4

1회전
0번(8)과 1번(5) 비교 후 8이 5보다 크니 교환이 발생한다. {5, 8, 6, 2, 4}
1번(8)과 2번(6)을 비교 후 교환 발생 {5, 6, 8, 2, 4}
2번(8)과 3번(2)을 비교 후 교환 발생 {5, 6, 2, 8, 4}
3번(8)과 4번(4)을 비교 후 1회전 종료

5

6

2

4

8

 

2회전
1회전을 통해 마지막 인덱스에 최대값이 저장됐으니, 2회전은 0번부터 3번까지의 비교만 진행한다.
0번(5)과 1번(6) 비교, 교환 발생되지 않음
1번(6)과 2번(2) 비교 후 교환 발생 {5, 2, 6, 4, 8}
2번(6)과 3번(4) 비교 후 교환 발생 {5, 2, 4, 6, 8}

5

2

4

6

8

 

3회전
0번(5)과 1번(2) 비교 후 교환 발생 {2, 5, 4, 6, 8}
1번(5)와 2번(4) 비교 후 교환 발생 {2, 4, 5, 6, 8}

2

4

5

6

8

4회전
0번(2)과 1번(4) 비교, 교환 발생되지 않으며 버블 정렬 종료

2

4

5

6

8

 

---

📝 Reference

👉 길벗 2023 시나공 퀵이지 정보처리기사실기 교재 참조

👉 https://www.youtube.com/watch?v=KqtZoMWd75o

👉 Claude 3.5 Sonnect, GPT 4o 답변 참조