[Python] 정렬 알고리즘 정리 : 선택 / 삽입 / 퀵 / 계수 정렬

< 비교 기반 정렬 알고리즘 >

1. 선택 정렬 : 가장 작은 데이터를 '선택'한 뒤 가장 앞으로 보내기

array = [7, 6, 3, 5] 
for i in range(len(array)):
	min_ind = i    # 비교 대상의 값을 min_ind로 설정
	for j in range(i+1, len(array)):
		if array[min_ind] > array[j]
		min_ind = j    # 가장 작은 원소의 인덱스를 min_ind로 설정
	array[i], array[min_ind] = array[min_ind], array[i]

print(array)

   - 시간 복잡도 : O(N^2)


2. 삽입 정렬 : 두번째 원소부터 움직이면서 정렬

array = [7, 6, 3, 5]
for i in range(1, len(array)):
	for j in range(i, len(array)):   # 모든 원소 확인
		if array[j] < array[j-1]:
			array[j], array[j-1] = array[j-1], array[j]
		else:
			break
print(array)

 

  - 시간 복잡도 : O(N^2)


3. 퀵 정렬 : 가운데 기준 피벗을 잡고 큰 데이터와 작은 데이터의 위치 교환

array = [7, 6, 3, 5]

def quick_sort(array):
	# 리스트가 하나 이하의 원소일 경우
	if len(array)<= 1: return array

	pivot = array[0]  # 첫번째 원소
	tail = array[1:]    # 피벗을 제외한 리스트

	left_array = [x for x in tail if x <= pivot]  # 분할된 왼쪽 부분
	right_array = [x for x in tail if x > pivot]  # 분할된 오른쪽 부분

	# 재귀적으로 정렬
	return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array)

 

  - 시간복잡도 : O(NlogN)

< 그 외 알고리즘 >

4. 계수 정렬
- 모든 범위의 데이터를 담을 수 있는 빈 배열 선언 후 데이터의 값과 동일한 인덱스에 넣기
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
- 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적
 ex) 성적 데이터

array = [7, 5, 6, 3, 2, 9, 0, 6, 5, 3, 1, 4]
# 모든 범위를 포함하는 리스트 선언 및 초기화
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]):    # count[i]만큼 숫자 출력
		print(i, end=' ')

 

  - 시간복잡도 : O(N+K) - 최악의 경우