[알고리즘 with Python] - 정렬

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈

버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 계수정렬, 파이썬 기본 정렬 함수(sort, sorted) 코드 첨부

 

0. 정렬 문제풀이 방법

- 정렬 라이브러리로 풀 수 있는 문제(sort, sorted): 정렬 라이브러리 사용방법 숙지하기

- 정렬 알고리즘의 원리에 대해 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야함

- 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반으로도 해결이 불가능할때, 계수 정렬 등의 더 빠른 알고리즘을 이용하거나 구조적으로 개선하기

예시: 문제에서 리스트의 최대 원소가 100000처럼 크게 주어졌을땐 O(NlogN)인 정렬 라이브러리나 퀵 정렬을 사용한다. 

1. Bubble Sort(버블 정렬)

각 단계에서 인접한 두 개의 원소를 비교하고 가장 큰 or 가장 작은 수를 맨 뒤로 보내는 것을 반복한다.

(버블이 몽글몽글 올라오듯)

시간복잡도는 O(n^2), 정렬 알고리즘 중에서 제일 느리다. 

# 버블정렬
def bubble_sort(array):
    n = len(array)
    for i in range(n - 1):  		 # 리스트의 길이 - 1만큼 반복
        for j in range(n - 1 - i):  	 # 정렬 범위를 줄이기 위해 i를 제외한 만큼 반복
            if array[j] > array[j + 1]:  # 현재 원소가 다음 원소보다 크다면 위치 교환
                array[j], array[j + 1] = array[j + 1], array[j]
    print(array)

array = [7, 5, 9, 0, 3, 1, 6, 2, 8]
bubble_sort(array)

2. Selection Sort(선택 정렬)

각 단계에서 가장 작은 것을 선택해 앞에 있는 데이터와 바꾸는 것을 반복한다. 

시간 복잡도는 O(n^2), 다른 정렬보다 느리지만 코딩테스트에서 특정 리스트에서 가장 작은 데이터를 찾는 경우 사용된다. 

# 선택정렬 
def selection_sort(array):
    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						# 가장 작은 원소의 인덱스는 j가 된다.
        array[i], array[min_index] = array[min_index], array[i]		# 현재 원소(각 단계의 맨 앞)과 가장 작은 원소 swap
    print(array)

array = [7, 5, 9, 0, 3, 1, 6, 2, 8]
selection_sort(array)

3. Insertion Sort(삽입 정렬)

각 단계에서 특정 데이터의 왼쪽에 있는 데이터는 이미 정렬이 된 상태로 생각하고, 해당 특정 데이터를 적절한 위치에 삽입한다.(특정 데이터가 왼쪽의 데이터들과 비교하다가 자기보다 작은 데이터를 만났다면 그 자리에 삽입하면 된다. )  

시간 복잡도는 O(n^2), 데이터가 거의 정렬되어 있을 때 사용하면 효율적이다.

# 삽입정렬
def insertion_sort(array):
    for i in range(1, len(array)):  # 0번째(첫번째) 원소는 이미 정렬되었다 생각하므로 2번째 원소부터 삽입 시작
        for j in range(i, 0, -1):   # 인덱스 i부터 1까지 1씩 감소하기
            if array[j] < array[j-1]:   # 한 칸씩 왼쪽으로 이동하며 swap(삽입할 위치 찾기)
                array[j], array[j-1] = array[j-1], array[j]
            else:       # 자신보다 작은 원소(그 자리에 남음) 찾으면 그 위치에서 멈춤
                break
    print(array)
    
    array = [7, 5, 9, 0, 3, 1, 6, 2, 8]
    insertion_sort(array)

4. Quick Sort(퀵 정렬)

정렬 알고리즘 중 가장 많이 사용되는 알고리즘.

맨 처음 데이터를 기준 데이터(pivot)로 정하고 왼쪽에서부터 pivot보다 큰 데이터를 찾고, 오른쪽에서 pivot보다 작은 데이터를 찾고, 위치를 교환해준다. 교환이 완료되면 피벗 왼쪽과 오른쪽을또다시 재귀를 이용해 반복해준다. 리스트의 데이터 개수가 1개인경우 재귀를 종료한다.  

평균 시간 복잡도는 O(NlogN), 최악의 경우 시간복잡도는 O(N^2)이다.

데이터가 이미 어느정도 정렬되어 있기보단 데이터가 무작위로 입력될때 빠르게 동작할 확률이 높다.

(데이터의 특성을 파악하기 어려울 때)

# 퀵 정렬
def quick_sort(array):
    if len(array) <= 1: # 리스트가 하나 이하의 원소만을 담고 있다면 종료하기
        return array
    pivot = array[0]    # pivot을 포함한 
    tail = array[1:]    # pivot을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # pivot보다 작으면 left_side리스트에 저장
    right_side = [x for x in tail if x> pivot]  # pivot보다 크면 right_side리스트에 저장

    # 분할 후 왼쪽 부분과 오른쪽 부분에서 quick sort를 각각 진행하고, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

array = [7, 5, 9, 0, 3, 1, 6, 2, 8]
print(quick_sort(array))

5. Count Sort(계수 정렬)

특정한 조건이 부합할 때 사용가능하지만(데이터 크기 범위가 제한되고, 정수 형태로 표현할 수 있을 때),

가장 빠른 정렬 알고리즘. 앞선 정렬들처럼 비교 정렬이 아니라, 새로운 리스트를 만들고 카운트를 센다.

먼저 가장 큰 데이터와가장 작은 데이터의 범위가 모두 담길 수 있도록 리스트를 생성하고, 각 데이터가 몇 번 등장했는지 횟수를 카운트한다. 

동일한 값을 가지는 데이터가 여러 개 등장할때 사용이 적합하다. (ex) 학생들의 성적 정렬)

시간복잡도는 데이터의 개수가 N, 최대값의 크기를 K라고 할 때 O(N + K)다. 공간복잡도도 마찬가지로 O(N+K)다.

# 계수 정렬
def count_sort(array):
    count = [0]*(max(array) + 1)	# 모든 범위를 포함하는 리스트 선언하기(모든 값은 0으로 초기화하기)

    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보다 크거나 같은 양의 정수라고 가정 
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count_sort(array)

6. 정렬 라이브러리 이용

- sorted함수, list구조의 메서드 sort()를 이용할 수 있다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 8]
result = sorted(array)
print(result)

result = array.sort()
print(result)

- reverse 매개변수 이용하기: True로 설정하면 내림차순으로 구해준다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 8]
result = array.sort(reverse = True)
print(result)

- key 이용하기: 어떤 값을 기준으로정렬할지 정한다 . 하나의 함수가 들어간다. 람다 함수를 사용할 수도 있다.

array = [('바나나',2), ('사과',5),('당근',3)]
def setting(data):
    return data[1]
result = sorted(array, key = setting)
print(result)

- 2차원 리스트도 sort()를 이용하면 자동 정렬이 가능하다.