728x90
반응형
정렬
정렬이란 값을 대소 관계에 따라 일정한 순서로 늘어놓는 작업을 의미한다.
정렬을 사용하면 검색을 더 쉽게 할 수 있다.
오름차순 정렬(Ascending order) : 값이 작은 데이터를 앞쪽에 배치
내림차순 정렬(descending order) : 값이 큰 데이터를 앞쪽에 배치
버블 정렬(Bubble Sort)
이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 정렬 알고리즘이다.
시간복잡도(Time Complexity)
- 최선의 경우(정렬된 배열이 주어진 경우): O(n)
- 이 경우에는 인접한 원소를 비교하고 교환할 필요가 없기 때문에 한 번의 순회만으로 정렬이 완료된다.
- 평균 및 최악의 경우: O(n^2)
- 버블 정렬은 인접한 원소를 비교하고 교환하는 과정을 n-1번 수행한다. 각 순회마다 최대 n-1, n-2, ..., 2, 1번의 비교와 교환을 수행하므로 전체적인 시간복잡도는 n-1 + n-2 + ... + 2 + 1 ≈ n(n-1)/2 ≈ O(n^2)이다.
- 버블 정렬은 이웃한 두 원소를 비교하므로 비교 횟수는 항상 n(n-1)/2이다.
공간복잡도(Space Complexity)
- O(1)
- 버블 정렬은 주어진 배열 안에서 원소의 위치를 교환하면서 정렬을 수행하므로, 추가적인 공간이 필요하지 않다.
구현 예시
# 버블정렬
from typing import Any
def bubbleSort(List:list,reverse=False)->list:
l = List[:] # 카피
for i in reversed(range(len(l))):
for j in range(i):
if l[j] > l[j+1]:
tmp = l[j]
l[j] = l[j+1]
l[j+1] = tmp
print(f"Pass {len(l)-i} => {l}")
if reverse : # 내림차순
return l[::-1]
else: # 오름차순
return l
print(bubbleSort(List,reverse = True))
선택 정렬(Selection Sort)
주어진 배열에서 최소값을 선택하여 정렬되지 않은 부분의 첫 번째 원소와 교환하는 방식으로 동작하는 정렬 알고리즘이다.
시간복잡도(Time Complexity)
- 최선, 평균, 최악의 경우: O(n^2)
- 선택 정렬은 정렬되지 않은 부분의 길이에 따라 n-1번의 반복을 수행한다.
- 각 반복에서 최소값을 찾기 위해 비교 연산이 n-1, n-2, ..., 2, 1번 수행되므로 전체적인 시간복잡도는 n(n-1)/2 ≈ O(n^2)이다. 선택 정렬은 이웃한 두 원소를 교환하지 않으므로 교환 연산은 최대 n-1번 수행됩니다.
공간복잡도(Space Complexity)
- 선택 정렬은 주어진 배열 안에서 원소의 위치를 교환하면서 정렬을 수행하므로, 추가적인 공간이 필요하지 않다. 따라서 공간복잡도는 O(1)입니다.
구현 예시
# 선택 정렬
def selectionSort(List:list,reverse=False)->list:
l = List[:]
for i in range(len(l)-1):
small = l[i]
for j in l[1+i:]:
if small > j:
small = j
l.remove(small)
l.insert(i,small)
print(f'Phase {i+1} -> {l}')
if reverse : # 내림차순
return l[::-1]
else: # 오름차순
return l
print(selectionSort(List,reverse = True))
삽입 정렬(Insertion Sort)
주어진 배열에서 정렬되지 않은 부분의 첫 번째 원소를 이미 정렬된 부분에 적절한 위치에 삽입하여 정렬하는 방식으로 동작하는 정렬 알고리즘이다.
시간복잡도(Time Complexity)
- 최선의 경우(정렬된 배열이 주어진 경우) : O(n)
- 이 경우에는 각 원소를 비교할 필요 없이 한 번의 순회만으로 정렬이 완료된다.
- 평균 및 최악의 경우: O(n^2)
- 삽입 정렬은 비교 연산과 원소의 이동 연산을 수행한다.
- 최악의 경우에는 정렬되지 않은 부분의 모든 원소를 이동시켜야 하므로 비교 횟수는 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 ≈ O(n^2)이다.
공간복잡도(Space Complexity) : O(1)
- 삽입 정렬은 주어진 배열 안에서 원소의 위치를 이동하면서 정렬을 수행하므로, 추가적인 공간이 필요하지 않다.
구현 예시
# 삽입 정렬
def insertionSort(List:list,reverse=False)->list:
l = List[:]
for i in range(1,len(l)):
item = l[i] # 정렬 안된 부분의 첫번째 원소
j = i-1 # 정렬된 부분의 마지막 인덱스
while j >= 0 and l[j] > item : # 정렬된 부분에서 key보다 큰 원소들은 오른쪽으로 이동
l[j + 1] = l[j]
j -= 1
l[j + 1] = item # key를 삽입할 위치에 삽입
print(f'Phase {i} -> {l}')
if reverse : # 내림차순
return l[::-1]
else: # 오름차순
return l
print(insertionSort(List,reverse = True))
셸 정렬(Shell Sort)
삽입 정렬의 장점은 살리고 단점은 보완한 정렬로, 배열을 일정한 간격으로 나누어 각 부분 배열을 정렬하고, 간격을 점차 줄여가며 정렬을 반복하는 방식으로 동작한다.
시간복잡도(Time Complexity)
- 최선의 경우: O(n log n)
- 셸 정렬은 초기 간격을 설정하여 여러 번의 삽입 정렬을 수행한다.
- 초기 간격에 따라 삽입 정렬이 수행되는 횟수가 달라지므로, 최선의 경우에는 O(n log n)의 시간복잡도를 가집니다.
- 평균 및 최악의 경우: O(n^2)
- 셸 정렬의 시간복잡도는 아직까지 이론적으로 완전히 분석되지 않았다.
- 평균적으로 O(n^2)의 시간복잡도를 가지며, 최악의 경우에도 O(n^2)이다. 그러나 삽입 정렬에 비해 훨씬 효율적으로 동작하는 특성이 있다.
공간복잡도(Space Complexity): O(1)
- 셸 정렬은 주어진 배열 안에서 원소의 위치를 이동하면서 정렬을 수행하므로, 추가적인 공간이 필요하지 않습니다.
구현예시
# 셸 정렬
def shellSort(List:list,reverse=False)->list:
l = List[:]
n = len(l)
gap = n // 2 # 초기 간격 설정
count = 1
while gap > 0:
for i in range(gap, n):
temp = l[i]
j = i
while j >= gap and l[j - gap] > temp:
l[j] = l[j - gap]
j -= gap
l[j] = temp
gap //= 2 # 간격을 절반으로 줄임
print(f'Phase {count} -> {l}')
count+=1
if reverse : # 내림차순
return l[::-1]
else: # 오름차순
return l
print(shellSort(List,reverse = True))
퀵 정렬(Quick Sort)
분할 정복(divide and conquer) 방식을 사용하여 배열을 정렬하는 알고리즘이다. 배열을 기준(pivot) 값을 기준으로 작은 값과 큰 값으로 분할하고, 분할된 부분 배열에 대해 재귀적으로 퀵 정렬을 수행하여 정렬을 완성한다.
시간복잡도(Time Complexity)
- 최선 및 평균의 경우: O(n log n)
- 퀵 정렬의 평균적인 시간복잡도는 O(n log n)이다.
- 분할할 때마다 배열이 대략 반으로 분할되므로, 재귀 호출이 log n번 발생하게 되고 각 분할에서 기준 값과 비교하는 연산은 평균적으로 O(n)번 수행된다.
- 최악의 경우: O(n^2)
- 퀵 정렬의 최악의 시간복잡도는 O(n^2)이다.
- 최악의 경우는 배열이 이미 정렬되어 있거나, 기준 값이 항상 최솟값 또는 최댓값으로 선택되는 경우이다. 이를 피하기 위해 기준 값을 잘 선택하거나, 랜덤한 기준 값을 사용할 수 있다.
공간복잡도(Space Complexity): 재귀 호출에 의한 스택 공간을 제외하면, 공간복잡도는 O(1)이다.
- 퀵 정렬은 주어진 배열을 분할하고 정렬하기 위해 추가적인 메모리를 필요로 하지 않는다.
구현 예시
# 퀵 정렬
def quickSort(List:list,reverse=False)->list:
if len(List) <= 1:
return List
pivot = List[len(List) // 2] # 기준 값 선택
left = [x for x in List if x < pivot] # 기준 값보다 작은 값들
middle = [x for x in List if x == pivot] # 기준 값과 같은 값들
right = [x for x in List if x > pivot] # 기준 값보다 큰 값들
return quickSort(left) + middle + quickSort(right) # 재귀적으로 정렬 후 병합
print(quickSort(List[:],reverse = True))
병합 정렬(Merge Sort)
분할 정복(divide and conquer) 방식을 사용하여 배열을 정렬하는 알고리즘이다. 배열을 반으로 나누어 각각을 재귀적으로 정렬한 후, 정렬된 두 개의 배열을 병합하여 최종적으로 정렬된 배열을 생성한다.
시간복잡도(Time Complexity)
- 최선, 평균, 최악의 경우: O(n log n)
- 병합 정렬은 배열을 반으로 나누는 단계에서 O(log n)번의 분할이 수행된다.
- 각 분할 단계에서 병합이 이루어지는데, 병합에는 O(n)의 시간이 소요됩니다. 따라서 전체적인 시간복잡도는 O(n log n)입니다.
- 최선, 평균, 최악의 경우 모두 동일한 시간복잡도를 가지므로, 입력 데이터의 상태에 상관없이 일정한 성능을 보장합니다.
공간복잡도(Space Complexity): O(n)
- 병합 정렬은 재귀적인 호출에 의해 추가적인 공간을 필요로 한다.
- 재귀 호출 스택에 사용되는 공간을 제외하면, 정렬할 배열의 크기와 동일한 크기의 추가 배열이 필요합니다.
구현 예시
def mergeSort(List:list)->list:
if len(List) <= 1:
return List
# 배열을 반으로 나누기
mid = len(List) // 2
left = List[:mid]
right = List[mid:]
# 나눈 배열에 대해 재귀적으로 병합 정렬 수행
left = mergeSort(left)
right = mergeSort(right)
# 정렬된 배열 병합
merged = merge(left, right)
return mergeddef merge(left:list, right:list)->list:
merged = []
i = j = 0
# 두 배열을 비교하며 작은 값을 차례대로 merged 배열에 추가
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# 남은 요소들을 merged 배열에 추가
while i < len(left):
merged.append(left[i])
i += 1
while j < len(right):
merged.append(right[j])
j += 1
return merged
print(mergeSort(List))힙 정렬(Heap Sort)
힙 자료구조를 기반으로 한 정렬 알고리즘이다. 힙은 완전 이진 트리의 일종으로, 최대 힙 또는 최소 힙이라는 특성을 가지고 있다. 힙 정렬은 주어진 배열을 힙으로 구성한 후, 힙의 특성을 유지하면서 최대(또는 최소) 값을 추출하여 배열의 뒷부분부터 저장하는 방식으로 동작한다.
시간복잡도(Time Complexity)
- 최선, 평균, 최악의 경우: O(n log n)
- 힙 정렬은 힙을 구성하는 단계에서 O(n)의 시간이 소요되며, 추출 및 재구성 단계에서 O(n log n)의 시간이 소요된다. 따라서 힙 정렬의 시간복잡도는 O(n log n)이다. 최선, 평균, 최악의 경우 모두 동일한 시간복잡도를 가지므로, 입력 데이터의 상태에 상관없이 일정한 성능을 보장한다.
공간복잡도(Space Complexity): O(1)
- 힙 정렬은 주어진 배열 안에서 힙을 구성하고 정렬을 수행하므로, 추가적인 공간이 필요하지 않습니다.
구성 예시
# 힙 정렬
def heapify(List:list, n:int, i:int)->list:
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and List[left] > List[largest]:
largest = left
if right < n and List[right] > List[largest]:
largest = right
if largest != i:
List[i], List[largest] = List[largest], List[i]
heapify(List, n, largest)
def heapSort(List:list,reverse=False)->list:
l = List[:]
n = len(l)
# 최대 힙 구성
for i in range(n // 2 - 1, -1, -1):
heapify(l, n, i)
# 힙에서 요소 추출하여 정렬
for i in range(n - 1, 0, -1):
l[i], l[0] = l[0], l[i] # 힙의 루트와 맨 뒤 요소 교환
heapify(l, i, 0) # 힙 특성 유지
if reverse : # 내림차순
return l[::-1]
else: # 오름차순
return l
print(heapSort(List,reverse=True))
도수 정렬(Counting Sort)
비교 기반 정렬 알고리즘이 아닌 정수 형태의 데이터를 정렬하는 선형 시간 알고리즘이다. 데이터의 값들을 카운트하고, 각 값이 얼마나 나타나는지를 기록한 뒤, 이를 바탕으로 정렬된 결과를 생성한다.
시간복잡도(Time Complexity):
- 최선, 평균, 최악의 경우: O(n + k)
- 입력 배열의 크기를 n이라고 할 때, 카운트 배열을 구성하는 단계에서 O(n)의 시간이 소요된다. 그리고 카운트 배열의 누적합을 계산하는 단계에서 O(k)의 시간이 소요된다. 이후 입력 배열을 역순으로 순회하며 정렬된 결과를 생성하는 단계에서 O(n)의 시간이 소요된다. 따라서 전체적인 시간복잡도는 O(n + k)이다.
- 여기서 k는 입력 배열의 값의 범위를 의미한다.
- 입력 배열의 크기에 비해 값의 범위가 작을 경우, k는 상수에 가까워져 선형 시간에 가까운 성능을 보인다.
공간복잡도(Space Complexity): O(k)
- 도수 정렬은 입력 배열의 크기와 값의 범위에 비례하는 크기의 카운트 배열을 사용한다.
구현 예시
# 도수 정렬
def countingSort(List:list,reverse=False)->list:
max_value = max(List)
count = [0] * (max_value + 1)
l = List[:]
# 입력 배열의 값들을 카운트
for num in l:
count[num] += 1
# 카운트 배열을 누적합으로 변경
for i in range(1, len(count)):
count[i] += count[i - 1]
# 입력 배열을 역순으로 순회하며 정렬된 결과 생성
sorted_arr = [0] * len(l)
for num in reversed(l):
index = count[num] - 1
sorted_arr[index] = num
count[num] -= 1
if reverse : # 내림차순
return sorted_arr[::-1]
else: # 오름차순
return sorted_arr
print(countingSort(List,reverse=True))
정렬 코드들
정렬.ipynb
Colaboratory notebook
colab.research.google.com
728x90
반응형
'CS > 자료구조 및 알고리즘' 카테고리의 다른 글
| [자료구조] 트리 (0) | 2023.06.30 |
|---|---|
| [자료구조] 리스트 (0) | 2023.06.30 |
| [알고리즘] 문자열 검색 (0) | 2023.06.29 |
| [알고리즘] 재귀 (0) | 2023.06.27 |
| [자료구조] 스택, 큐, 파이썬 내장 자료구조 및 라이브러리 (0) | 2023.06.26 |
