[이코테 python] 정렬 - 선택,삽입,퀵,계수 정렬과 예제

🔊 본 포스팅의 내용은 나동빈님의 [이것이 취업을 위한 코딩테스트다] 유튜브 강의를 수강 후 정리한 내용을 기록한 글로, 모든 사진과 자료의 출처는 해당 영상에 있습니다.

훌륭한 강의로 지식을 전달해 주신 나동빈님께 감사의 말씀을 전합니다.

 

목차

• 정렬 알고리즘
• 선택 정렬
• 삽입 정렬
• 퀵 정렬
• 계수 정렬
• 정렬 알고리즘 비교하기
• 정렬 알고리즘 예제

 

선택 정렬

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

선택 정렬 동작 예시

 

선택 정렬은 반복시마다 탐색 범위가 줄어듭니다.

 

선택 정렬 코드

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] # 스와프

print(array)

# 실행결과 : [0,1,2,3,4,5,6,7,8,9]

 

선택 정렬의 시간 복잡도

• 선택정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.
• 구현 방식에 따라 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같습니다.
  • N + ( N - 1 ) + ( N - 2 ) + … + 2
• 이는 ( N^2 + N - 2 ) / 2 로 표현 할 수 있으며, 빅오 표기법에 따라 O(N^2) 이라고 작성합니다.

---

삽입 정렬

- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.
- 선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 더 효율적으로 동작합니다.

 

삽입 정렬 동작 예시

 

삽입 정렬 코드

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까지 1씩 감소하며 반복하는 문법
		if array[j]<array[j-1]: # 한 칸씩 왼쪽으로 이동
			array[j], array[j-1] = array[j-1], array[j]
		else: # 자기(array [j) 보다 작은 데이터를 만나면 그 위치에서 멈춤
			break

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

삽입 정렬의 시간 복잡도

• 삽입 정렬의 시간 복잡도는 O(N^2) 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됩니다.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다.
  • 최선의 경우 O(N)의 시간 복잡도를 가집니다.

---

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다.
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다.
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다.
• 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터( Pivot )로 설정합니다

퀵 정렬 동작 예시

 

 

 

이처럼 퀵정렬이 수행되는 과정은 재귀적으로 수행됩니다.

 

퀵 정렬이 빠른 이유?

• 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NllogN)를 기대할 수 있습니다.
  • 너비 X 높이 = N x logN = NlogN

단순히 생각했을 때, 전체 데이터에 대해서 퀵정렬을 이용해서 데이터가 반씩 분할되었다고 가정해봅시다.
이상적인 경우 데이터의 범위가 절반씩 줄어들기 때문에, 전체 높이를 logN이라고 할 수 있습니다.
따라서 , 데이터의 개수가 N이고 높이가 logN이기 때문에 NlogN의 시간복잡도를 기대할 수 있습니다.

 

• 최악의 경우 O(N^2)의 시간복잡도를 가집니다.
• 이유 : 이미 정렬된 배열에 대해 수행했을때, 이중 반복문 전체를 돌며 full-scan을 하게 됩니다.

퀵 정렬 코드

1. 일반적인 방식

array = [5,7,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):
    	# 피벗보다 큰 데이터를 찾을 때까지 반복
        while(left<=end and array[left]<=array[pivot]):
        	left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right>start and array[tight]>=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)

 

2. 파이썬의 장점을 살린 방식

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

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)
    
print(quick_sort(array))

 

 

---

계수 정렬

• 특정한 조건이 부합할 떄만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘입니다.
• 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다.
• 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장합니다.

계수 정렬 동작 예시

 

 

 

 

계수 정렬 소스 코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
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 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

계수 정렬의 복잡도 분석

• 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+K)이다.
• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
  • 데이터가 0과 999,999로 단 2개만 존재하는 경우, 백만개 만큼의 원소가 담길 수 있는 배열을 만들어야 한다.
• 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.
  • 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 떄문에 계수 정렬이 효과적이다.

---

 

정렬 알고리즘 비교하기

대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있습니다.

위에서 다룬 네 가지 정렬 알고리즘을 비교하면 다음과 같습니다. 

 

---

문제 : 두 배열의 원소 교체

 

 

내 풀이

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

for _ in range(k):
		min_a = min(a)
		max_b = max(b)
    a[a.index(min_a)],b[b.index(max_b)] = max_b,min_a
print(sum(a))

• K번 도는 반복문
• min(a), max(b), index 연산 : 각 O(n)
• O(K(n+n+n)) = O(nk)*
• 즉, n과 k가 최댓값인 10,000,000일 경우 시간 제한 내에 수행되지 않는다.
  • 내가 짠 코드의 최악의 시간 복잡도가 O(10^5 * 10^5) = O(10^10)이므로, O(10^8) 연산의 수행이 1초라 가정할 때, 약 100초가 걸리기 때문.

이코테 설명

• 핵심 아이디어 : 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체합니다.
• 가장 먼저 배열 A와 B가 주어지면 A에 대하여 오름차순 정렬하고, B에 대해 내림차순 정렬합니다.
• 이후 두 배열의 원소를 첫 번쨰 인덱스부터 차례로 확인하며 A의 원소가 B의 원소보다 작을 때에만 교체를 수행합니다.
• 이 문제에서는 두 배열의 원소가 최대 100,000개 까지 입력될 수 있으므로, 최악의 경우 O(NlogN)울 보장하는 정렬 알고리즘을 이용해야합니다.

이코테 풀이

n,k = map(int,input().split()) # N과 K를 입력받기
a = list(map(int,input().split())) # 배열 A의 모든 원소 입력받기
b = list(map(int,input().split())) # 배열 B의 모든 원소 입력받기

a.sort() # 배열 A는 오름차순 정렬 수행
b.sort() # 배열 B는 내림차순 정렬 수행

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
	# A의 원소가 B의 원소보다 작은경우
	if a[i] < b[i]:
		a[i],b[i] = b[i],a[i]
	else : # A의 원소가 B의 원소보다 크거나 같을떄, 반복문을 탈출
		break

print(sum(a)) # 배열 a의 모든 원소의 합을 출력