정렬

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

• '알고리즘의 효율성' 을 쉽게 이해할 수 있다.
• 다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음

파이썬의 정렬 라이브러리

sorted() VS .sort()

sorted() _ 함수

• 병합 정렬 기반의 함수
• 리스트, 딕셔너리 자료형 등을 입력받아 정렬된 결과를 출력
• 집합이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형

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

result = sorted(array)
print(result)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(array)
# [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

.sort() _ 리스트 객체의내장 함수

• 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬됨

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

array.sort()
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

정렬 라이브러리의 시간 복잡도

• 최악의 경우에도 시간 복잡도 $O(NlogN)$을 보장한다.

---

Bubble Sort (버블정렬)

Idea

• 두 인접한 데이터를 비교해서 자리를 바꾼다
  참고: https://visualgo.net/en/sorting

출처: https://en.wikipedia.org/wiki/Bubble_sort

How To

1. 두개의 인접한 데이터를 비교하고,
2. 앞의 데이터가 뒤의 데이터보다 크면 자리를 바꾼다

Code

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

for i in range(len(array)-1):
    for j in range(len(array)-i-1):
        if array[j] > array[j+1]:  # 두개의 인접 데이터 비교
            array[j], array[j+1] = array[j+1], array[j]  # swap
            
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Analysis

• 시간복잡도 = $O(N^2)$
• 완전 정렬 되어있으면 최선의 시간복잡도 = $O(N)$

---

Selection Sort (선택정렬)

Idea

• 매번 가장 작은 것을 '선택'한다
  참고: https://visualgo.net/en/sorting

출처: https://en.wikipedia.org/wiki/Selection_sort

How To

1. 가장 작은 데이터를 선택해 만 앞에 있는 데이터와 바꾸고
2. 그 다음 작은 데이터를 앞에서 두 번째 데이터와 바꾸는 과정을 반복

Code

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

for i in range(len(array)):
    min_idx = i  # 가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        if array[min_idx] > array[j]:
            min_idx = j
    array[i], array[min_idx] = array[min_idx], array[i]  # Swap
    
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Analysis

• 시간복잡도 = $O(N^2)$
  1. N-1번만큼 가장 작은 수를 찾아 맨 앞으로 보내야 함
  2. 매번 작은 수를 찾기 위한 비교 연산 필요
  

---

Insertion Sort (삽입정렬)

Idea

• 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 '삽입'한다.
• 필요할 때만 위치를 바꾸무로 '데이터가 거의 정렬되어 있을 때' 효율적
  참고: https://visualgo.net/en/sorting

출처: https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

How To

1. 두 번째 인덱스부터 시작
2. 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
3. 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

Code

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):  # i부터 1까지 역으로 확인
        if array[j] < array[j-1]:  # 자기보다 크다면 한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else:  # 자기보다 작은 수를 만나면 멈춤
            break
            
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Analysis

• 시간복잡도 = $O(N^2)$
• 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
  - 완전 정렬되어있는 경우 시간복잡도 = $O(N)$