정보올림피아드 초등 - 지역예선] 2010년도 8번문제

 

8.30, 15, 10, 25, 5, 20을 인접한 두 수들만 교환하여 5, 10, 15, 20, 25, 30과 같이 크기 순서대로 정렬하고자 한다. 최소 교환 횟수는 얼마인가? ①8 ②10 ③11 ④12 ⑤13

문제풀이)

여기서 정렬 알고리즘을 살펴 본다.

정렬 알고리즘으로는 다음과 같은 방식이 있다.

선택정렬

버블정렬

삽입정렬

퀵정렬

합병정렬

각각의 정렬 방식을 간단하게 살펴 보면

선택 정렬은 기준 선택 후 최소값을 찾아서 기준값과 교환하는 방식

위의 자료를 선택 정렬로 정렬 하는 방식은

30을 기준 선택 후 최소값 5 와 위치를 바꾼다. 5,15,10,25,30,20 

그리고 15를 기준 선택 후 최소값 10과 순서를 바꾼다. 5,10,15,25,30,20

다시 15를 기준 선택 후 최소값이 15보다 크므로 기준 선택 변경 하여

25를 기준 선택 후 최소값 20과 순서를 바꾼다. 5,10,15,20,30,25

30을 기준 선택 후 최소값 25와 순서를 바꾼다. 5,10,15,20,25,30

하지만 인접한 두수를 교환하는 방식이 아니므로 선택 정렬은 맞지 않다.

버블정렬은 작은 순서대로 인접한 값과 비교하여 정렬 한다.

위의 자료를 버블정렬로 정렬 하는 경우

1) 30, 15, 10, 25, 5, 20 ->  15, 30, 10, 25, 5, 20 -> 15, 10, 30, 25, 5, 20  -> 15, 10, 25, 30,5, 20 -> 15, 10, 25, 5, 30, 20  -> 15, 10, 25, 5, 20, 30   

2) 15, 10, 25, 5,20,30 -> 10,15,25, 5,20,30 -> 10,15,5, 25, 20,30 -> 10,15,5, 20,25,30

3) 10,15,5, 20,25,30 -> 10,5,15,20,25,30  

4) 10,5,15,20,25,30 -> 5,10,15,20,25,30

삽입정렬은 하나씩 선택 하여 삽입 하는 형태

1) 30

2) 15,30

3) 10,15,30

4) 10,15,25,30

5) 5, 10,15,25,30

6) 5, 10,15,20,25,30

=> 하지만 인접한 두수를 교환하는 방식이 아니므로 삽입정렬은 맞지 않다.

퀵정렬은 기준으로 하여 작은 수는 왼쪽으로 큰수는 오른쪽으로 보내는 정렬 방식

위의 자료를 퀵정렬로 정렬 하는 경우

1) 30(i), 15, 10, 25, 5(j), 20(p)  -> 5(i), 15, 10, 25, 30(j), 20(p) -> 5, 15(i), 10, 25(j), 30, 20(p) -> 5, 15, 10, 20(p), 25, 30

2) 피벗을 기준으로 5, 15, 10 / 25, 30 각각 퀵정렬로 다시 정렬 한다.

=> 하지만 인접한 두수를 교환하는 방식이 아니므로 퀵정렬은 맞지 않다.

합병정렬은 주어진 수를 2로 나누어 최종 2개의 데이터만 남을 때까지 나눈 후 합병 하면서 정렬 한다.

위의 자료를 합병정렬로 정렬 하는 경우

1) 30, 15, 10, 25, 5, 20 -> 30, 15, 10 /25, 5, 20  -> 30 / 15,10 // 25 / 5,20  ( 분리하는 과정)

2) 30 / 15,10 // 25 / 5,20  -> 30 / 10,15 // 25 / 5,20  -> 10,15,30 / 5.20.25 -> 5,10,15,20,25,30 

 

참고) 인접한 두수를 교환하는 방식은 버블정렬임

따라서 버블정렬 방식으로 정렬시 교환 횟수는 10회

정답) 2번