정렬
정의
데이터를 ‘순서대로 배열’ 하는 일.
목적
탐색 편하게 하기 위해 정렬한다.
전제
‘순서’가 있어야 한다.
순서 정의
비교가능한 모든 속성.
$\Rightarrow$ 데이터 사이 ‘비교가능한 속성’ 있어야 정렬할 수 있다.
순서 예시
- 오름차순
- 내림차순
데이터셋 관점에서 본 정렬
예컨대 다음과 같은 데이터셋이 있다고 하자.
1
2
3
4
5
6
7
8
9
10
11
# 사이킷런 보스턴 집값 데이터셋
from sklearn.datasets import load_boston
data = load_boston()
data
df = pd.DataFrame(
data['data'], columns=data.feature_names
)
df
- 각 열: 레코드
- 각 행: 필드(field)
- 정렬 키(sort key): 정렬 기준이 되는 필드
정렬은 키 값 순서대로 레코드를 배열하는 것이다.
- 곧, 정렬 대상은 ‘레코드’다.
예컨대 정렬 키를 AGE 로 삼아 정렬한다고 가정하자.
그러면 AGE 값의 순서(예: 오름차순) 대로 각 행도 순서가 재배열 될 것이다.
정렬 알고리듬 분류, 평가 기준
상황별로 최적 정렬 알고리듬이 다르다. 상황에 따라 적합한 정렬 알고리듬 골라 사용하는 게 필요하다.
레코드 수 많고 적음, 레코드 크기 크고 작음, key 특성(문자, 정수, 실수 등) 등에 맞춰서 정렬 알고리듬을 선정한다.
정렬 알고리듬 분류 기준
1. 정렬 장소
- 내부 정렬: 모든 데이터가 주기억장치에 저장되어 있고, 정렬도 거기서 일어난다.
- 외부 정렬: 대부분 데이터가 외부기억장치, 일부가 주기억장치에 저장. 정렬이 외부기억장치에서 일어난다.
2. 효율성
- 단순하지만 낮은 효율성: 삽입, 선택, 버블정렬 등
- 복잡하지만 높은 효율성: 퀵, 힙, 병합, 기수정렬, 팀 등
3. 정렬 알고리듬의 안정성(Stability) 보장 유무
- 안정성 보장된 알고리듬: 정렬해도 키 값 같은 데이터들 사이 상대적 위치(들어온 순서)는 변치 않는다.
- 안정성 없는 알고리듬: 정렬하면 키 값 같은 데이터들 사이에도 상대적 위치 변한다(들어온 순서 유지 안 된다).
안정성 없는 알고리듬 예)
- 같은 키 값(10) 갖는 세 레코드가 정렬 후 순서가 뒤엉켰다.
- 안정성 보장된 알고리듬이었다면, 세 레코드의 들어온 순서가 정렬 후에도 유지되었을 것이다.
정렬 알고리듬 성능 평가 기준
1. 비교횟수
2. 이동횟수
선택 정렬(Selection Sort) 알고리듬
정의
배열의 정렬되지 않은 원소들 중 최솟값을 ‘선택’ 해서 정렬된 부분 바로 오른쪽 원소와 ‘교환’하는 정렬 알고리듬.
과정
1. 리스트 정렬된 부분과 정렬 안 된 부분
- 맨 처음에는 정렬된 부분 없음.
- 모두 정렬 안 된 상태다.
2. 정렬 안 된 부분에서 최솟값 선택, 정렬 안 된 부분 첫번째 원소와 교환
- 정렬 된 부분 크기 1 증가한다.
- 정렬 안 된 부분 크기 1 감소한다.
3. 정렬 안 된 부분 원소가 모두 사라지면 정렬 완료
선택 정렬 수행 예
선택 정렬 성능
비교연산 시간복잡도
매 루프 마다 배열의 정렬 안 된 부분에서 최솟값 찾는다.
- 맨 처음 루프에서 최솟값 찾기 위해 값들 간 비교 횟수: $N-1$
- 두번째 루프에서 최솟값 찾기 위해 값들 간 비교 횟수: $N-2$
- 마지막 루프에서 최솟값 찾기 위해 값들 간 비교 횟수: $1$ (2개 값 비교해서 1개 최솟값 찾는다)
$\Rightarrow$ 총 비교 횟수 $=$ $(N-1)+(N-2)+(N-3)+…+2+1 = \frac{N(N-1)}{2}$
$\Rightarrow$ 비교연산 시간복잡도 $= O(N^{2})$
따라서 선택 정렬 총 시간복잡도는 $O(N^{2})$
선택 정렬 특징
- 항상 $O(N^{2})$ 시간복잡도가 보장된다.
- 선택 정렬 할 때 i값 - 최솟값 사이 총 교환 횟수는 $N-1$ 이다. 모든 정렬 알고리듬 중 가장 적은 원소 교환 횟수다.
- 정렬 알고리듬 안정성 보장하지 않는다. 곧, 정렬하면. 같은 키 값 갖는 원소들 사이 들어온 순서. 유지되지 않는다.
효율성 떨어진다. 거의 이용하지 않는다 ($O(N^{2})$).
선택 정렬 알고리듬 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 선택 정렬 알고리듬 정의
def selection_sort(A) :
n = len(A) #정렬 안 된 원소 개수
for i in range(n-1) : # 오른쪽 리스트 첫번째 값
minimum = i
for j in range(i+1, n) :
if A[j] < A[minimum] :
minimum = j
A[i], A[minimum] = A[minimum], A[i] # 오른쪽 리스트 첫번째 값 - 최솟값 교환
printStep(A, i+1) # 정렬 결과 출력
# 몇 번째 선택 정렬 루프인가. 그리고 그 루프 정렬 결과 출력 정의
def printStep(arranged, loop) :
print(f'{loop}번째 루프 정렬 결과 =', end=' ')
print(arranged)
리스트 예
1
data = [5,3,8,4,9,1,6,2,7]
위 리스트를 정의된 선택 정렬 알고리듬으로 정렬시키기
1
2
3
4
print('정렬 전:', data)
selection_sort(data)
print()
print('선택정렬 후', data)
정렬 전: [5, 3, 8, 4, 9, 1, 6, 2, 7]
1번째 루프 정렬 결과 = [1, 3, 8, 4, 9, 5, 6, 2, 7]
2번째 루프 정렬 결과 = [1, 2, 8, 4, 9, 5, 6, 3, 7]
3번째 루프 정렬 결과 = [1, 2, 3, 4, 9, 5, 6, 8, 7]
4번째 루프 정렬 결과 = [1, 2, 3, 4, 9, 5, 6, 8, 7]
5번째 루프 정렬 결과 = [1, 2, 3, 4, 5, 9, 6, 8, 7]
6번째 루프 정렬 결과 = [1, 2, 3, 4, 5, 6, 9, 8, 7]
7번째 루프 정렬 결과 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
8번째 루프 정렬 결과 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
선택정렬 후 [1, 2, 3, 4, 5, 6, 7, 8, 9]