정렬 알고리즘
선택 정렬 알고리즘
- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.
array = [7,5,9,0,3,1,6,2]
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
print(array)선택 정렬의 시간 복잡도
- 선택정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.
- 구현 방식은 오차가 있을 수 있지만, 전체 연산 횟수는
N + (N-1) + (N-2) + ... 2 - 이는 (N^2 + N - 2) /2와 같고, 따라서 시간 복잡도는 O(n^2)입니다.
삽입 정렬
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.
- 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작합니다.
array = [7,5,9,0,3,1,6,2]
for i in range(len(array)):
for j in range(i,0,-1):
if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array)삽입 정렬의 시간 복잡도
- 삽입 정렬의 시간 복잡도는 O(n^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됩니다.
- 삽입 정렬은
현재 리스트의 데이터가 거의 정렬되어 있는 형태라면 매우 빠르게 동작합니다.- 최선의 경우 O(n)의 시간복잡도를 지닙니다.
퀵 정렬
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나.
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘.
- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정함.
- 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할이라고 함.
퀵정렬의 시간 복잡도
너비 x 높이 = N x logN = NlogN
- 평균의 경우 O(NlogN)의 시간복잡도를 지님.
- 최악의 경우 O(n^2)의 시간 복잡도를 지님.
array = [7,5,9,0,3,1,6,2,4]
def quick_sort(array,start, end):
if start >= end:
return
pivot = start # 피벗은 항상 첫번째 원소
left = start + 1
right = end
while(left <= right):
# 피벗보다 큰 데이터를 찾을 때까지 반복
while(left <= end and array[left] <= array[pivot]):
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while(right > start and array[right] >= array[pivot]):
right -= 1
if (left > right): # 엇갈렸다면, 작은데이터와 피벗을 교체
array[right], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른 쪽 부분에서 각자 정렬 수행
quick_sort(array, start, right - 1)
quick_sort(array, right + 1, end)
quick_sort(array, 0 , len(array) -1)
print(array)퀵 정렬 소스 코드 : 파이썬의 장점을 살린 방식
array = [7,5,9,0,3,1,6,2,4]
def quick_sort(array):
# 만약 하나 이하의 원소만을 담고 있다면 종료
if len(array) <= 1:
return array
pivot = array[0] # 피벗은 첫 번째 원소
tail = array[1:] # 피벗을 제외한 리스트
left_side = [x for x in tail if x <=pivot] # 분할된 왼쪽 부분
right_side = [y for y in tail if y>pivot] # 분할된 오른족 부분
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
- 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현될 수 있을 때 사용 가능함.
- 데이터의 개수가 N , 데이터(양수) 중 최대값이 K 일때 최악의 경우에도 수행시간 O(N+k)를 보장함.
def counting_sort(array):
max_value = max(array)
count = [0] * (max_value + 1)
for number in array:
count[number] += 1
sorted_array = []
# 그 갯수만큼, 곱해서 추가함.
for i in range(len(count)):
sorted_array.extend([i] * count[i])
return sorted_array
# 예제 사용
array = [4, 2, 2, 8, 3, 3, 1]
sorted_array = counting_sort(array)
print(sorted_array)계수 정렬의 시간복잡도
- 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(n+k)입니다.
- 계수 정렬은 때와 따라서 심각한 비효율성을 초래할 수 있습니다.
- 데이터가 0과 99999999999로 단 2개만 있는 경우가 그렇겠죠?
- 계수 정렬은 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적으로 사용할 수 있습니다.
- 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적입니다.
- 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적입니다.
하나를 알고 그걸로 모든걸 관통한다.