3강. 정렬 ( 1 )

1. 정렬이란?

• 주어진 데이터를 값의 크기 순서에 따라 재배치하는 것
  • ex ) 오름차순, 내림차순
• 정렬 구분
  • 기준 : 정렬 수행 시점에 데이터가 어디에 저장되어 있는가?
  • 내부 정렬
    • 전체 데이터를 주기억장치에 저장한 후 정렬을 수행하는 방식
  • 외부 정렬
    • 모든 데이터를 주기억장치에 저장할 수 없는 경우,
    • 모든 데이터를 보조기억장치에 저장해 두고
    • 그중 일부 데이터만을 반복적으로 주기억장치로 옮겨와서 정렬을 수행하는 방식

2. 내부 정렬 알고리즘

• 비교 기반 알고리즘 : 키값의 비교 횟수
  • O(n2)
    • 선택 정렬
    • 버블 정렬
    • 삽입 정렬
    • 셸 정렬
  • O(nlogn)
    • 퀵 정렬
    • 합병 정렬
    • 힙 정렬
• 데이터 분포 기반 알고리즘 : 데이터의 이동 횟수
  • O(n)
    • 계수 정렬
    • 기수 정렬
    • 버킷 정렬

3. 정렬관련 개념

• 안정적 정렬 ( Stable )
  • 동일한 값을 갖는 데이터가 여러 개 있을 때 정렬 전의 상대적 위치가 정렬 후에도 그대로 유지되는 정렬
  • ex ) 30 A 20 B 10 → 10 A B 20 30
• 제자리 정렬 ( In-Place )
  • 입력 배열 이외에 별도로 필요한 저장 공간이 상수 개를 넘지 않는 정렬
  • 입력 크기 𝑛이 증가함에도 불구하고 추가적인 저장 공간은 증가하지 않음

4. 정렬 알고리즘의 기본 가정

• 입력 배열 : A[0..n-1]
• 입력 크기 : n
• 입력 데이터 : 양의 정수
• 정렬 방식 : 오름차순

5. 선택 정렬이란?

• 입력 배열에서 가장 작은 값부터 순서대로 ‘선택’해서 나열하는 방식

6. 선택 정렬의 처리 과정

• ① 미정렬 부분 A[𝑖... 𝑛 − 1]에서 최솟값 찾기
• ② 최솟값과 데이터 A[𝑖]와 위치 교환
• 이를 n-1번 반복

for (i=0; i < n-1; i++) { // (n-1)번 반복
	min = i;
	for (j=i+1; j < n; j++) { // ① A[i..n-1]에서 최솟값 찾기
		if (A[min] > A[j]) {
			min = j;
			A[i]와 A[min]의 자리바꿈; // ② 최소값과 A[i]의 위치 교환
		}
	}
}

7. 선택 정렬의 성능과 특징

• 반복문을 중첩하여 사용
  • iter문 안에 iter 문이 한번 더 있다.
  • 총 n(n-1)/2번 비교하기에 → O(n2)
• 입력 데이터의 순서에 민감하지 않음
  • 최소값 찾기 → 미정렬 부분 A[i..n-1]에서 항상 (n-1)-i번의 비교가 필요
  • 입력 데이터의 상태와 상관없이 항상 동일한 성능 **O(n2)**을 가짐
• 제자리 정렬 알고리즘
  • 입력 배열 A[ ] 이외에 상수 개의 저장 공간( 예 : i, j, min, tmp )만 필요
  • 반복문에서 사용할 i와 j, 최솟값을 저장할 min, 그리고 자리 교환을 위한 tmp변수만 필요
• 안정적이지 않은 정렬 알고리즘

8. 버블 정렬이란?

• 모든 인접한 두 데이터를 차례대로 비교해서 왼쪽 데이터가 더 큰 경우에는 오른쪽 데이터와 자리를 바꾸는 과정을 반복해서 정렬을 수행하는 방식
• 비교를 진행하는 방식
  • 왼쪽에서 오른쪽으로 진행
    • 가장 큰 값부터 찾아서 오른쪽 끝에서부터 위치시킴
  • 오른쪽에서 왼쪽으로 진행
    • 가장 작은 값부터 찾아서 왼쪽 끝에서부터 위치시킴

9. 기본 형태의 버블 정렬 알고리즘 과정

• 왼쪽에서 오른쪽으로 진행하는 경우 ‘왼쪽 데이터 > 오른쪽 데이터’이면 자리 교환
• 이를 n-1번 반복

for (i=0; i < n-1; i++) { // 단계: (n-1)번 반복
    for (j=0; j < n-1; j++) { // 왼쪽에서 오른쪽으로 진행하는 경우
        if (A[j] > A[j+1]) { // ‘왼쪽 데이터 > 오른쪽 데이터’이면
            A[j]와 A[j+1]의 자리바꿈; 
        }
	}	
}

