정렬 알고리즘

zunzero·2022년 8월 5일
0

알고리즘(파이썬)

목록 보기
4/54

정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
정렬 알고리즘을 통해 데이터를 정렬하면 이진 탐색(binary search)이 가능하다.

정렬 알고리즘은 굉장히 다양하다.
선택정렬, 삽입정렬, 퀵 정렬, 계수 정렬만 언급하겠다.

7, 5, 9, 0, 3, 1, 6, 2, 4, 8을 정렬해보자!

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해, 맨 앞에 있는 데이터와 바꾸는 작업 반복

1. 전체 구간: 7, 0 change
0, 5, 9 , 7, 3, ...

2. 5 ~ 8 구간: 5, 1 change
0, 1, 9, 7, 3, ...

3. 9 ~ 8 구간: 9, 2 change
0, 1, 2, 7, 3, ...

4. 7 ~ 8 구간: 7, 3 change
0, 1, 2, 3, 7, ...

탐색 구간은 점점 줄어들지만, 최소값을 구하기 위해 매번 모든 데이터를 뒤져야 한다.
(N + (N-1) + ... + 2 = 약 (N * (N+1)) / 2 -> 최소값 구하기 위한 연산)
시간 복잡도는 O(N^2)이다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

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]	# swap

print(array)
# 결과는 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

위의 소스 코드에서도 알 수 있듯이, 2중 반복문이 사용되었기 때문에 시간 복잡도는 O(N^2)이다.

삽입정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
선택정렬 보다 구현 난이도는 높지만, 더 효율적 !

1. 첫번째 데이터인 7은 이미 정렬되어 있다고 가정하고, 두번 째 데이터인 5가 삽입될 위치 결정 
(7의 왼쪽 혹은 오른쪽)
5, 7, 9, 0, ...

2. 9가 들어갈 위치 결정 (5,7 기준)
5, 7, 9, ...

3. 0이 들어갈 위치 결정 (5, 7, 9 기준)
0, 5, 7, 9, ...

4. 3이 들어갈 위치 결정 (0, 5, 7, 9 기준)
0, 3, 5, 7, 9, ...

삽입 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 O(N^2)이다.
다만, 만약 현재의 리스트가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 이 때에는 퀵정렬보다 빠르게 동작한다.
최선의 경우 O(N)의 시간 복잡도를 가진다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
	for j in range(i, 0, -1):	# 인덱스 i부터 1까지 감소하며 반복하는 문법
    	if array[j] < array[j-1]: 	# 한 칸씩 왼쪽으로 이동
        	array[j], array[j-1] = array[j-1], array[j]
        else:	# 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        	break

print(array)
# 결과는 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

위의 소스 코드에서도 알 수 있듯이, 2중 반복문이 사용되었기 때문에 시간 복잡도는 O(N^2)이다.

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
병합 정렬과 더불어 대부분의 프로그래밍 언어의 표준 정렬 라이브러리의 근간이 되는 알고리즘

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(pivot)로 설정한다.
1. 리스트의 왼쪽에서부터는 pivot 보다 큰 값을, 
오른쪽에서부터는 pivot 보다 작은 값을 선택하여 서로 위치를 바꿔줌
2. 왼쪽에서부터 pivot 보다 큰 값을 찾고, 
오른쪽에서부터 pivot 보다 작은 값을 찾았을 때, 만약 이 둘의 위치가 엇갈린 경우라면
    그 중 작은 값을 pivot 과 바꾼다.
3. 그러면 pivot 을 기준으로, 왼쪽 파트와 오른쪽 파트로 분할 (divide) 된다.
4. 각 파트에 대해 첫 원소를 pivot 으로 설정하여 퀵 정렬 다시~~ (재귀)

퀵 정렬의 시간 복잡도는 평균적으로 O(NlogN)이다. 분할이 절반에 가까울 수록 좋다.
하지만 최악의 경우 O(N^2)의 시간 복잡도를 가진다. 이는 분할이 한쪽에 편향되어 있는 경우이다. (ex. 이미 정렬된 배열)
하지만 표준 라이브러리에서는 최악의 경우에도 O(NlogN)의 시간 복잡도를 가질 수 있도록 알고리즘을 설정해두었으니 걱정할 필요 없다. ㅎㅎ

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
	if start >= end:	# 원소가 1개인 경우 종료
    	return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
    	# pivot보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
        	left += 1
        # pivot보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
        	right -= 1
        if left > right: 	# 엇갈렸다면 작은 값과 pivot 교체
        	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)
# 결과는 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]    

다음은 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스 코드이다. 참고만 하자.
(비교 연산 횟수가 증가하여 시간 면에서는 조금 더 비효율적이다.)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
	# 리스트가 1개 이하의 원소를 갖고 있다면 종료
	if len(array) <= 1:
    	return array
    
    pivot = array[0]
    tail = array[1:]	# pivot 을 제외한 리스트
    
    
    left_side = [x for x in tail if x <= pivot]	# pivot보다 작은 부분
    right_side = [x for x in tail if x > pivot]	# pivot 보다 큰 부분
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
print(array)
# 결과는 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]        

계수 정렬

계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 정렬 알고립즘이다.
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하며,
데이터의 개수가 N, 데이터(양수) 중 최대값이 K일 때 최악의 경우에도 수행시간 O(N+K) 보장한다.
실수형 데이터가 주어지는 경우는 사용하기 어렵고,
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트 생성
if data = 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2:
    list => index 0~9 
    (각 인덱스는 데이터에 해당함, 즉 각 데이터가 몇개씩 있는지 count 할 리스트를 생성하는 것!)
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
3. 최종적으로 리스트에는 각 데이터가 몇번씩 등장했는지 그 횟수가 기록됨.
4. 결과를 확인할 때는 리스트의 첫번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다.

상대적으로 공간 복잡도가 높다. (리스트 생성 시 메모리 상대적으로 쪼끔 많이 사용)
동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용가능하다.
만약 데이터가 0과 999,999 단 2개만 존재하는 경우,,, count 배열을 1,000,000 개 만들어야 한다는 단점이 있다.

array = =[7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(array)+1)	# (9+1)개의 리스트 -> 0부터 9까지의 개수를 담는 배열이다.

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 0 1 1 2 2 3 4 5 5 6 7 8 9 9         

데이터의 범윔만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.
사실상 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)와 더불어 가장 빠르다고 볼 수 있다.

이외

이외에도 병합정렬이나 버블정렬 같은 것들이 많이 있다.

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.
이는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 이는 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
이러한 sorted()함수는 리스트나 딕셔너리 자료형 등을 입력 받아 정렬된 결과를 출력한다.
또한 리스트 객체의 내장 함수인 sort()를 이용할 수도 있다.
위의 두 함수를 사용할 때는 key 매개변수를 입력으로 받을 수 있는데, 이 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

result = sorted(array)
# or
array.sort()
arrya = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
	return data[1]

result = sorted(array, key=setting)
print(result)
# 결과는 [('바나나', 2), ('당근', 3), ('사과', 5)]

정렬 라이브러리의 시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
따라서 별도의 요구가 없는 상황이라면 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬ㄹ을 사용하자.

참고

해당 블로그는 나동빈님의 '이것이 취업을 위한 코딩 테스트다. with 파이썬' 교재와 유튜브 강의를 참고하여 작성되었습니다.

profile
나만 읽을 수 있는 블로그

0개의 댓글