개요

• 정렬
  • 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
  • 데이터를 정렬해두면 이진탐색이 가능해진다.
• 대표적으로
  • 선택정렬
  • 삽입정렬
  • 퀵정렬
  • 계수정렬

선택정렬 (Selection Sort)

선택정렬
가장 작은 데이터를 선택해, 맨 앞에 있는 데이터와 바꾸고
그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복

과정

코드

• 정렬 완료한 부분 ~ 끝 까지 판단 반복
  • 판단 = 가장 작은 원소 찾아서 swap
• 종료조건 : 길이가 n이면 n-1번째에 모든 정렬이 완료되므로 끝남

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] # 정렬되지 않은 부분 중 가장작은 원소 <->  정렬되지 않은 부분 중 제일 앞 원소  swap

print(array)

시간복잡도

$O(N^2)$

• 연산횟수는 N + (N-1) + (N-2) + ... + 2 번 연산
• 근사치로 N*(N+1)/2 번 연산
• big O 표기로 $O(N^2)$
• 비효율적이지만, 특정 리스트에서 가장 작은 데이터 찾는일이 코테에서 잦으므로, 선택정렬 소스코드 형태에 익숙해질 필요가 있다.

삽입정렬

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하기
데이터가 거의 정렬되어있을때 유리하다.

과정

_판단한다는 것은?

재밌게도

이렇게 정렬 완료된 부분들은 오름차순을 유지하고 있기 때문에

삽입될 위치를 선정할때, 자기보다 작은 데이터를 만나면 그 위치에서 멈추면 된다. 그 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로, 더 살펴볼 필요가 없다.

코드

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

for i in range(1, len(array)) : # 총 n-1 번 반복하면 정렬이 끝난다
	# '삽입하기 적절한' 위치를 뒤에서부터 찾는다
	for j in range(i, 0, -1 ):
		if array[j] < array[j-1] : # 자기보다 크다 = 삽입하기 적절하지 않음. 한 칸씩 왼쪽으로 이동
			array[j], array[j-1] = array[j-1], array[j] # swap
		else : # 자기보다 작은 데이터를 처음 만난다 = 삽입하기 적절함. 그 위치에서 멈춤
			break

print(array)

시간복잡도

$O(N^2)$
다만, 데이터가 거의 정렬되어있는 상태라면 매우 빠르게 동작
(최선의 경우 $O(N)$)

퀵정렬

가장 많이 사용됨.

pivot을 설정하고
왼쪽끝부터 pivot보다 큰 데이터 <-> 오른쪽끝부터 pivot보다 작은 데이터를 교환
양쪽끝이 만나면, 작은 데이터 <-> pivot 교환
그러면 [(pivot보다 작은 원소들), pivot, (pivot보다 큰 원소들)] 이 된다.
이렇게 pivot 기준으로 리스트를 반으로 나누어서, 앞의 과정을 반복한다.
나누어진 리스트의 길이가 1일때까지 반복한다.

동작 과정

전통적인 Hoare partition 기준

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[right] >= array[pivot] :
			right -= 1
		if left > right : #엇갈렸다면 작은 데이터 <-> pivot swap
			array[right], array[pivot] = array[pivot], array[right]
		else : # 엇갈리지 않았다면 왼쪽에서부터 처음 만난 작은 데이터 <-> 오른쪽에서부터 처음 만난 큰 데이터 swap
			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)

파이썬의 장점을 살리지만, 시간은 약간 불리한 코드

# 파이썬의 장점을 살린 퀵 정렬
# 기존 퀵 정렬 분할방식과 조금다른데, 피벗<->데이터 비교하는 비교연산 횟수가 증가하므로 시간면에서는 비효율적이다.
# 하지만 더 직관적이고 기억하기 쉽다.

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)

시간복잡도

• 평균 시간복잡도 : $O(NlogN)$
• 최악 시간 복잡도 : $O(N^2)$
• 사용상황
  • 데이터가 무작위 입력될때 퀵정렬을 빠르게 작동할 확률 적음
  • 이미 데이터가 어느정도 정렬되어있는 경우 불리함
  • 삽입정렬과 반대임을 알 수 있다.

• 다른 복잡도와 비교

  • 선택, 삽입정렬은 최악의 경우에 항상 $O(N^2)$ 보장
  • 퀵은 '평균복잡도'의 경우 유리하다.

• 증명

  • 시간복잡도 구체적 증명은 까다롭고,
    절반으로 나누어 떨어지는 과정=높이가 $log_2N$ 이며
    데이터의 갯수는 N개이므로 $O(NlogN)$$$ 라고 이해하면 된다.

• 대부분의 정렬 라이브러리에서

  • 추가적인 로직을 더해줘서 최악의 경우에도 O(NlogN)을 보장한다.

계수 정렬

특정한 조건이 부합할때만 사용할 수 있지만, 매우 빠른 알고리즘
qufeh fltmxmfmf

사용상황

• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때 사용가능
  • 데이터의 갯수는 매우 많더라도 빠르게 작동한다
• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000를 넘지 않을때 효과적으로 사용가능
  • ex) 0이상 100이하인 성적 데이터 정렬할때

작동 과정

예시) [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

0) [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 리스트 생성

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0

이 이후 부터 데이터를 하나씩 확인하며, 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수정렬 끝!

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

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0

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

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	1	0	1	0	0

3) [~~7, 5, 9 ~~, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	1	0	1	0	1

.... 반복 ....

15) [7, 5, 9 , 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

0	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

출력 ) 차례로 출력하면 된다.
[0 ,0 ,1 ,1 ,2 ,2 ,3 ,4 ,5 ,5 ,6 ,7 ,8 ,9 ,9]

코드

# 계수 정렬

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

# 모든 범위를 포함하는 리스트 선인 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

# counting 과정
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=' ')

시간복잡도

데이터 갯수가 N, 데이터 최댓값이 K일때
최악의 경우 O(N+K).
현존하는 정렬알고리즘 중 기수정렬(Radix Sort)와 더불어 가장 빠르다

데이터의 크기가 한정되어있고, 데이터의 크기가 많이 중복되어있을 수록 유리하다.

공간복잡도

데이터의 갯수가 너무 많다면, 공간복잡도에서 심각하게 비효율적이다.
데이터의 크기가 한정되어있고, 데이터의 크기가 많이 중복되어있을 수록 유리하다.

파이썬의 정렬 라이브러리

• 최악의 경우에도 $O(NlogN)$ 보장
• sorted()
  • param 을 정렬한 새로운 리스트를 리턴
• sort()
  • param을 정렬