[방송대 알고리즘]정렬 알고리즘

정렬 알고리즘

1. 정렬의 개념

내부 정렬: 정렬할 데이터 전체가 속도가 빠르고 무작위 접근이 가능한 주기억장치에 있는 경우에 사용되는 정렬 방식

비교 기반 정렬 알고리즘: 데이터의 키값 전체를 직접적으로 비교하여 어떤 값이 큰지 또는 작은지를 결정하여 정렬을 수행하는 방식의 알고리즘

안정적 정렬 알고리즘: 동일한 값을 같는 데이터가 여러 개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 방식의 정렬 알고리즘

제자리 정렬: 데이터를 정렬함에 있어서 입력 데이터를 저장한 공간 이외에 별도로 필요한 저장 공간이 상수 개를 넘지 않는 정렬 알고리즘

내부 정렬 알고리즘

비교 기반 알고리즘

데이터의 값을 직접적으로 비교해서 정렬하는 알고리즘

키값의 비교 횟수를 가지고 성능을 판단함

• 버블, 선택, 삽입, 셸: O(n^2)
• 합병, 퀵, 힙: O(nlogn)

데이터 분포 기반 알고리즘

데이터의 분포 특성을 이용하여 정렬

데이터의 이동 횟수를 가지고 성능을 판단함

성능적으로 좋지만 일반성이 떨어져서 사용하기 힘듬

• 계수, 기수: O(n)

기본 개념

안정적 정렬

같은 데이터가 여러 개 있을 때, 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식

제자리 정렬

입력 데이터를 저장한 공간 이외의 추가적인 저장 공간을 상수 개만 필요로 하는 정렬 방식

• 입력 크기 n이 증가함에도 불구하고 추가적인 저장 공간은 증가하지 않음

2. 버블 정렬

모든 인접한 두 값을 비교하여 왼쪽의 값이 더 큰 경우에는 자리를 바꾸는 과정을 반복하여 정렬하는 방식

• O(n^2)
• 안정적 정렬 알고리즘
• 제자리 정렬 알고리즘

개선된 알고리즘 → exchange체크, 내부 for문 조건에 -i처리

3. 선택 정렬

주어진 데이터 중에서 가장 작은 값부터 차례대로 선택해서 나열

• 정렬되지 않은 데이터 중에서 가장 작은 값을 선택
• 선택된 값과 미정렬 데이터 부분의 첫 번째 원소와 교환
• 언제나 동일한 시간복잡도 O(n^2)
• 제자리 정렬 알고리즘
• 안정적이지 않은 정렬 알고리즘

4. 삽입 정렬

주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 형태를 갖도록 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식

• 입력 배열을 정렬 부분과 미정렬 부분으로 구분
• 미정렬 부분에서 첫 번째(아무)데이터를 뽑은 후,
• 정렬 부분에서 제자리를 찾아 뽑은 데이터를 삽입하는 과정을 반복
• 첫번째 데이터는 정렬되었다 가정하고 진행
• O(n^2)
• 역순으로 정렬된 경우 n^2, 정렬된 경우 n
• 안정적인 정렬 알고리즘
• 제자리 정렬 알고리즘
• 삽입된 위치를 찾기 위해 한 번에 한 자리씩만 이동 → 데이터의 이동이 여러 번 발생

5. 셀 정렬

삽입 정렬의 단점 보완(Donald L. Shell)

• 삽입 정렬 단점: 데이터가 삽입될 위치에서 멀리 떨어져 있어도 바로 왼쪽의 이웃한 데이터와의 비교를 통해 한번에 한 자리씩만 이동 → 제자리를 찾는데 느림
• 셀 정렬은 멀리 떨어진 데이터와 비교-교환해서 처리 속도 향상
• 처음에는 멀리 떨어진 두 데이터를 비교해서 필요시 위치 교환, 점차 가까운 위치의 데이터를 비교-교환, 맨 마지막에는 인접한 데이터를 비교-교환
• 입력 배열을 부분 배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜 가면서 반복
• D: 두 데이터 간의 거리이자 부분배열의 갯수
• 최악의 경우 O(n^2)
• 최선 O(nlogn)
• 간격의 크기 D를 계산하는 방식에 따라 성능이 달라짐
• 가장 좋은 간격을 찾는 것은 미해결 과제
• 제자리 정렬 알고리즘
• 안정적이지 않은 정렬 알고리즘

6. 합병 정렬과 퀵 정렬

합병 정렬

배열을 더이상 나눌 수 없을 때 까지 반으로 나눈 뒤, 합치며 정렬

• 언제나 O(nlogn)
• 안정적
• 제자리 정렬 알고리즘이 아님

퀵 정렬

피벗을 정한 다음 피벗이 제자리를 잡게 한 다음 왼쪽과 오른쪽으로 나누어 정렬

• 최악 O(n^2), 최선/평균 O(nlogn)
• 피벗 선택의 임의성만 보장되면 평균 성능을 보일 가능성이 매우 높음
• 일반적으로 가장 좋은 성능을 보여주는 알고리즘
• 안정적이지 않음
• 제자리 정렬이 아님

7. 힙 정렬

힙 자료구조의 장점을 활용한 정렬

힙

• 완전 이진 트리
• 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같다(최대힙)
• 임의의 값 삽입과 최대값 삭제가 용이
• 논리적으로는 트리지만, 구현시에는 배열로 구현

힙 정렬의 처리 과정

1단계: 1차원 배열 → 힙으로 변환

2단계: 힙의 최댓값 삭제 → 힙의 재구성

초기 힙 구축

1. 주어진 입력 배열의 각 원소에 대해 힙에서의 삽입 과정을 반복
2. 입력 배열을 완전 이진트리로 만든 후 아래에서 위, 오른쪽에서 왼쪽으로 진행하면서 각 노드에 대해 힙의 조건이 만족하도록 조정

최댓 값 삭제

최댓값과 루트노드의 자리를 바꾼 후, 최대값이 들어간 루트노드를 삭제한 노드 처리함

특징

• 항상 nlogn
• 바깥 루프 : n
• 안쪽 루프: logn
• 안정적이지 않음
• 제자리정렬

8. 비교 기반의 알고리즘의 하한

• 기본 성능 O(n^2): 버블, 선택, 삽입, 셸
• 향상된 성능 O(nlogn): 합병, 퀵, 힙

비교 기반 알고리즘의 하한은 O(nlogn)이다.

• 결정 트리로 증명

9. 계수 정렬

비교 기반이 아닌 데이터의 분포를 이용한 정렬 방식으로, 선형 시간을 가짐

• 주어진 원소 중에서 자신보다 작거나 같은 값을 갖는 원소의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방식
• 입력값이 어떤 작은 정수 범위 내에 있다는 것을 알고 있는 경우에만 적용 가능

각 수의 출현 횟수를 이용해 누적값을 구하고, 그 누적값을 통해 정렬을 수행

• 안정적인 정렬
• 제자리 정렬이 아님

10. 기수 정렬

입력값을 자릿수별로 부분적으로 비교하는 정렬

• 각 자릿수별로 계수 정렬과 같은 안정적인 정렬 알고리즘을 반복적으로 적용
• LSD(Least) 기수 정렬: 낮은 자리부터 높은 자리로 진행
• MSD(Most) 기수 정렬: 높은 자리부터 낮은 자리로 진행

특징

• 성능: O(dn)
• 입력 원소의 값의 자릿수(d)가 상수일 때 유용
• 안정적인 정렬 알고리즘
• 제자리 정렬 알고리즘이 아님