정렬 알고리즘

정렬(sort)

 정렬이란 컴퓨터 과학에서 가장 많이 사용되는 응용 중 하나로서, 주어진 데이터를 일정한 기준에 따라 재배열하는 연산이다. 정렬 방법은 정렬이 수행될 당시 데이터가 어디에 저장되어 있느냐에 따라 크게 내부 정렬(internal sort)과 외부 정렬(external sort)로 나눌 수 있다. 내부 정렬이란 정렬할 데이터의 양이 충분히 크지 않기 때문에 모든 데이터를 주기억장치에 적재해서 정렬하는 방법으로 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬 등이 있다. 한편 데이터가 많은 경우 전체 데이터를 보조기억장치에 저장하고 그 중 일부 데이터를 번갈아가며 주기억장치에 적재해서 정렬을 수행하는 방법을 외부 정렬이라고 하며, 대치선택 방법, 다단계 합병 정렬 등이 있다.

 

선택 정렬

 주어진 원소 중 가장 작은 키값을 갖는 원소를 선택하여 나열하는 정렬 방식이다. 먼저, 리스트 중 가장 작은을 찾고 그 값을 맨 왼쪽에 위치시킨다. 다음 맨 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체한다. 데이터 수가 적은 경우 효율적이며 시간 복잡도가 언제나 동일한 수행 시간인 О(n2) 이다. 즉 데이터의 입력 상태에 수행 시간이 민감하지 않다.

 

버블 정렬

주어진 리스트의 왼쪽에서부터 두 인접한 원소를 차례로 비교하여 왼쪽 값이 더 큰 경우 오른쪽과 자리바꿈을 해가며 정렬하는 방법이다. 인접한 두 개의 항목을 비교하는 방식으로 정렬하기 때문에 개념이 단순해서 프로그래밍하기 편하지만 선택 정렬보다 비교 작업이 많아서 연산 시간이 오래 걸리는 것이 단점이다.

 

삽입 정렬

정렬이 필요한 요소를 뽑아내어 이를 적당한 곳에 삽입하는 정렬 방식이다. 데이터 집합에서 두 번째 자료부터 시작해서, 정렬된 부분에서 오른쪽 끝에서부터 왼쪽으로 차례로 비교하며 적절한 위치에 삽입하는 방식의 과정을 반복하며 정렬을 수행한다. 시간 복잡도는 최선의 경우 О(n), 입력 자료가 역순일 경우 О(n2) 가 될 수 있다.

 

퀵 정렬

퀵 정렬은 평균적으로 가장 좋은 성능인 О(n log n)을 갖는 비교 기반 알고리즘이다. 퀵 정렬에서 리스트의 분할을 위한 특정한 키를 분할원소 또는 피벗(pivot)이라고 한다. 퀵 정렬은 피벗이 제자리를 잡도록 하여 정렬하는 방식이다. 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽으로, 큰 요소는 오른쪽으로 옮겨진다. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 더 이상 분할이 불가능할 때까지 반복하는 분할정복 방법이 적용된 정렬 알고리즘이다. 분할정복이란 정렬할 n개의 원소를 피벗을 기준으로 두 개의 서브리스트로 분할하고 두 서브리스트에 대해 퀵 정렬을 순환적으로 적용하여 두 서브리스트를 정렬하는 것을 의미한다.

 

합병 정렬

합병 정렬은 왼쪽 서브리스트와 오른쪽 서브리스트의 크기를 항상 같게 분할하고 각 서브리스트에 대해 다시 두개의 서브리스트로 분할하는 과정을 순환적으로 적용하여 왼쪽과 오른쪽 서브리스트에 대한 처리가 완료되면 이들을 합병하여 하나의 정렬된 리스트를 만드는 방식이다. 합병 정렬은 분할정복 방법 정렬 알고리즘으로, 정렬할 n개 원소를 n/2개의 원소를 갖는 두 서브리스트로 분할한다. 그리고 두 서브리스트에 대해 합병 정렬을 순환적으로 적용하여 두 서브리스트를 정렬한다. 정렬된 두 서브리스트를 합병하여 원래 정렬된 리스트를 만든다. 수행 시간은 언제나 O(n log n)이 된다.

 

References

컴퓨터과학개론 / KNOUPress, aladin.kr/p/gWrFz

컴퓨터과학개론 (워크북 포함)