📍 정렬

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
정렬 알고리즘은 이진 탐색의 전처리 과정이기도 함

선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

참고) 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공함
       내림차순 정렬은 오름차순 정렬을 수행한 뒤 그 결과를 뒤집기하여 만들 수 있음

---

🔎 선택 정렬

매번 '가장 작은 것을 선택'한다는 의미의 선택 정렬 알고리즘
데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 가장 원시적인 방법

가장 작은 데이터를 앞으로 보내는 과정을 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)

참고) 스와프란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업
파이썬에서는 아래와 같이 간단히 리스트 내 두 원소의 위치 변경 가능

array = [3, 5]
array[0], array[1] = array[1], array[0]

# 결과
# [5, 3]

선택 정렬의 시간 복잡도

N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하며 매번 가장 작은 수를 찾기 위해 비교 연산이 필요
≈ N + (N - 1) + (N - 2) + ··· + 2 = N x (N + 1) / 2번의 연산을 수행한다고 가정
즉 (N² + N) / 2로 표현할 수 있고 빅오 표기법으로 O(N²)이라고 표현할 수 있음

선택 정렬의 시간 복잡도 = O(N²)

기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적임
다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에선 잦기 때문에 선택 정렬 소스코드 형태에 익숙해지자

---

🔎 삽입 정렬

특정한 데이터를 적절한 위치에 '삽입'한다는 의미의 삽입 정렬 알고리즘
데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입함
특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정함

# 삽입 정렬 소스코드
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)

삽입 정렬 동작 예시

[4]   [6]   [8]   [1]   [2]   [7]   [3]   [5]
1. 첫 번째 데이터 '4'은 그 자체로 정렬되어 있다고 판단함
2. 두 번째 데이터인 '6'이 어떤 위치로 들어갈지 판단함
  '4'의 왼쪽 혹은 오른쪽으로 들어가는 두 경우만 존재함
  => 원래 자리 그대로 둠 ('4'의 오른쪽에 삽입)

[4]   [6]   [8]   [1]   [2]   [7]   [3]   [5]
'8'이 어떤 위치에 들어갈지 판단함
  삽입될 수 있는 위치는 총 3가지 ('4'의 왼쪽, '4'와 '6' 사이, '6'의 오른쪽)
  => '8'은 '4'와 '6'보다 크기 때문에 원래 자리 그대로 둠

[4]   [6]   [8]   [1]   [2]   [7]   [3]   [5]
'1'이 어떤 위치에 들어갈지 판단함
  => '4', '6', '8'과 비교했을 때 가장 작기 때문에 첫 번째 위치에 삽입

[1]   [4]   [6]   [8]   [2]   [7]   [3]   [5]
'2'가 어떤 위치에 들어갈지 판단함
  => '1'과 '4' 사이에 삽입함

[1]   [2]   [4]   [6]   [8]   [7]   [3]   [5]
'7'이 어떤 위치에 들어갈지 판단함
  => '6'과 '8' 사이에 삽입함

[1]   [2]   [4]   [6]   [7]   [8]   [3]   [5]
'3'이 어떤 위치에 들어갈지 판단함
  => '2'와 '4' 사이에 삽입함

[1]   [2]   [3]   [4]   [6]   [7]   [8]   [5]
'5'가 어떤 위치에 들어갈지 판단함
  => '4'와 '6' 사이에 삽입함

[1]   [2]   [3]   [4]   [5]   [6]   [7]   [8]  
이와 같이 적절한 위치에 삽입하는 과정을 N - 1번 반복하게 되면 이와 같이 모든 데이터가 정렬된 것을 확인할 수 있음

정렬이 이루어진 원소는 항상 오름차순을 유지하고 있음
(하늘색으로 칠해진 카드들은 어떤 단계든지 항상 정렬된 상태임)
  => 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 되는 것!

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도 = O(N²), 선택 정렬과 흡사한 시간이 소요됨
But, 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작함!

최선의 경우 O(N)의 시간 복잡도

거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 삽입 정렬을 이용하는 것이 정답 확률 높일 수 있음

---

🔎 퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정함

# 파이썬의 장점을 살린 퀵 정렬 소스코드
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))

퀵 정렬 동작 예시

[4]   [6]   [8]   [1]   [2]   [7]   [3]   [5]
1. 현재 피벗의 값은 '4', 왼쪽에서부터 '4'보다 큰 데이터를 선택 = '6', 오른쪽에서부터 '4'보다 작은 데이터를 선택 = '3'
  => 두 데이터의 위치를 서로 변경

[4]   [3]   [8]   [1]   [2]   [7]   [6]   [5]
2. 현재 피벗의 값은 '4', 왼쪽에서부터 '4'보다 큰 데이터를 선택 = '8', 오른쪽에서부터 '4'보다 작은 데이터를 선택 = '2'
  => 두 데이터의 위치를 서로 변경

[4]   [3]   [2]   [1]   [8]   [7]   [6]   [5]
3. 현재 피벗의 값은 '4', 왼쪽에서부터 '4'보다 큰 데이터를 선택 = '8', 오른쪽에서부터 '4'보다 작은 데이터를 선택 = '1'
  => 단, 이처럼 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 서로 변경

[1]   [3]   [2]   [4]   [8]   [7]   [6]   [5]
[분할 완료] '4'의 왼쪽에 있는 데이터는 모두 4보다 작고, 오른쪽에 있는 데이터는 모두 4보다 큼
이와 같이 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide) 혹은 파티션(Partition)이라 함

[1]   [3]   [2]   [  ]   [  ]   [  ]   [  ]   [  ]  
[왼쪽 데이터 묶음 정렬] 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬 수행