10. 버블 정렬 성능과 특징

• 반복문을 중첩하여 사용
  • iter문 안에 iter 문이 한번 더 있다.
  • 총 (n-1) * (n-1)번 비교하기에 → O(n2)
• 안정적인 정렬 알고리즘
  • 인접한 두 데이터가 동일한 경우 → 위치 교환이 미발생
• 제자리 정렬 알고리즘
  • 입력 배열 A[ ] 이외에 상수 개의 저장 공간( 예 : i, j, tmp )만 필요
  • 반복문에서 사용할 i와 j, 최솟값을 저장할 min, 그리고 자리 교환을 위한 tmp변수만 필요
• 선택 정렬에 비해 데이터 교환이 많이 발생
  • 동일하게 O(n2)이나, 선택 정렬보다 비효율적

11. 개선된 버블 정렬 알고리즘

• 각 루프의 반복 횟수를 줄여서 개선 가능
  • 처리 단계의 수 ( Outer Iter )
    • 자리바꿈이 발생하지 않으면 이미 정렬된 상태이므로 이후의 처리 단계를 수행하지 않고 종료
  • 인접한 두 데이터의 비교 횟수 ( Inner Iter )
    • 각 단계에서 무조건 오른쪽/왼쪽 끝까지 이동하면서 인접한 두 데이터의 비교가 불필요
    • 이미 제자리를 잡은 데이터에 대해서는 비교를 수행하지 않도록 함

12. 개선된 버블 정렬 알고리즘 과정

for (i=0; i < n-1; i++) { // 단계: 0, 1, …, (n-2)
	Sorted = TRUE; // 이미 정렬된 상태라고 가정
  for (j=0; j < (n-1) -i ; j++) { // 왼쪽에서 오른쪽으로 진행하는 경우
			if (A[j] > A[j+1]) {
			A[j]와 A[j+1]의 자리바꿈;
			Sorted = FALSE; // 자리바꿈 발생 → 미정렬 상태
			}
	}
	if (Sorted == TRUE) break; // 이미 정렬된 상태이므로 종료
}

13. 개선된 버블 정렬 알고리즘 성능과 특징

• 시간 복잡도는 O(n2)로 동일하나, 총 비교 횟수가 줄어든다.
  • 총 비교 횟수 : n(n-1) / 2
• 입력 데이터의 상태에 따라 성능이 달라짐
  • 최악의 경우 O(n2) / 최선의 경우 O(n)

14. 삽입 정렬이란?

• 주어진 데이터를 하나씩 뽑은 후 이미 나열된 데이터가 항상 정렬된 상태를 유지하도록 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식
• 입력 배열을 정렬 부분 A[0..k-1]과 미정렬 부분 A[k..n-1]으로 구분해서 처리
  • A[0]를 정렬 부분, A[1..n-1]은 미정렬 부분으로 취급하여 시작
  • k=1, …, n-1까지 반복
  • 미정렬 부분 A[k..n-1]의 첫 번째 데이터 A[k]를 뽑고,
  • 정렬 부분 A[0..k-1]에서 제자리를 찾아 A[k]를 삽입해서 A[0..k]가 정렬 상태를 유지하도록 만듦

15. 삽입 정렬 알고리즘 과정

for (i=1; i < n; i++) { // A[0] 정렬 부분; 1, …, (n-1)까지 (n-1)번 반복
	val = A[i]; // 미정렬 부분 A[i..n-1]의 첫 번째 데이터 선택
	for (j=i; j > 0 && A[j-1] > val; j--) { // 삽입할 위치 찾기
			A[j] = A[j-1]; // 정렬 부분의 A[j-1]이 크면 뒤로 한 칸 이동 OR
			A[j] = val; // 찾아진 위치에 선택된 데이터 삽입
		}
}

16. 삽입 정렬의 성능과 특징

• 반복문을 중첩하여 사용
  • iter문 안에 iter 문이 한번 더 있다.
  • 총 n (n-1) / 2번 비교하기에 → O(n2)
• 안정적인 정렬 알고리즘
  • 인접한 두 데이터가 정렬되지 않은 경우에만 위치 교환이 발생
• 제자리 정렬 알고리즘
  • 입력 배열 A[ ] 이외에 상수 개의 저장 공간( 예 : i, j, val )만 필요
• 입력 데이터의 원래 순서에 민감
  • 원하는 정렬 순서의 역순으로 주어지는 경우 → O(n2)
  • 원하는 순서의 정렬된 상태로 주어지는 경우 → O(n)

17. 셸 정렬이란?

• 삽입 정렬의 단점 보완 ( by Donald L. Shell )
  • 삽입 정렬은 현재 삽입하고자 하는 데이터가 삽입될 제 위치에서 많이 벗어나 있어도 한 번에 한 자리씩만 이동해서 찾아가야 함
