정렬이란?
말 그대로 데이터를 특정한 기준에 따라서 순서대로 나열하는 것!
정렬의 종류
문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.
1. 선택 정렬
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택, 맨 앞에 있는 데이터와 바꾸는 작업을 반복하여 정렬.
<선택 정렬 동작 예시>
- 정렬할 데이터를 준비한다.
- 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꾼다.
- 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와 바꾼다.
- 처리되지 않은 데이터 중 가장 작은 '2'를 선택해 가장 앞의 '9'와 바꾼다.
- 처리되지 않은 데이터 중 가장 작은 '3'을 선택해 가장 앞의 '7'과 바꾼다.
- 이러한 과정을 반복하면 다음과 같이 정렬이 완료된다.
선택 정렬 소스코드 (Python)
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]선택 정렬의 시간 복잡도
선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다
구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다
𝑁 + (𝑁 - 1) + (𝑁 - 2) + ... + 2
이는 (𝑁² + 𝑁 - 2) / 2 로 표현할 수 있는데, 빅오 표기법에 따라서 O(N²) 이라고 작성한다.
2. 삽입 정렬
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
선택 정렬에 비해 구현 난이도가 더 높고, 일반적으로 더 효율적인 방식이다.
<삽입 정렬 동작 예시>
- 첫번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 전제하고, 두번째 데이터인 '5'가 어떤 위치에 들어가는 것이 적절한지 판단한다. '7'의 왼쪽과 오른쪽 두 경우가 존재하며, 왼쪽이 적절하다고 판단하여 넣는다.
- 이어서 '9'가 어떤 위치로 들어갈지 판단한다.
- 이어서 '0'이 어떤 위치로 들어갈지 판단한다.
- 이어서 '3'이 어떤 위치로 들어갈지 판단한다.
- 이러한 과정을 반복하면 다음과 같이 정렬이 완료된다.
삽입 정렬 소스코드 (Python)
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까지 1씩 감소하며 반복하는 문법
if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j - 1] = array[j - 1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]삽입 정렬의 시간 복잡도
삽입 정렬의 시간 복잡도는 O(N²) 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다
삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다
최선의 경우 O(N) 의 시간 복잡도를 가진다
3. 퀵 정렬
기준키(pivot)를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법. 가장 많이 사용되는 알고리즘. 병합 정렬과 함께 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.
퀵 정렬의 시간 복잡도 : 평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 시간 복잡도는 O(N²)
4. 계수 정렬
각 숫자가 얼마나 들어있는지 세어주고 작은 수부터 각 숫자의 갯수만큼 정렬해주는 방식. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용가능. 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 안됨. '모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언'해야 하기 때문. 그리고 그 리스트에 정렬의 정보를 담아준다.
계수 정렬의 시간 복잡도 : 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 시간 복잡도는 O(N + K)
계수 정렬의 공간 복잡도 : 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리. 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적. 정렬 문제에서의 데이터 개수는 보통 1,000만 개 미만. O(N + K)
[Python] sort()와 sorted()
파이썬 리스트는 sort() 라는 메소드를 가지고 이 메소드는 리스트를 정렬된 상태로 변경한다. 또 sorted() 라는 내장 함수는 이터러블 객체로부터 정렬된 리스트를 생성한다.
파이썬에서 간단하게 정렬을 실행하려면 다음과 같이 sorted()를 호출하면 된다. sorted()는 기존의 리스트를 변경하는 것이 아니라 정렬된 새로운 리스트를 반환한다.
>>> sorted([4, 2, 3, 5, 1])
[1, 2, 3, 4, 5]리스트의 메소드인 sort()를 사용하여도 정렬이 된다. 이 경우에는 리스트 자체를 변경해 버린다. 일반적으로 이것보다는 내장함수인 sorted()가 더 편리하다.
sort()는 리스트만을 위한 메소드이지만 sorted() 함수는 어떤 이터러블 객체도 받을 수 있다. 예를 들어서 다음과 같은 딕셔너리 객체도 받을 수 있다.
>>> sorted({3: 'D', 2: 'B', 5: 'B', 4: 'E', 1: 'A'})
[1, 2, 3, 4, 5]key 매개변수
객체의 데이터 중에서 특정한 데이터를 기준으로 정렬하기 위해 key 매개변수로 정렬을 하기 전에 각 요소에 대하여 적용되는 함수를 지정할 수 있다. 다음의 경우를 살펴보자.
>>> students = [
('홍길동', 3.9, 2016303),
('김철수', 3.0, 2016302),
('최자영', 4.3, 2016301),
]
>>> sorted(students, key=lambda student: student[2])
[('최자영', 4.3, 2016301), ('김철수', 3.0, 2016302), ('홍길동', 3.9, 2016303)]lambda는 람다식을 나타낸 것으로 정렬을 하기 전에 호출되는 함수를 나타낸 것으로 student요소를 받아서 student[2]를 반환한다. 즉 정렬의 기준이 학생들의 학번이 되는 것이다.
오름차순 정렬과 내림차순 정렬
list.sort()와 내장함수 sorted()는 모두 reverse 매개변수를 받는다. reverse 변수는 부울형으로 True 이면 내림차순이 된다. 위의 예제에서 내림차순으로 정렬하려면 다음과 같이 한다.
>>> sorted(students, key=lambda student: student[2], reverse=True)
[('홍길동', 3.9, 2016303), ('김철수', 3.0, 2016302), ('최자영', 4.3, 2016301)]