Chapter 06 : 정렬

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

선택 정렬
순서대로 탐색하며 정렬되지 않은 데이터 중에서 가장 작은 데이터를 정렬되지 않은 데이터 중 가장 앞과 바꿈

• 시간 복잡도 : O(N^2)

삽입 정렬
삽입될 데이터가 이미 정렬되어 있다 가정하고, 데이터를 적절한 위치에 삽입함
하나씩 넣고, 넣기 전 이미 정렬이 돼있기 때문에 탐색하다 삽입될 데이터보다 작은 숫자 오른쪽에 삽입하면 됨

• 시간 복잡도 : O(N^2), 최선의 경우 O(N) (리스트가 거의 정렬돼 있는 경우)

퀵 정렬
기준인 피봇과 가장 가까운 큰 숫자와 가장 먼 작은 숫자를 교환하며, 교환 중 가장 가까운 큰 숫자가 가장 먼 작은 숫자보다 멀어지면 가장 먼 작은 숫자를 피봇과 교환한 후 분할하여 반복 진행함

• 시간 복잡도 : O(N
  logN), 최악의 경우 O(N^2) (이미 데이터가 정렬되어 있는 경우)

계수 정렬
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있음 (큰 데이터와 작은 데이터의 차이가 너무 크지 않아야 함)

• 시간 복잡도 : O(N + K) (K : 최댓값)

• 공간 복잡도 : O(N + K)

sorted()

기본 정렬 라이브러리
최악의 경우에도 시간 복잡도 O(NlogN)을 보장
리스트, 딕셔너리 자료형들을 입력받아서 정렬된 결과를 리스트 자료형으로 출력

sort()

리스트 내부원소를 정렬

key를 이용하여 정렬

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

result = sorted(array, key = setting)

print(result)

output:
  [('바나나', 2), ('당근', 3), ('사과', 5)]