[Python] 파이썬 정렬하기
파이썬 정렬하기
파이썬에서 정렬하는 방법에 대해 살펴봅니다.
기본 정렬
기본 정렬에는 삽입 정렬, 선택 정렬, 버블 정렬 등이 있습니다.
위 3가지의 정렬 알고리즘은 모두 O(n2) 의 시간 복잡도를 가집니다.
삽입 정렬
- 설명
정렬하고자 하는 리스트는 unsorted list와 sorted list로 나눠집니다. unsorted list의 맨 앞에 있는 숫자를 sorted list의 적절한 위치에 삽입해가면서 sorted list의 길이를 늘려가는 방식입니다.
- 예시
- 코드
def insertionSort(x):
for size in range(1, len(x)):
val = x[size]
i = size
while i > 0 and x[i-1] > val:
x[i] = x[i-1]
i -= 1
x[i] = val
return x
선택 정렬
- 설명
정렬하고자 하는 리스트는 unsorted list와 sorted list로 나눠집니다. unsorted list의 최솟값과 unsorted list의 맨 앞 원소를 교체하여 sorted list의 길이를 늘려가는 방식입니다.
- 예시
- 코드
def selectionSort(x):
for size in (range(len(x)):
min_i = size
for i in range(size+1,len(x)):
if x[i] < x[min_i]:
min_i = i
x[size], x[min_i] = x[min_i], x[size]
return x
버블 정렬
- 설명
정렬하고자 하는 리스트는 unsorted list와 sorted list로 나눠집니다. unsorted list의 맨 뒤에서 앞으로 이동하며 이웃한 두 값을 비교하면서 현재 값이 더 작다면 다음 값과 교체하는 방식으로 sorted list 의 길이를 늘려갑니다.
- 예시
- 코드
def bubbleSort(x):
for size in reversed(range(len(x))):
for i in range(size):
if x[i] > x[i+1]:
x[i],x[i+1] = x[i+1],x[i]
return x
고급 정렬
고급 정렬에는 병합 정렬, 퀵 정렬, 힙 정렬 등이 있다.
고급 정렬은 기본 정렬보다 구현하기 복잡하지만, O(nlogn)의 시간 복잡도를 보여준다.
파이썬의 heapq 모듈을 이용하여 힙 정렬을 간단히 구현할 수 있으므로 여기서는 힙 정렬을 구현하는 방법만 살펴보겠다.
힙 정렬
- 설명
정렬하고자 하는 리스트를 먼저 (최소) 힙 구조로 만들고, 힙의 root element부터 차례로 pop한다.
- 코드
def heapSort(x):
from heapq import heapify, heappop
heapify(x)
while x:
x.append(heappop(x))
return x
파이썬 내장 정렬 함수
파이썬은 기본적으로 내장된 정렬 함수를 제공합니다.
이 함수는 O(nlogn)의 시간 복잡도를 보이기 때문에, 파이썬에서 정렬이 필요할 때는 정렬 함수를 따로 구현하지 않고 내장 정렬 함수를 사용하면 됩니다.
sort( ) 메서드와 sorted( ) 함수
파이썬에서 정렬을 수행할 수 있는 방법에는 sort( ) 메서드와 sorted( ) 함수를 사용하는 방법이 있습니다.
- sort( ): 리스트의 메서드로, 메서드를 호출한 리스트를 직접적으로 정렬하며 반환 값은 None이다.
x = [3,2,4,1]
y = x.sort()
print(x)
print(y)
out:
[1,2,3,4]
None
- sorted( ): 파이썬의 내장 함수로, 원본 리스트에 직접 정렬을 하지는 않으며 반환값으로 정렬된 리스트를 반환한다.
x = [3,2,4,1]
y = sorted(x)
print(x)
print(y)
out:
[3,2,4,1]
[1,2,3,4]
key: 정렬 기준 지정
sort 메서드든 sorted 함수든, 정렬 기준을 key 파라미터로 간단히 지정할 수 있습니다.
in:
sorted("This is a test string from Andrew".split(), key=str.lower)
out:
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
in:
student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
sorted(student_tuples, key=lambda student: student[2])
out:
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
reverse: 내림차순 정렬
sort 메서드든 sorted 함수든, 기본적으로 오름차순 정렬을 수행합니다. 파라미터로 reverse=True를 지정하면 내림차순으로 정렬할 수 있습니다.
in:
sorted(student_tuples, key=lambda student: student[2], reverse=True)
out:
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
카운팅 정렬
비교 연산을 수행하지 않는 정렬 방법입니다.
이 카운팅 정렬 알고리즘은 정렬할 숫자의 범위가 작을 때 그 효과가 배가됩니다.
예를 들어 1~1,000,000 까지의 숫자들이 있는 리스트를 정렬할 때에는 O(nlogn)의 시간 복잡도를 가지는 정렬 알고리즘을 이용하는 것이 좋지만, 1~10000 까지인 경우 카운팅 정렬이 좋은 선택이 될 수 있습니다.
이에 대한 예제는 아래 백준 문제에서 확인할 수 있습니다.
코드
def countingSort(x):
UPPER_LIMIT = max(x)
cnts = [0 for _ in range(UPPER_LIMIT+1)]
sorted_x = []
for num in range(len(cnts)):
for cnt in range(cnts[num]):
sorted_x.append(num)
return sorted_x
Leave a comment