Python [AtoZ] Chapter 06. 정렬

[ Table of Contents ]

기준에 따라 데이터를 정렬

1. 정렬 알고리즘 개요

2. 선택 정렬

3. 삽입 정렬

4. 퀵 정렬

5. 계수 정렬

6. 파이썬의 정렬 라이브러리

 

실전 문제

1. 위에서 아래로

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

3. 두 배열의 원소 교체

 

기출 문제

1. 국영수

2. 안테나

3. 실패율

4. 카드 정렬하기

[ Abstract ]

0. 계산 복잡도 : P-NP문제

1. DP란? 퀵정렬과는 다르며, 재귀 함수 말고 반복문으로 구현할 것

2. 탑다운(=메모이제이션) : 연속적이지 않은 경우 사전dict 자료형 사용 가능

3. 보텀업(=DP의 전형적인 형태) : DP테이블 사용

4. 피보나치 수열의 시간복잡도 : 재귀(O(2ᴺ)), DP(O(N))

 

기준에 따라 데이터를 정렬

1. 정렬 알고리즘 개요

정렬Sorting이란 데이터를 특정한 기준에 다라서 순서대로 나열하는 것으로, 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색Binary Search이 가능해진다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 이 책에서 언급하려 한다. 더불어 파이썬에서 제공하는 기본 정렬 라이브러리를 적용하여 좀 더 효과적인 정렬 수행 방법도 다루려 한다.

보통 정렬부터 공부하면 알고리즘의 효율성을 쉽게 이해할 수 있어 알고리즘 개론서 초반에 정렬 알고리즘을 설명하는 경우가 많다. 또한 일반적으로 문제에서 요구하는 조건에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 상황에 적절하지 못한 정렬 알고리즘을 이용하면 당연히 프로그램은 비효율적으로 동작하며 필요 이상으로 시간을 많이 소요한다. 그래서 정렬 알고리즘을 공부하다 보면 자연스럽게 알고리즘 효율의 중요성을 깨닫는다.

이 장에서 다루는 예제는 모두 오름차순 정렬을 수행한다고 가정한다. 내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 된다. 또한 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공한다. 그래서 내림차순 정렬은 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기Reverse하여 내림차순 리스트를 만들 수 있으며, 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있다.

 

2. 선택 정렬

선택 정렬Selection Sort은 데이터가 무작위로 여러 개 있을 때, 이중에서 매번 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 가장 원시적인 방법이다. 이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 (N-1)번 반복하면 정렬이 완료되는 것을 알 수 있다.

#선택정렬
arr = [7,5,9,0,3,1,6,2,4,8]
for i in range(len(arr)):
    min_index = i #가장 작은 원소의 인덱스
    for j in range(i+1, len(arr)):
        if arr[min_index] > arr[j]:
            min_index = j
            #print(f"(idx, arr) : {i,arr[i]} <-> {j,arr[j]}") # <--- 선택정렬을 이해하기 위한 코드로 실제로는 불필요
    arr[i], arr[min_index] = arr[min_index], arr[i] #스와프
print(arr) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

스와프Swap란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미한다. 파이썬에서는 다음처럼 간단히 리스트 내 두원소의 위치를 변경할 수 있다. 하지만 다른 대부분의 프로그래밍 언어에서는 명시적으로 임시 저장용 변수를 만들어 두 원소의 값을 변경해야 한다.

#스와프
arr = [3, 5]
arr[0], arr[1] = arr[1], arr[0]
print(arr) #[5, 3]

 

 

선택 정렬의 시간 복잡도

선택 정렬은 (N-1)번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있으며, 근사치로 N(N+1)/2번의 연산을 수행한다고 가정했을 때, 간단히 O(N²)이라고 표현할 수 있다. 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이라고 이해할 수 있다.

아래는 데이터의 개수에 따른 수행 시간을 비교한 결과이다. 측정 시간은 컴퓨터의 성능에 따라 다를 수 있으며, 파이썬의 기본 정렬 라이브러리는 내부적으로 C언어 기반이며, 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다.

데이터의 개수(N)	선택 정렬	퀵 정렬	기본 정렬 라이브러리
N = 100	0.0123초	0.00156초	0.00000753초
N = 1,000	0.354초	0.00343초	0.0000365초
N = 10,000	15.475초	0.0312초	0.000248초

 

 

