[Python] 정렬

정렬은 특정한 기준으로 나열한다. 선택정렬, 삽입정렬, 퀵정렬, 계수정렬 등 많은 정렬 방식이 있다.

 

선택정렬

주어진 리스트에서 가장 작은 데이터를 선택해 맨 앞 데이터와 교체, 그 다음 작은 데이터를 찾아 두번째 데이터와 교체하면서 정렬한다. 

for i in range(len(array)):
	min_idx = i	#최소값 인덱스
	for j in range(i+1, len(array)):
		if array[min_idx] > array[j]: # 최소값보다 작은 값을 찾음
			min_idx = j
	array[i], array[min_idx] = array[min_idx], array[i] # swap

 

삽입정렬

데이터를 하나씩 확인하면서 각 데이터를 적절한 위치에 삽입한다. 구현할 때, 리스트를 읽으면서 왼쪽 데이터와 비교하며 작으면 교체하면서 정렬한다.

for i in range(1, len(array)):
    for j in range(i, 0, -1): # j는 i부터 리스트 왼쪽으로 1칸씩 이동
        if array[j] < array[j-1]: # 현재 위치 값이 좌측의 값보다 작은 경우
            array[j], array[j-1] = array[j-1], array[j] # swap
        else:
            break # 큰 경우 다음 위치로

 

퀵정렬

기준이 되는 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터 위치를 바꾼다. 작은 데이터, 큰 데이터 반으로 나눠서 다시 반복한다. (재귀함수 사용)

# 원래 구현하는 방식이 아니지만, 좀 더 쉽게 구현하는 방식으로
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) # 각각 다시 퀵정렬

 

계수정렬

특정한 상황에서만 사용하지만 빠르게 정렬할 수 있다. 별도의 리스트를 생성해 값을 카운트하고 순서대로 출력하여 정렬한다.

cnt = [0] * (max(array) + 1) # 별도의 리스트 생성
for i in range(len(array)):
    cnt[array[i]] += 1 # array의 값을 인덱스로 있을때마다 카운트

 

파이썬에서 정렬 라이브러리

sorted, sort를 사용한다. sorted는 반환값으로 받아야 한다.