[Algorithm] 정렬 | 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

정렬이란 주어진 데이터를 특정 기준에 따라 순서대로 나열하여 재배치하는 것을 말한다.

정렬된 배열에서 원하는 값을 탐색하는 이진 탐색(Binary Search)를 위해서는 정렬 알고리즘을 잘 알아두어야 한다.

 

 

1. 선택 정렬

 

📌 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 교환하는 과정을 반복

 

swap(리스트에서 두 원소의 위치를 변경하는 작업)을 이용하면 선택정렬을 쉽게 구현할 수 있다.

 

arr = [4,3,1,7,2,8,6,5]

for i in range(len(arr)):
	min_index = i # 우선 가장 작은 원소의 인덱스로 맨 앞의 원소를 지정
    for j in range(i+1, len(arr)): # 맨 앞 원소 제외
    	if arr[min_index] > arr[j]: # 가장 작은 원소로 지정한 원소보다 더 작은 원소가 있다면
        	min_index = j # 이제부터 그 원소의 인덱스가 가장 작은 원소의 인덱스
    
    arr[i], arr[min_index] = arr[min_index], arr[i] # swap

 

📌 선택 정렬의 시간 복잡도: O(N^2)

→ 탐색 범위가 N에서 1씩 줄어들기 때문에, 아래 수식을 따른다.

 

 

2. 삽입 정렬

 

📌 특정한 데이터를 기준으로 다른 데이터를 적절한 위치에 삽입한다.

 

 

arr = [4,3,1,7,2,8,6,5]

for i in range(1, len(arr)):
	for j in range(i, 0, -1) # 인덱스 i부터 1까지 감소하여 반복하는 수열(=한 칸씩 왼쪽으로 이동)
    	if arr[j] < arr[j-1]: # 나보다 큰 데이터를 만나면
        	arr[j], arr[j-1] = arr[j-1], arr[j] # 만난 데이터랑 위치 변경
        else: # 나보다 작은 데이터를 만나면 멈춤
        	break

 

📌 삽입 정렬의 시간 복잡도: O(N^2)

※ 정렬해야하는 리스트가 거의 정렬되어있는 상태: O(N) → 이 경우에는 퀵정렬보다 삽입 정렬의 효과 강력

 

 

3. 퀵 정렬

 

📌 피벗(기준이 되는 데이터)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 

 

 

※ 호어 분할 방식의 퀵 정렬 → 리스트에서 첫 번째 데이터를 피벗으로 결정

 

(1) 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.  

(2) 양쪽에서 찾았다면 두 데이터의 위치를 서로 변경한다.

(3) 왼쪽에서 찾는 값과 오른쪽에서부터 찾는 값의 위치가 엇갈렸다면(예시 참고) 둘 중 작은 데이터와 피벗의 위치를 변경한다.

(4) 이동한 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트가 나뉜다. 각각 퀵 정렬을 다시 수행해준다.

(5) 현재 리스트의 데이터 개수가 1개면 퀵 정렬이 종료된다.

 

 

Case1.

 

arr = [4,3,1,7,2,8,6,5]

def quick_sort(arr, start, end):
	if start >= end:
    	return
    
    pivot = start # 첫 번째 원소를 피벗으로 설정
    left = start + 1 # 왼쪽에서부터 고고
    right = end # 오른쪽에서부터 고고
    
    while left <= right: # 화살표 엇갈리지 않는 동안
    	# left가 끝에 닿지 않고 left 원소가 피봇보다 작으면 keep going 
    	while left <= end and arr[left] <= arr[pivot]:
        	left += 1 # 피봇보다 큰 원소를 찾아야 하기때문에 계속 오른쪽으로 계속 이동
            
        # left가 start에 닿지 않고 right 원소가 피봇보다 크면 keep going
        while right > start and arr[right] >= arr[pivot]:
        	right -= 1 # 피봇보다 작은 원소를 찾아야 하기 때문에 계속왼쪽으로 계속 이동
            
        if left > right: # 엇갈렸다면 작은 데이터와 피벗 위치 교환
        	arr[right], arr[pivot] = arr[pivot], arr[right]
        
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터 교체
        	arr[left], arr[right] = arr[right], arr[left]
   
	# right가 이제 (전)피봇이므로 right를 기준으로 다시 수행
	quick_sort(arr, start, right - 1)
	quick_sort(arr, right + 1, end) 
    

quick_sort(arr, 0, len(arr)-1)

 

 

Case2.

 

arr = [4,3,1,7,2,8,6,5]

def quick_sort(arr):
	if len(arr) <= 1:
    	return arr
        
    pivot = arr[0]
    tail = arr[1:] # 피벗을 제외한 리스트
    
    left_arr = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분 -> 피봇보다 작은 원소들
    right_arr = [x for x in tail if x > pivot] # 분할된 오른쪽 부분 -> 피봇보다 큰 원소들
    
    return quick_sort(left_arr) + [pivot] + quick_sort(right_arr)
    
    
quick_sort(arr)

 

 

📌 퀵 정렬의 시간 복잡도: O(NlogN)

 

※ 최악의 경우 시간 복잡도 O(N^2)

→ 피벗을 리스트의 가장 왼쪽 데이터로 정할 때 이미 리스트가 정렬되어 있는 경우 (삽입 정렬과 반대로 동작)

 

 

4. 계수 정렬

 

📌 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때, 별도의 리스트를 선언해 데이터의 개수를 담아 정렬에 사용한다.

 

 

arr = [4,3,1,2,3,2,1,2,0]

count = [0] * (max(arr) + 1)

for i in range(len(arr)):
	count[arr[i]] += 1
    
for i in range(len(count)):
	for j in range(count[i]):
    	print(i, end=' '))

 

 

📌 계수 정렬의 시간 복잡도: O(N+K) 보장  → 데이터의 개수: N, 데이터 중 최대값의 크기: K

 

 

📌 계수 정렬의 공간 복잡도: O(N+K) → 데이터의 개수: N, 데이터 중 최대값의 크기: K

 

→ 데이터가 0과 999,999 단 2개일 경우 심각한 비효율성 초래

→ 동일한 값을 가지는 데이터가 여러 개 등장할 때 효율적 

 

 

5. 파이썬의 정렬 라이브러리

 

파이썬의 내장 함수인 sort()를 사용할 경우 시간 복잡도 O(NlogN) 보장

 

 

 

※  본 게시글은 이것이 취업을 위한 코딩테스트다 with 파이썬을 참고하여 구현하였습니다.