정렬

정렬

• 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 정렬 알고리즘은 공식처럼 사용되기도 함

선택 정렬

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

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

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

• 시간 복잡도는 $O(N^2)$ 이다.

삽입 정렬

: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

EX)
7 5 9 0 3 1 6 2 4 8 로 위치할 때
7은 제 자리를 지키고,
5는 7보다 작으므로 7 전으로 이동, -> 5 7 ...
9는 7보다 크므로 제자리,
0은 5보다 작으므로 5 전으로 이동, -> 0 5 7 9 ...

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) : #정확한 위치를 찾기 위해 
    	if array[j] < array[j-1]:
        	array[j], array[j-1] = array[j-1], array[j]
        else : # 더 작은 값을 만날 경우, 더 비교할 필요 없음 
        	break

• 선택정렬보다 구현 난이도 ↑ / 동작 효율 ↑
• 시간 복잡도는 $O(N^2)$ 이다.
• 현재 리스트 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
  • 최선일 때는 $O(N)$

퀵 정렬

: 기준 데이터를 설정하고, 그 기준 데이터보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

• 일반적인 상황에서 가장 많이 사용됨
• 정렬 라이브러리의 근간이 됨 (with 병합정렬)
• 첫번째 데이터를 기준 데이터(=pivot)로 설정
• 시간 복잡도는 평균 $O(NlogN)$, 최악일 경우 $O(N^2)$ 이다.

EX.

5 7 9 0 3 1 6 2 4 8 일 때,

Pivot = 5
왼쪽에서부터는 5보다 큰데이터를, 오른쪽에서부터는 5보다 작은데이터를 선택
-> 두 데이터의 위치를 서로 변경

-> 반복

-> 왼쪽/오른쪽에서 방향이 서로 엇갈리게 되는 순간, pivot과 작은데이터의 위치를 서로 변경.
기존 pivot을 기준으로 분할하면 5보다 작은 숫자들은 왼쪽에 / 5보다 큰 숫자들은 오른쪽에 위치하게 됨.

-> 왼쪽과 오른쪽 데이터를 각자 묶어 위의 과정 반복

파이썬 일반적인 코드

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

def quick_sort(array, start, end) : 
	if start >= end : # 원소가 한 개인 경우 종료 
    	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):
        	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)

파이썬 장점 살린 코드

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)

계수 정렬

: 정수 형태로 표현할 수 있을 때만 사용할 수 있음

• 시간 복잡도는 최악의 경우에도 $O(N+K)$를 보장함.
• 때에 따라 심각하게 비효율적임 (0, 999999 단 2개만 존재할 때)
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적

EX.
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 일 때,
정렬할 데이터의 범위만큼의 리스트 생성

-> 각 데이터가 몇 번 등장했는지 횟수 기록

-> 횟수만큼 인덱스를 출력

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
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=' ')