# 정렬 알고리즘

정렬
: 데이터를 특정한 기준에 따라 순서대로 나열하는 것

1. 선택 정렬

처리되지 않은 데이터 중, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것
시간 복잡도는 O(N2)

ex. 

2 4 6 8 7 9 0 1 3 5 
가 있을 때, 
처리되지 않은 데이터 > 처음엔 전부 처리가 안되어 있는 상태니까 제일 작은 건 0 
> 0과 제일 앞에 있는 데이터인 2와 자리 바꾸기
0 4 6 8 7 9 2 1 3 5 으로 재정렬

이 중에 처리되지 않은 데이터는 맨 앞에 0 외에 
4 6 8 7 9 2 1 3 5
제일 작은 건 1이고, 맨 앞에 있는 데이터(4)와 자리 변경
0 1 6 8 7 9 2 4 3 5

위의 과정 반복

소스코드

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

2. 삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
선택 정렬에 비해 구현 난이도는 높지만, 일반적으로 더 효율적으로 동작한다
데이터가 거의 정렬되어 있을 때 가장 빠르다.

ex. 

7 5 9 0 3 1 6 2 4 8
가 있을 때, 
1. 제일 첫번 째 데이터는 그 자체로 정렬이 되어 있다고 가정.
두번 째 데이터인 5가 7의 왼쪽/오른쪽 중에 어디로 들어가는지 판단한다
값이 작으면 7의 왼쪽, 값이 크면 7의 오른쪽
>> 5 7 9 0 3 1 6 2 4 8

2. 세번째 데이터인 9를 확인
5의 앞 / 7의 앞 / 9의 앞 중에 어디로 들어가는 지 판단
5와 7보다 크니까 자리 그대로 유지하도록 하기

위의 과정 반복

소스코드

array = [7 5 9 0 3 1 6 2 4 8]
for i in range(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
            
print(array)        

3. 퀵 정렬 알고리즘

일반적으로 사용하는 정렬 알고리즘 중 가장 많이 사용됨
기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈
첫 번째 데이터를 기준 데이터(pivot)로 설정함
시간 복잡도 : O(NlogN)

ex. 

5 7 9 0 3 1 6 2 4 8
가 있을 때,

1. 기준(pivot)은 5.

왼쪽과 오른쪽에서 비교를 하면서 살펴본다.
왼쪽에서부터 5보다 큰 데이터를 찾고,
오른쪽에서부터 5보다 작은 데이터를 찾는다.

왼쪽에서 시작했을 때 >> 7 9 0 .... 
               >> 5보다 큰 데이터는 7
               
오른쪽에서 시작했을 때 >> 8 4 2 ... 
                >> 5보다 작은 데이터는 4
                
                7 과 4를 비교했을 때, 4가 작으니까 데이터 자리 변경
                >> 5 4 9 0 3 1 6 2 7 8
                

위의 과정 반복

소스코드

array = [15, 17, 19, 10, 13, 11, 16, 12, 14, 18]

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))

4. 계수 정렬

매우 빠르게 동작하는 정렬 알고리즘
데이터의 범위가 너무 크고 데이터는 적을 때(Ex. 0, 999,999 두개만 있을 때)는 너무 비효율적이다.
데이터의 크기 범위가 제한되어 정수 형태로 표현 할 수 있을 때 사용 가능

ex.

정렬 데이터 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
가장 작은 데이터부터 가장 큰 데이터까지의 범위가 담길 수 있는 리스트로 초기화
그럼 가장 작은 데이터(0) ~ 가장 큰 데이터(9) 니까
인덱스가 0 1 2 3 4 5 6 7 8 9 인 리스트가 만들어짐

인덱스 : 0 1 2 3 4 5 6 7 8 9
개수   : 각각의 인덱스의 값에 해당하는 숫자가 몇 번 나오는지 찾기

인덱스 : 0 1 2 3 4 5 6 7 8 9
개수  :  2 2 2 1 1 2 1 1 1 2 

데이터 출력 시, 인덱스에 해당 하는 값만큼 반복적으로 인덱스 출력
0이 두번 이니까, 0 0 // 1도 두번이니까 1 1 ....

출력결과 :
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

소스코드

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=' ')

출처