정렬

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

→ 선택정렬, 삽입정렬, 퀵정렬, 계수정렬등이 존재

선택 정렬

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

예시 카드 정렬

7 5 9 0 3 1 6 2 4 8

1. 가장 작은 0 선택, 7과 바꿈: 0 5 9 7 3 1 6 2 4 8
2. 다음으로 작은 수인 1 선택, 5와 변경: 0 1 9 7 3 5 6 2 4 8
3. 과정 반복

이 과정을 N-1번 반복하면 정렬 완료

코드

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

for i in range(len(array)):
    min = i
    for j in range(i + 1, len(array)):
        if array[min] > array[j]:
            min = j
    array[i], array[min] = array[min], array[i]
    
print(array)

시간 복잡도

• n-1번 가장 작은 수를 찾아 앞으로 보내야한다.

• 작은 수를 찾기 위한 비교 연산이 필요하다.

  n + (n-1) + … + 2 = O(n^2)

  • 2중 반복문 때문

• 파이썬의 기본 정렬 라이브러리보다 느린 비효율적인 알고리즘 중 하나

삽입 정렬

데이터를 하나씩 확인해 적절한 위치에 삽입하는 정렬 방식

• 필요할 때만 위치를 변경해 데이터가 거의 정렬되어 있을 때 효율적인 알고리즘

예시 카드 정렬

7 5 9 0 3 1 6 2 4 8

1. 7은 이미 정렬되어 있다 판단하고 다음 데이터인 5가 어디에 들어가야할 지 판단
   • 7 왼쪽 vs 7 오른쪽
   • 7보다 작은 수이므로 왼쪽으로 삽입
   • 5 7 9 0 3 1 6 2 4 8
2. 9가 어디에 들어갈지 판단. 7보다 크므로 pass
   • 7 5 9 0 3 1 6 2 4 8
3. 0이 어디로 들어갈지 판단. 5보다 작으므로 5 왼쪽에 삽입
   • 0 7 5 9 3 1 6 2 4 8
4. 과정 반복

이 과정을 n-1번 반복하면 정렬 완료

코드

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)

시간 복잡도

• O(n^2) - 2중 반복문 때문
• 하지만 데이터가 거의 정렬되어 있는 경우 빠르게 동작: O(N)

퀵 정렬

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

• pivot을 설정하여 정렬: 교환을 위한 기준
• pivot을 어떻게 설정할 것인지 명시해야 함

예시 카드 정렬

5 7 9 0 3 1 6 2 4 8

1. 첫번째 데이터인 5를 피벗으로 설정
   • 5 7 9 0 3 1 6 2 4 8: 왼쪽에서 5다 큰 수, 오른쪽에서 5보다 작은 수를 찾는다: 7, 4
   • 5 7 9 0 3 1 6 2 4 8: 4와 7의 위치 변경
   • 5 4 9 0 3 1 6 2 7 8: 2와 9의 위치 변경
   • 5 4 2 0 3 1 6 9 7 8: 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 순서가 엇갈리가 된 경우 피벗의 위치 변경된다.
   • 1 4 2 0 3 5 6 9 7 8: 1차 완료
2. 왼쪽, 오른쪽 리스트 각각 정렬반복

이 과정을 n-1번 반복하면 정렬 완료

코드

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

시간 복잡도

• O(nlogn): 선택정렬, 삽입 정렬보다 빠르다 - 2중 반복문 때문
• 최악의 경우 O(n^2): 이미 데이터가 정렬되어있는 경우

계수 정렬

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

• 모든 데이터가 양의 정수인 상황
• 데이터의 개수 N, 데이터의 최댓값이 K
• 알고리즘 수행시간 O(n+k) 보장
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 경우에만 사용가능
• 가장 큰 데이터와 작은 데이터가 1,000,000을 넘지 않을 경우 효율적
• 모든 범위를 담을 수 있는 리스트를 선언해야하기 때문

예시 카드 정렬

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

1. 가장 앞의 수인 7부터 정렬: 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	1	0	0

2. 다음 5 정렬: 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. 과정 반복

리스트의 첫번째 데이터부터 하나씩 값의 인덱스만큼 출력하면 된다.

코드

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


print(max(array))

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

시간 복잡도

• O(n + k): 데이터의 개수 n, 최대값의 크기 k

공간 복잡도

• 데이터가 0과 999,999 2개 존재해도 리스트 크기를 100만개 만들어야 한다.
• 따라서 항상 사용할 수 있는 알고리즘은 X
• 동일한 값을 가지는 데디터가 여러개 등장할 때 적합
• 데이터의 크기가 한정 되어 있고 데이터 크기가 많이 중복된 경우 유리한 것을 꼭 기억!

파이썬의 정렬 라이브러리

sorted() 함수가 제공된다.

• 병합 방식을 기반으로 만들어졌다.
• 최악의 경우에도 O(NlogN)을 보장

문제 유형

1. 라이브러리를 사용해 풀 수 있는 문제: 단순 정렬 기법을 알고 있는지 물어보는 문제
2. 정렬 알고리즘의 원리를 물어보는 문제: 정렬의 원리를 알고있어야 풀 수 있는 문제
3. 더 빠른 정렬이 필요한 문제: 퀵정렬 기반으로 풀 수 없으며 계수정렬 등의 알고리즘 이용 또는 기존 알려진 알고리즘의 구조적 개선을 거쳐야 풀 수 있음