[이코테] 정렬

정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

 

선택 정렬

가장 작은 데이터를 선택해서 맨 앞의 데이터와 바꾸고, 그 다음 작은 데이터를 선택해서 앞에서 두 번째의 데이터와 바꾸는 과정을 반복.

매번 '가장 작은 것을 선택' 한다는 의미에서 선택정렬 알고리즘이라고 함.

 

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-1 번 만큼 매번 가장 작은 원소를 찾아서 스와프 해야 하므로 O(N^2) 의 시간복잡도를 지님.

 

삽입 정렬

필요할 때만 위치를 바꿔서 데이터가 거의 정렬되어 있는 경우에 유용

적절한 위치를 찾은 뒤에 그 위치에 삽입됨.

 

for i in range(1, 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

O(N^2) 의 시간복잡도를 지니지만, 어느 정도 정렬되어 있는 경우에는 계속 break 문을 만나서 O(N) 의 시간복잡도를 지니게 됨.

 

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

 

피벗을 설정해서, 왼쪽에서는 피벗보다 큰 수, 오른쪽에서는 피벗보다 작은 수를 찾고 이 둘을 교환한다.

큰 수와 작은 수를 찾는 과정에서 둘이 엇갈리게 된다면, 피벗을 더 작은 수와 바꾼다

 

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)

 

파이썬의 장점을 살린 퀵 정렬

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 = [x for x in tail if x>pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

 

시간 복잡도

평균적으로 O(n logn) 원리는 자세히 알지 못해도 됨

이미 어느 정도 정렬된 경우에는 느리게 동작함

 

계수 정렬

특정 조건이 부합할 때만 사용할 수 있는 빠른 정렬 알고리즘

데이터의 개수가 N / 데이터 중 최댓값이 K => O(N+K)

 

계수 정렬 사용 시에는 모든 범위를 담을 수 있는 크기의 배열을 선언해야 함.

 

앞서 다룬 방법들처럼 직접 데이터의 값을 비교해서 위치를 변경, 정렬하는 방식이 아님

 

예를 들어, 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 가 있다고 가정

이 경우, 가장 큰 데이터는 9 이고 가장 작은 데이터는 0 이기 때문에 배열의 길이가 10인 배열을 따로 선언해주면 됨.

 

0~9까지의 인덱스에 각 숫자가 몇번 등장했는지 기록하고, 정렬 시에는 해당하는 인덱스의 숫자를 해당 횟수만큼 출력하면 됨.

 

array = [7, 5, 9, ...]
count = [0]*(max(array)+1)

for i in range(len(array)):
	count[array[i]]+=1 # 각 데이터에 해당하는 인덱스의 값을 증가시키기
    
for i in range(len(count)):
	for j in range(count[i]):
		print(i,end=' ')

 

공간 복잡도

 

데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리. (만약, [0, 999999] 를 정렬해야 한다면 퀵 정렬을 사용하는 것이 유리하기 때문!)

 

파이썬 정렬 라이브러리

병합 정렬을 사용. 최악의 경우에도 O(N log N)