[CS50] 선택 정렬, 삽입 정렬

선택 정렬

보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있다. 정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

 

 

실행

우리에게 5, 1, 6, 2, 4, 3이란 배열이 주어지고 선택 정렬을 이용하여 정렬해줘야 한다면 의사 코드를 <코드 1>과 같이 만들 수 있을 것이다.

코드 1

① 프로그램은 array라는 배열의 첫 번째 자리(5)에서 시작한다. 

② 가장 작은 원소를 찾기 위해 5를 (1, 6, 2, 4, 3)와 비교한다.

③ 1이 가장 작은 값이기 때문에 5의 위치와 교환한다.

④ 이제 1은 정렬되었으며 나머지 5, 6, 2, 4, 3은 여전히 정렬되지 않은 상태이다.

⑤ 다음은 두 번째 자리(5)인데, 정렬되지 않은 오른쪽(6, 2, 4, 3) 부분만 확인하면 된다.

⑥ 2가 정렬되지 않은 배열의 원소 중 가장 작은 원소이므로 5와 자리를 바꿔준다.

⑦ 이와 같은 방식으로 계속해서 비교와 교환을 반복한다.

 

step 5에 이르면 우리는 배열이 정렬되었다는 것을 알 수 있지만 컴퓨터는 우리처럼 큰 그림을 볼 수 없다는 것을 알아야 한다. 따라서 step6으로 넘어가 5와 6의 크기 비교까지 마친 후에야 알고리즘이 종료된다.

 

 

정렬된 배열

버블 정렬과는 다르게 몇 번의 교환을 해주었는지 횟수를 셀 필요가 없다. 하지만 이 과정은 우리가 해야 할 비교 횟수보다 훨씬 더 많은 비교가 필요하므로 비용이 많이 든다. 원래 배열의 순서와 상관없이, 선택 정렬로 정렬되는 배열은 n-1번의 교환이 필요하다. n-1번의 교환은 확실히 버블 정렬의 교환 횟수보다는 적다. 그러나 한 번의 교환이 일어나기 위해서는 정렬되지 않은 수의 모든 비교가 이루어져야 하므로, n²번의 비교가 이루어 진다. 선택 정렬은 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교와 교환을 해주어야 한다.

 

------------------

 

삽입 정렬

자료를 정렬하는 또 다른 알고리즘 중 하나인데, 자료를 여러 번 비교하거나 교환할 필요가 없는 방법이 있다. 삽입정렬은 자료가 정렬된 부분과 정렬되지 않은 부분으로 나누어진다. 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법이다.

 

 

실행

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분, 두 개의 부분으로 나누면서 동작한다. 만약 5, 1, 6, 2, 4, 3 이라는 값을 삽입정렬을 이용하여 정렬해주어야 한다면 <코드 1>과 같이 의사코드를 작성할 수 있다.

코드 1

① 프로그램이 실행되었을 때, array라는 배열의 첫 번째 자리(5)는 이미 정렬된 부분이라고 간주한다.

② 정렬되지 않은 부분의 맨 앞 자리인 1은 5보다 작기 때문에 5는 오른쪽으로 이동하고 1이 첫 번째 자리로 온다.

③ 다음으로 정렬되지 않은 부분의 6을 살펴본다.

④ 6은 5보다 크기 때문에 이동할 필요가 없다.

⑤ 같은 방식으로 계속 실행하면 전체 값이 모두 정렬되다.

그림 1

 

정렬된 배열

삽입 정렬은 특정 실행 단계에서, 어떤 원소가 정렬된 배열 내에 자리를 찾았다고 해서 그것이 최종적인 제자리라는 보장은 없다. 다음 단계가 진행되면서 다른 자료에 의해 위치가 바뀔 수 있기 때문이다. 따라서 삽입 정렬은 자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬이 되어있는 경우 효율적이다. 삽입정렬은 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮다.