정렬(Sorting)

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

정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다.

정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해진다.

정렬 알고리즘을 공부하다 보면 자연스럽게 알고리즘 효율의 중요성을 깨닫는다.

정렬 알고리즘 또한 매우 중요하다. 면접에서도 단골 문제로 출제된다.

내림차순 정렬은 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기(Reverse)하여 내림차순 리스트를 만들 수 있다.

리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있다.

 

(1) 선택 정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸며 정렬한다.

# 앞으로 보내는 과정을 N-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)

결과 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

스와프 : 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

[5, 3]

 

선택 정렬의 시간 복잡도
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, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

삽입 정렬의 시간 복잡도

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

수행 시간을 테스트해보면 선택 정렬과 흡사한 시간이 소요되는 것을 알 수 있다.

삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

최선의 경우 O(N)의 시간 복잡도를 가진다.

정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이
정답 확률을 높일 수 있다.

 

(3) 퀵 정렬

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

퀵 정렬은 가장 많이 사용되는 알고리즘이다.

퀵 정렬에서는 피벗(Pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고
표현한다.

리스트에서 첫 번째 데이터를 피벗으로 정한다.

피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다.

퀵 정렬이 끝나는 조건 : 현재 리스트의 데이터 개수가 1개인 경우이다. 리스트의 원소가 1개라면, 이미 정렬이 되어
있다고 간주할 수 있으며 분할이 불가능하다.

분할(Divide) or 파티션(Partition)

: 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업

직관적인 형태의 퀵 정렬 소스코드

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        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: # 엇갈렸다면 작은 right -= 1 데이터와 피벗 교체
            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)

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

파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드

피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간 면에서는 조금 비효율적이다.

직관적이고 기억하기 쉽다.

array = [5, 7, 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))

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

 

퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도 : O(NlogN)

ex) 퀵 정렬에서 최선의 경우

피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할

데이터 개수 : N개, 높이 : logN

분할이 이루어지는 횟수가 기하급수적으로 감소하게 된다.

(log의 의미는 밑이 2인 로그)

N = 1000일 때, log(2)N ~ 10은 상대적으로 매우 작은 수이다.

데이터의 개수가 많을수록 차이는 매우 극명하게 드러난다.

데이터의 개수가 많을수록 퀵 정렬은 선택, 삽입 정렬에 비해 압도적으로 빠르게 동작하리라 추측할 수 있다.

표는 '평균 시간 복잡도'를 기준으로 각 정렬 알고리즘이 데이터의 개수에 따라 얼마나 많은 연산을 요구하는지를
보여주기 위해 작성되었다.

데이터의 개수(N)	N^2(선택 정렬, 삽입 정렬)	NlogN(퀵 정렬)
N = 1000	~ 1,000,000	~ 10,000
N = 1,000,000	~ 1,000,000,000,000	~ 20,000,000

퀵 정렬의 시간 복잡도에 대하여 한 가지 기억할 점

평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 시간 복잡도가 O(N^2)이다.

데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다.

퀵 정렬처럼 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다.

• 삽입 정렬은 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작한다.
• 퀵 정렬은 데이터가 무작위로 입력되어 있는 경우 매우 빠르게 동작한다.

파이썬에서 퀵 정렬 이용시, 기본 정렬 라이브러리를 이용하면 O(NlogN)을 보장해준다.

 

(4) 계수 정렬

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

최악의 경우, 수행 시간 O(N + K)

계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.

일반적으로 가장 큰 데이터와 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

계수 정렬을 이용할 때는 '모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언'해야 한다.

비교 기반의 정렬 알고리즘 : 선택, 삽입, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 정렬 방법
(계수 정렬은 해당하지 않는다.)

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

EX) 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

데이터의 범위 : 0부터 9까지이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 한다.

1) 처음에는 리스트의 모든 데이터가 0이 되도록 초기화 한다.
2) 그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

결과적으로 최종 정렬된 결과인 '0 0 1 1 2 2 3 4 5 5 6 7 8 9 9'가 출력된다.

# 모든 원소의 값이 0보다 크거나 같다고 지정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

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

 

계수 정렬의 시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는
O(N + K)이다.

데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.

현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다.

계수 정렬의 공간 복잡도

계수 정렬 알고리즘은 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.

반면, 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을
이용하는 것이 유리하다.

계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다.

코딩테스트 시스템 환경, 정렬 문제에서는 데이터 개수가 1,000만 개 미만으로 출제된다. 상황에 맞추어 계수 정렬 알고리즘을 사용한다.

계수 정렬의 공간 복잡도는 O(N+K)이다.

 

파이썬의 정렬 라이브러리

정렬 알고리즘 문제는 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제라고 할 수 있다.

(1) sorted

• 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다.
• 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.
• 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.
• 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.

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]

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]

sorted()나 sort()를 이용할 때에는 key 매개변수를 입력 받을 수 있다.

key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

ex) 리스트의 데이터가 튜플로 구성되어 있을 때, 각 데이터의 두 번째 원소를 기준으로 설정

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

def setting(data):
    return data[1]

result = sorted(array, key=setting)
print(result)

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

 

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

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.

문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 알고리즘을 사용하고,
데이터 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용한다.

코딩 테스트에서 정렬 알고리즘이 사용되는 경우

1) 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2) 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3) 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

문제 6-2 위에서 아래로

수의 개수가 500개 이하로 매우 적으며, 모든 수는 1 이상 100,000 이하이므로 어떠한 정렬 알고리즘을 사용해도 문제를 해결할 수 있다.
소스

# N을 입력받기
n = int(input())

# N개의 정수를 입력받아 리스트에 저장
array = []
for i in range(n):
	array.append(int(input()))
	
# 파이썬 기본 정렬 라이브러리를 이용하여 정렬 수행
array = sorted(array, reverse=True)

# 정렬이 수행된 결과를 출력
for i in array:
	print(i, end=' ')

 

문제 6-3 성적이 낮은 순서로 학생 출력하기

이 문제에서는 학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다.
학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행해야 한다.
소스

# N을 입력받기

# N명의 학생 정보를 입력받아 리스트에 저장
array = []
for i in range(n):
	input_data = input().split()
	# 이름은 문자열 그래도, 점수는 정수형으로 변환하여 저장
	array.append((input_data[0], int(input_data[1])))
	
# 키(Key)를 이용하여, 점수를 기준으로 정렬
array = sorted(array, key=lambda student: student[1])

# 정렬이 수행된 결과를 출력
for student in array:
	print(student[0], end=' ')

 

문제 6-4 두 배열의 원소 교체

배열 A의 모든 원소들의 합의 최대값을 출력
두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬 알고리즘 이용한다.

# 두 배열의 원소 교체
n, k = map(int, input().split()) # N과 K를 입력받기

list_data1 = list(map(int, input().split()))    # 배열 A의 모든 원소를 입력받기
list_data2 = list(map(int, input().split()))    # 배열 B의 모든 원소를 입력받기

list_data1 = sorted(list_data1) # 배열 A는 오름차순 정렬 수행
list_data2 = sorted(list_data2, reverse=True)   # 배열 B는 내림차순 정렬 수행

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
    # A의 원소가 B의 원소보다 작은 경우
    if list_data1[i] < list_data2[i]:
        # 두 원소를 교체
        list_data1[i] = list_data2[i]
    else:   # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
        break

# 배열 A의 모든 원소의 합을 출력
print(sum(list_data1))

 

---

참고 자료

• 이것이 코딩 테스트다.