nnginii
[자료구조] 정렬 (SORT) 본문
- 정렬
- 선택 / 삽입 / 버블 정렬의 과정과 알고리즘, 시간복잡도
- 정렬된 배열을 이용한 집합
정렬(sorting) _ 데이터를 순서대로 재배열하는 작업
- 정렬을 위해서는 사물들을 서로 비교할수 있어야하고, 비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있다.
- 정렬시켜야 될 대상을 레코드(record)라고 부른다.
- 레코드는 여러 개의 필드(field)로 이루어진다.
- 정렬의 기준이 되는 필드를 키(key) 또는 정렬 키(sort key)라고 한다.
즉, 정렬이란 레코드들을 키(key)의 순서로 재배열 하는 것이다.
선택 정렬 (selection sort)
가장 작은 요소를 꺼내서 순서대로 출력
| 정렬 된(왼쪽) 리스트 | 정렬 안 된(오른쪽) 리스트 | 설명 |
| [ ] | [5, 3, 8, 4, 9, 1, 6, 2, 7] | 초기상태 |
| [1] | [5, 3, 8, 4, 9, 6, 2, 7] | 1 선택 및 이동 |
| [1, 2] | [5, 3, 8, 4, 9, 6, 7] | 2 선택 및 이동 |
| [1, 2, 3] | [5, 8, 4, 9, 6, 7] | 3 선택 및 이동 |
| ... | ... | 4~8 선택 및 이동 |
| [1, 2, 3, 4, 5, 6, 7, 8, 9] | [ ] | 9 선택 및 이동 |
입력 배열에서 가장 작은 숫자를 선택하여 출력 배열의 맨 뒤로 이동하는 작업을 반복한다. 이 과정을 입력 배열이 공백상태가 될 때까지 반복하면 정렬이 끝난다. 최솟값이 선택되면 이것을 맨 앞의 요소와 교환하는 원리이다.
def selection_sort(A) :
n = len(A)
for i in range (n-1): // 0, 1, 2, ... n-2 [외부루프]
least = i;
for j in range(i+1, n) : // i+1, ..., n-1 [내부루프]
if (A[j]<A[least]) :
least = j
A[i], A[least] = A[least], A[i]
printStep(A, i+1)
def printStep(arr, val) :
print(" Step %2d =" % val, end='')
print(arr)
정렬 함수에서 이중 루프가 사용되는데, 내부 루프는 i+1부터 n-1까지(n-1-i번) 반복한다. 외부 루프에서 i는 0부터 n-2까지 순서대로 대입되므로 비교연산 실행 횟수는 다음과 같다.
(n-1) + (n-2) + ··· + 1 = n (n-1) / 2 = O(n^2)
이러한 시간복잡도를 봤을 때, 선택정렬은 효율적인 알고리즘도 아니고 안정성을 만족하지도 않는다. 그러나 알고리즘이 간단하고, 입력 자료의 구성과 상관없이 자료이동 횟수가 열정된다는 장점을 갖는다.
삽입 정렬 (insertion sort)
두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬한다.
def insertion_sort(A) :
n = len(A)
for i in range(1, n) : // 외부루프 : 1, 2, ... n-1
key = A[i]
j = i-1
while j>=0 and A[j] > key :
A[j + 1] = A[j]
j -= 1
A[j + 1] = key
printStep(A, i)
정렬된 부분의 맨 뒤에서 앞으로 가면서 key보다 큰 요소는 모두 한칸씩 뒤로 이동한다. 이동이 멈춘 위치에 원래의 A[i]를 저장(끼워넣음)한다. 처음 key 값은 두 번재 자료부터 시작한다.
삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다.
입력 배열이 이미 정렬되어있는 경우, while문의 반복 조건 중에서 A[j]>key가 항상 False이므로 항상 빠져나오게 된다. 외부루프는 n-1번 반복하는데 while문의 루프 내부가 O(1)이므로 전체 복잡도는 O(n)이 된다.
입력 배열이 역순으로 정렬 된 경우에는, 항상 맨 앞에 끼워 넣어야 하므로 while문은 항상 i번 반복한다. 따라서 전체 복잡도는 다음과 같다.
$$\sum_{i=0}^{n-1}i = 1+2+\cdot \cdot \cdot +(n-1)=\frac{n(n-1)}{2} = O(n^2)$$
삽입 정렬은 많은 레코드의 이동을 포함하므로 레코드가 크고, 양이 많은 경우 효율적이지 않다. 반면에 알고리즘이 간단하고, 안정성도 충족한다. 특히 대부분의 레코드가 이미 정렬되어 있는 경우 효율적으로 사용될 수 있다.
버블 정렬 (bubble sort)
인접한 2개의 레코드를 비교하여 크기가 순서대로가 아니면 서로 교환하는 방법을 사용한다. 이러한 비교 - 교환 과정은 배열의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 비교 - 교환 과정이 한번 완료되면(한 번의 스캔) 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동한다. 비교 - 교환 과정은 더 이상 교환이 일어나지 않을 때까지 계속된다.
def bubble_sort(A) :
n = len(A)
for i in range(n-1, 0, -1) : // 외부 루프 : n-1, n-2, ... 2, 1
bChanged = False
for j in range (i) : // 내부 루프 : 0, 1, ... i-1
if (A[j]>A[j+1]) :
A[j], A[j+1] = A[j+1], A[j]
bChanged = True
if not bChanged: break;
printStep(A, n - i);
버블 정렬도 입력의 구성에 따라 복잡도가 달라진다. 최선의 경우는 입력 배열이 이미 정렬되어 있는 경우이다. 첫 번째 스캔에서부터 교환이 발생하지 않고, 외부 반복문을 바로 빠져나온다. 한 번의 스캔이 O(n)이므로 최선의 복잡도는 O(n)이다.
최악의 경우는 입력 배열이 역순으로 정렬된 경우이다. 외부 루프가 n-1번 반복하고, 그 만큼의 스캔이 필요하므로 버블 정렬은 최악의 입력에서 O(n^2)의 복잡도를 갖는다.
버블 정렬은 알고리즘이 단순하고 안정성을 충족하지만 효율적이지는 않다. 그렇지만 입력 배열이 어느 정도 정렬된 경우라면 효과적으로 사용될 수도 있다.
정렬된 배열을 이용한 집합
배열 요소를 오름차순으로 정렬하여 집합을 저장하면 연산에 대한 시간복잡도가 개선된다. 집합의 비교나 합집합, 차집합, 교집합 등을 훨씬 효율적으로 구현할 수 있다.
새로운 원소를 삽입하는 insert() 연산
def insert(self, e) : # O(n) -> O(n)
if self.contains(e) or self.isFull() :
return
self.array[self.size] = e
self.size += 1 // 일단 정렬된 배열의 맨 뒤에 추가함
for i in range(self.size-1, 0, -1) :
if self.array[i-1] <= self.array[i] : break
// 맨 뒤에서부터 앞의 워노가 더 크면 원소를 교환, 이 과정을 작거나 같은 원소가 나올 때까지 반복
self.array[i-1], self.array[i] = self.array[i], self.array[i-1] // 원소 교환이 연산의 복잡도는 O(n)으로 정렬하지 않은 배열을 이용하는 삽입 연산과같다. 원소를 제자리에 끼워넣는 과정이 추가되지만, 중복 검사가 반드시 필요하기 때문에 정렬과 관계없이 삽입 연산의 복잡도는 모두 O(n)이다.
원소를 삭제하는 delete() 연산
def delete(self, e) : // O(n) -> O(n)
if not self.contains(e) :
return
i = 0
while self.array[i] < e : i += 1
self.size -= 1
while i < self.size :
self.array[i] < self.array[i+1]
i += 1삭제할 위치 이후의 모든 원소들을 앞으로 한 칸씩 옮겨야한다. 삭제 연산도 코드는 좀 더 복잡해지지만 시간 복잡도에서는 차이가 없다. O(n)에 삭제가 완료된다.
두 집합을 비교하는 연산자 중복함수 __eq__()
def __eq__( self, setB ): // O(mn) ---> O(n+m)
if self.size != setB.size :
return False
for i in range(self.size) :
if self.array[i] != setB.array[i] :
return False
return True두 집합의 원소 개수가 같아야 두 집합이 같은 집합인지 비교할 수 있다. 두 집합 A와 B가 같은지 == 연산자로 비교할 수 있으려면 __eq__() 메소드를 구현해야 하는데, 크기를 먼저 비교한 후 A의 모든 원소가 B에 있는지를 검사해야한다. 두 집합이 정렬되어있으면 contains()함수를 사용하지 않고 해당 원소들만 비교하면 된다. 따라서 복잡도는 O(n)이 된다. 정렬을 이용하면 시간복잡도가 많이 개선된다.
합집합을 구하는 union 연산
def union( self, setB ): // O(mn) -> O(n+m)
setC = SortedArraySet() // 합집합을 저장할 공백 집합
i = 0 // 집합 self의 원소의 인덱스. 0부터 시작
j = 0 // 집합 setB의 원소의 인덱스. 0부터 시작
while i < self.size and j < setB.size :
a = self.array[i]
b = setB.array[j]
if a == b:
setC.append(a)
i += 1
j += 1
elif a < b:
setC.append(a)
i += 1
else :
setC.append(b)
j += 1
while i < self.size :
setC.append(self.array[i])
i += 1
while j < setB.size :
setC.append(setB.array[j])
j += 1
return setC // 최종 합집합을 반환원소들이 크기순으로 정렬되어 있으면 두 집합의 가장 작은 원소부터 시작해 전체 원소를 한 번씩만 스캔하여 합집합을 구할 수 있다. 코드를 간단하게 설명해보자면 다음과 같다.
- 두 집합의 원소들이 크기순으로 정렬되어 있으므로, 가장 작은 원소들부터 비교하여 더 작은 원소를 새로운 집합에 넣고 그 집합의 인덱스를 증가시킨다.
- 만약 두 집합의 현재 원소가 같으면 하나만을 새 집합에 넣으면 된다. 인덱스는 모두 증가시킨다.
- 한쪽 집합이 모두 처리되면 나머지 집합의 남은 모든 원소를 순서대로 새 집합에 넣는다.
이 연산의 시간복잡도를 알기 위해서는 두 집합의 원소의 개수 합에 비례하는 비교가 필요하다. 만약 두 집합의 크기를 n이라고 한다면 이 연산의 시간 복잡도는 O(n)이다.
정렬되지 않은 리스트와 정렬된 리스트로 구현한 집합에서의 복잡도 비교
| 집합의 연산 | 정렬되지 않은 리스트 | 정렬된 리스트 |
| insert(e) | O(n) | O(n) |
| __eq__(setB) | O(n^2) | O(n) |
| union(setB) | O(n^2) | O(n) |
| intersect(setB) | O(n^2) | O(n) |
| difference(setB) | O(n^2) | O(n) |
| contains(e) | O(n), 순차탐색 | O(log n), 이진탐색 |
연산에 대한 시간 복잡도를 비교해보았을 때, 정렬을 사용하면 삽입이 약간 번거롭기는 하지만 집합의 여러 연산들을 훨씬 효율적으로 처리할 수 있는것을 알 수 있다.
학기 중에 과제를 하며 정렬 부분을 공부할 때는 정렬 과정 이미지를 보고 이해했지만, 이번에 다시 공부하면서 파이썬으로 직접 정렬과 탐색 함수를 작성해 보니 꽤 성장한 것 같아서 좋았다. 하지만 머릿속에 있는 코드를 바로 작성하는 데에는 오류도 많고 시간이 꽤 오래 걸려서 노트에 큰 틀을 그리고 손으로 한 번 적어본 뒤에 코드를 작성했다. 코딩이 끝나고 난 뒤에는 이 과정을 머릿속에서 끝낼 수 있는 사람이 되고 싶다는 생각을 많이 한 것 같다. 2024년이 가기 전에 다시 돌아와서 한 번 더 코드를 작성해 보면서 얼마나 발전했을지 확인해 봐야겠다.