[  ]   [  ]   [  ]   [  ]   [8]   [7]   [6]   [5]
[오른쪽 데이터 묶음 정렬] 오른쪽에 있는 데이터에 대해서 마찬가지로 정렬 수행

이러한 과정을 반복하면 전체 데이터에 대해서 정렬이 수행됨
(부분 리스트들이 더 이상 분할이 불가능할 때까지 반복함)

퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도 = O(NlogN)
평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 O(N²)

데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높음
이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작함

기본 정렬 라이브러리를 이용하면 최악의 경우에도 시간 복잡도가 O(NlogN)이 되는 것을 보장해주기에 걱정 X

---

🔎 계수 정렬

계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
'데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능

1. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성함
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴
   => 결과적으로 최종 리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록됨
   결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력

# 계수 정렬 소스코드

# 모든 원소의 값이 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

계수 정렬 동작 예시

[4]   [6]   [4]   [8]   [1]   [2]   [7]   [1]

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

초기상태, 가장 큰 데이터는 '8', 가장 작은 데이터는 '1'
가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성
리스트의 모든 데이터가 0이 되도록 초기화함

데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 됨
[4]   [6]   [4]   [8]   [1]   [2]   [7]   [1]

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

[4]   [6]   [4]   [8]   [1]   [2]   [7]   [1]

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

[4]   [6]   [4]   [8]   [1]   [2]   [7]   [1]

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

...

[4]   [6]   [4]   [8]   [1]   [2]   [7]   [1]

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

결과적으로 위 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록됨
정렬된 결과를 직접 눈으로 확인하고 싶다면, 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 됨
ex) 출력 결과: 1 1 2 4 4 6 7 8

계수 정렬의 시간 복잡도

데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K) 를 보장함
시간 복잡도와 공간 복잡도 모두 O(N + K)

동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있음

---

📍 정렬 알고리즘 비교

참고) 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있음

---

📍 파이썬의 정렬 라이브러리

기본 정렬 라이브러리인 sorted() 함수를 제공함
퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 함, 최악의 경우에도 시간 복잡도 O(NlogN)을 보장함

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있음
리스트 객체의 내장 함수인 sort()를 이용하는 것

sorted()나 sort()를 이용할 때엔 key 매개변수를 입력으로 받을 수 있음
key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 됨

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

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

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

---

✏️ 실전 문제

📝 위에서 아래로

하나의 수열에는 다양한 수가 존재함, 이러한 수는 크기에 상관없이 나열되어 있음
이 수를 큰 수부터 작은 수의 순서로 정렬해야 함

수열을 내림차순으로 정렬하는 프로그램을 만드시오

• 입력 조건
  - 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어짐 (1 ≤ N ≤ 500)
  - 둘째 줄부터 N + 1번째 줄까지 N개의 수가 입력됨, 수의 범위는 1 이상 100,000 이하의 자연수
• 출력 조건
  - 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력함, 동일한 수의 순서는 자유롭게 출력해도 괜찮음
  

문제 해설

가장 기본적인 정렬을 할 수 있는지 물어보는 문제
수의 개수가 500개 이하로 매우 적으며, 모든 수는 1 이상 100,000 이하이므로 어떠한 정렬 알고리즘을 사용해도 문제를 해결할 수 있음

가장 코드가 간결해지는 파이썬의 기본 정렬 라이브러리를 이용하는 것이 효과적

소스코드

---

📝 성적이 낮은 순서로 학생 출력하기

N명의 학생 정보가 있음, 학생 정보는 학생의 이름과 학생의 성적으로 구분됨

각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오

• 입력 조건
  - 첫 번째 줄에 학생의 수 N이 입력됨 (1 ≤ N ≤ 100,000)
  - 두 번째 줄부터 N + 1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력됨, 문자열 A의 길이와 학생의 성적은 100 이하의 자연수
• 출력 조건
  - 모든 학생의 이름을 성적이 낮은 순서대로 출력함, 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮음
  

문제 해설

학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 됨

입력되는 데이터는 학생의 이름과 점수지만, 출력할 때는 학생의 이름만 출력하면 되므로 학생 정보를 (점수, 이름)으로 묶은 뒤 점수를 기준으로 정렬을 수행해야 함

따라서 이런 경우에도 마찬가지로 파이썬의 기본 정렬 라이브러리를 사용하는 것이 효과적

소스코드

---

📝 두 배열의 원소 교체

수빈이는 두 개의 배열 A와 B를 가지고 있음
두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수임
수빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라 두 원소를 서로 바꾸는 것을 말함
수빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 우리는 수빈이를 도와야 함

N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오

• 입력 조건
  - 첫 번째 줄에 N, K가 공백으로 구분되어 입력됨 (1 ≤ N ≤ 100,000, 0 ≤ K ≤ N)
  - 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력됨, 모든 원소는 10,000,000보다 작은 자연수
  - 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력됨, 모든 원소는 10,000,000보다 작은 자연수
• 출력 조건
  - 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력함
  

문제 해설

문제 해결을 위한 기본 아이디어는 매번 배열 A에서 가장 작은 원소를 골라, 배열 B에서 가장 큰 원소와 교체하는 것
단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체를 수행해야 함
이러한 과정을 K번 반복하면 원하는 정답을 얻을 수 있음

배열 A의 원소를 오름차순으로, 배열 B의 원소를 내림차순으로 정렬함
두 배열의 원소를 가장 첫 번째 인덱스부터 차례대로 비교하며 A의 원소가 B의 원소보다 작을 때에만 교체를 수행함

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

소스코드

---

📒 이것이 코딩 테스트다 교재를 통해 학습한 내용을 정리하였습니다.