정렬

개념

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.

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)

시간 복잡도

선택 정렬의 전체 연산 횟수는 N + (N-1) + (N-2) + ... + 2 이다.
등차수열로 나타내면 (N^2 + N - 2) / 2 로 나타난다. 고로 빅오 표기법으로 O(N^2) 이다.

2. 삽입 정렬

개념

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

예시

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

for i in range(1, len(array)):
    for j in range(i):
        if array[i] < array[j]:
            array[i], array[j] = array[j], array[i]
        else:
            break

print(array)

시간 복잡도

반복문이 두번 중첩되어(for문 안에 간단한 스왑만 있어) O(N^2)인 것을 알 수 있다.
삽입 정렬의 장점은 데이터가 이미 거의 정렬되어 있다면 선택 정렬보다 매우 빠르게 동작한다는 점이다.

3. 퀵 정렬

개념

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

예시

def quick(array):
    if len(array) <= 1:
        return array

    more = []
    less = []

    for i in range(1, len(array)):
        if array[0] <= array[i]:
            more.append(array[i])
        else:
            less.append(array[i])

    return quick(less) + [array[0]] + quick(more)

이 코드에선 Pivot을 각 array의 index=0을 기준으로 했다. Pivot을 기준으로 more과 less를 나누고 재귀적으로 이를 반복해서 정렬한 값을 return 한다.

시간 복잡도

평균의 경우 O(NlogN)의 시간 복잡도를 가진다. 하지만 우리의 코드 처럼 Pivot을 항상 index=0으로 설정하면 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

표준 라이브러리에서는 적어도 O(NlogN)을 보장하는 시간 복잡도를 가지게 구현해놓았다.

4. 계수 정렬

개념

특정한 조건이 부합할 때만 사용 가능하다. HashMap의 개념을 활용해서 각 숫자마자 Count를 구해서 정렬하는 방식.

예시

def sort(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)이다.

만약 데이터가 0과 999999로 단 2개만 존재하면 매우 비효율적이다. 동일한 값을 가지는 데이터가 여러개 존재하고, 데이터의 편차가 심하지 않을 때 효율적이다.

예제

💡아이디어

A리스트를 오름차순으로 정렬하고, B리스트를 내림차순으로 정렬한다. 그리고 K만큼 A와 B의 원소를 교환하면 된다.

N, K = map(int, input('입력 = ').split())

arrayA = list(map(int, input().split()))
arrayB = list(map(int, input().split()))

arrayA.sort()
arrayB.sort(reverse=True)

for i in range(K):
    arrayA[i], arrayB[i] = arrayB[i], arrayA[i]

print(sum(arrayA))