• 기본 아이디어
  • 멀리 떨어진 데이터와의 비교·교환으로 한 번에 이동할 수 있는 거리를 늘려서 처리 속도 향상
  • 처음에는 멀리 떨어진 두 데이터를 비교해서 필요시 위치를 교환하고, 점차 가까운 위치의 데이터를 비교·교환한 뒤, 맨 마지막에는 인접한 데이터를 비교·교환하는 방식
  • 입력 배열을 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜 가면서 반복
• 부분배열의 개수를 정하는 방법
  • 양수로 이루어진 임의의 순열 ℎ1, ⋯ , ℎ𝑘−1 , ℎ𝑘을 사용
    • 1 < 𝑖 < 𝑘인 𝑖에 대하여 ℎ𝑖−1 < ℎ𝑖 < ℎ𝑖+1를 항상 만족
    • 임의의 𝑖, 𝑗에 대하여 𝑖 < 𝑗이면 ℎ𝑗는 ℎ𝑖의 배수가 되지 않음
    • 항상 ℎ1 = 1이 되어야 함
  • 순열의 역순으로 적용 → ℎ𝑘 → ℎ𝑘−1 → ⋯ → ℎ1
    • 첫 번째 단계 → 전체 배열을 ℎ𝑘개의 부분배열로 나누어 처리( 삽입 정렬 수행 ),
    • 두 번째 단계 → 부분 정렬된 전체 배열을 ℎ𝑘−1개의 부분배열로 나누어 처리, …
    • 마지막 단계 → 부분 정렬된 전체 배열을 ℎ1 = 1개의 부분배열, 즉 전체에 대해서 처리
    • 즉, 처음에는 많은 부분 배열로 나누어 처리하다가 점점 줄여 마지막에는 한개의 부분배열로 처리

18. 셸 정렬에서 순열값 ℎ𝑘의 의미

• 부분배열의 개수
  • 전체 배열을 ℎ𝑘개의 부분배열로 나누어 각 부분배열에 대해서 삽입 정렬을 적용
• 각 부분배열 내에서 이웃한 데이터 간의 거리
  • 𝑖번째 부분배열을 구성하는 데이터
    • 배열 인덱스를 ℎ𝑘로 나누었을 때 나머지가 𝑖 − 1인 데이터
  • ex ) ℎ𝑘 = 4일때, 부분배열을 구성할때 원소를 4씩으로 거리가 있는 데이터끼리 부분배열을 구성
  • 각 부분배열은 전체 배열에서 ℎ𝑘씩 떨어진 데이터로 구성

19. 셸 정렬 알고리즘의 과정

• 하나의 입력 배열을 물리적으로 여러 개의 부분배열로 분할하지 않음
• 각 부분배열을 번갈아 가면서 미정렬 부분의 첫 번째 데이터를 뽑은 후 D만큼씩 떨어진 정렬 부분에서 제자리를 찾아서 삽입하는 방식

for (D=(n/2); D>=1; D=(D/2)) { // D: 부분배열의 개수 & 간격의 크기
	for (i=D; i < n; i++) { // D개의 부분배열에 대한 삽입 정렬 과정
		val = A[i];
		for (j=i; j>=D && A[j-D] > val; j=j-D) {
				A[j] = A[j-D];
				A[j] = val;
		}
	}
}

20. 셸 정렬 알고리즘의 성능과 특징

• 사용하는 순열에 따라 성능이 달라짐
  • 가장 좋은 간격을 찾는 것은 아직 미해결 과제
  • 순열값의 역순으로 차례대로 적용
    • ℎ𝑘 → ℎ𝑘−1 → ⋯ → ℎ1
• 최선 O(nlogn) ~ 최악 O(n2)
• 제자리 정렬 알고리즘
  • 입력 배열 A[ ] 이외에 상수 개의 저장 공간( 예 : D, i, j, val )만 필요
• 안정적이지 않은 정렬 알고리즘

21. 요약

• 기본 개념
  • 내부 정렬, 비교 기반 ↔ 데이터 분포 기반, 안정적, 제자리
• 선택 정렬
  • O(n2), 불안정적, 제자리, 언제나 동일한 시간 복잡도를 가짐
• 버블 정렬
  • O(n2), 안정적, 제자리
  • 개선된 버블 정렬 알고리즘은 데이터의 입력 상태에 따라 성능이 달라짐
• 삽입 정렬
  • O(n2), 안정적, 제자리, 입력 상태의 순서에 민감
• 셸 정렬
  • 삽입 정렬 단점 보완 → 부분배열의 크기/개수를 변화시키면서 삽입 정렬 수행
  • O(n2), 불안정적, 제자리, 사용하는 순열에 따라 성능이 달라짐
• 위의 정렬들은 모두 기본적으로 O(n2)의 성능을 지님