3. 삽입 정렬

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이므로, 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 방식으로 접근해보자.

삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘으로, 선택 정렬에 비해 구현 난이도가 높은 편이지만 실행 시간 측면에서 효율적이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로, 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬Insertion Sort이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정하며, 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다. 따라서 두 번째 데이터가 첫 번째의 왼쪽 혹은 오른쪽으로 들어가는 두 경우만 존재한다.

삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다. 이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때(삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

#삽입정렬
arr = [7,5,9,0,3,1,6,2,4,8]
for i in range(1, len(arr)): #첫번째(i=0)는 정렬되어 있다고 가정
    for j in range(i, 0, -1): #두번째(j=i=1)부터 왼쪽(-1)으로 이동
        if arr[j] < arr[j-1]:
            #print(arr[:j+1],arr[j-1],'<->',arr[j]) # <--- 삽입정렬을 이해하기 위한 코드
            arr[j], arr[j-1] = arr[j-1], arr[j]
            #print(arr[:j+1]) # <--- 삽입정렬을 이해하기 위한 코드
        else:
            break
print(arr) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N²)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 단, 리스트의 데이터가 거의 정렬되어 있는 최선의 상태라면 O(N)의 시간 복잡도를 가진다. 보통은 삽입 정렬이 아래에서 배울 퀵 정렬보다 비효율적이나, 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다.

 

 

4. 퀵 정렬

퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 이 책에서 다루지는 않지만 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 병합 정렬이 있다. 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다.

퀵 정렬Quick Sort은 기준 데이터를 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 원리를 이해하면 병합 정렬, 힙 정렬 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할 수 있다.

퀵 정렬에서는 피벗Pivot이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 책에서는 가장 대표적인 분할 방식인 호어 분할Hoare Partition 방식을 기준으로 설명하겠다. (호어 분할 : 리스트에서 첫 번째 데이터를 피벗으로 설정)

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

 

 

퀵 정렬은 전체를 3개의 파트로 나눠서 보는게 편한다.

파트1

1) 리스트의 첫 번째 데이터를 피벗으로 설정

2) 왼쪽(두 번째)에서부터 피벗보다 큰 데이터와 오른쪽(마지막)에서부터 피벗보다 작은 데이터를 선택하여 위치를 스와프한다.

3) 그 다음 번째(세 번째와 마지막-1번째)에서 피벗보다 큰 데이터와 작은 데이터를 찾아 위치를 교환한다.

4) 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈렸을 때, 작은 데이터와 피벗의 위치를 교환한다.

5) 이제 피벗을 기준으로 왼쪽에 있는 데이터는 모두 피벗보다 작고, 오른쪽에 있는 데이터는 피벗보다 크다는 특징이 있다. 이러한 작업을 분할Divide 혹은 파티션Partition이라고 한다. 이러한 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬시키면, 전체 리스트에 대하여 모두 정렬이 이루어질 것이다.

 

파트2

1)

2)

 

파트3

1)

2)

 

 

ㅇ

ㅇ

5. 계수 정렬

ㅇ

ㅇ

6. 파이썬의 정렬 라이브러리

ㅇ

ㅇ

실전 문제

1. 위에서 아래로

[난이도: 하 / 풀이시간: 20분 / 시간제한: 1초 / 메모리제한: 128MB]

[입력 조건]

[출력 조건]

 

문제 해설

ㅇ

ㅇ

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

[난이도: 하 / 풀이시간: 20분 / 시간제한: 1초 / 메모리제한: 128MB]

[입력 조건]

[출력 조건]

 

문제 해설

ㅇ

ㅇ

3. 두 배열의 원소 교체

[난이도: 하 / 풀이시간: 20분 / 시간제한: 1초 / 메모리제한: 128MB]

[입력 조건]

[출력 조건]

 

문제 해설

ㅇ

ㅇ

기출 문제

1. 국영수

2. 안테나

3. 실패율

4. 카드 정렬하기

 

 

이 글은 주인장의 자습 목적을 위해 <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 99.99% 참고하여 만들었다.