정렬

선택 정렬

매번 가장 작은 것을 선택한다.
시간복잡도 : O(N^2)

1. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾼다.
2. 맨 앞의 데이터를 제외한 나머지 데이터들로 1의 과정을 반복한다.

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]

print(array)

삽입 정렬

정렬된 리스트에 새로운 데이터를 순서에 맞게 삽입한다.
데이터가 정렬되어 있을수록 효율적
시간복잡도 : O(N^2)
정렬된 리스트 최선 : O(N)

1. 첫 번째 수는 정렬되어 있다고 보고 두 번째 수부터 판단한다.
2. 오름차순인 경우 새로운 데이터보다 큰 데이터를 만나면 왼쪽에 삽입한다.

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

퀵 정렬

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나눈다.
시간복잡도 : O(NlogN)
이미 정렬되어 있는 경우 최악 : O(N^2)

1. 리스트에서 첫 번째 데이터를 피벗(기준)으로 정한다.
2. 왼쪽에서부터 피벗보다 큰 데이터, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
3. 큰 데이터와 작은 데이터의 위치를 바꾼다.
4. 3을 반복하다가 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 인덱스가 엇갈린 경우, 작은 데이터와 피벗의 위치를 바꾼다.
5. 피벗의 왼쪽에는 피벗보다 작은 데이터만, 피벗의 오른쪽에는 피벗보다 큰 데이터만 남으면서 분할된다.
6. 정렬하는 모든 리스트의 원소가 1개가 될 때까지 1~5를 반복한다.

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

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

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있는 매우 빠른 알고리즘
데이터의 크기가 한정되어 있고 데이터가 많이 중복되어 있을수록 유리
시간복잡도 최악 : O(N + K) # K : 데이터 중 최댓값

[계수 정렬 사용 조건]
1. 모든 데이터가 양의 정수
2. 데이터의 크기 범위를 정수 형태로 표현 가능
3. 최댓값과 최솟값의 차이가 크면 쓰기 어렵다.

1. 최댓값과 최솟값이 모두 담길 수 있는 범위의 리스트를 생성한다.
2. 데이터를 하나씩 뽑아 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
3. 리스트의 첫 번째 데이터부터 값만큼 인덱스를 출력하면 정렬된 리스트를 볼 수 있다.

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

정렬 라이브러리

앵간하면 이게 최고다.
병합정렬 기반.
시간복잡도 : O(NlogN) 보장

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

array.sort()
array.sort(reverse=True)
sorted_array = sorted(array)

array2 = [('홍길동', 95), ('이순신', 77)]
sorted_array2 = sorted(array2, key=lambda x:x[1])

결론😎

그냥 정렬할 때 : sort()
데이터의 범위가 한정적이고 더 빠르게 동작해야 할 때 : 계수 정렬