Search

정렬 알고리즘

선택 정렬 (Selection Sort)

무작위의 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬 → 매번 가장 작은 것을 선택
오름차순 선택 정렬 코드

스와프(Swap)?

특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업
파이썬의 스와프 소스 코드

시간 복잡도 : O(N²)

선택 정렬은 알고리즘 문제 풀이에 사용하기엔 느린 편

삽입 정렬 (Insertion Sort)

모든 원소를 비교하고 위치를 바꾸는 게 아니라, 필요할 때만 위치를 바꾸는 정렬 → 특정한 데이터를 적절한 위치에 삽입 → 데이터가 거의 정렬되어 있을 때 훨씬 효율적
삽입 정렬에 비해 구현 난이도는 더 높지만, 실행 시간 측면에서는 더 효율적
삽입 정렬은 두 번째 데이터부터 시작
→ 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단
정렬이 이루어진 원소는 항상 오름차순을 유지
삽입 정렬 코드

시간 복잡도 : O(N)

퀵 정렬 (Quick Sort)

모든 원소를 비교하고 위치를 바꾸는 게 아니라, 필요할 때만 위치를 바꾸는 정렬 → 특정한 데이터를 적절한 위치에 삽입 → 데이터가 거의 정렬되어 있을 때 훨씬 효율적
가장 많이 사용되는 알고리즘
피벗(큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준)을 사용
피벗 설정 후 다음 큰수와 작은 수를 교환한 후, 리스트를 반으로 나누는 방식으로 동작

호어 분할 (Hoare Partition)

가장 대표적인 퀵 정렬의 분할 방식
리스트에서 첫 번째 데이터를 피벗으로 결정
왼쪽에서부터 피벗보다 큰 데이터를 탐색, 오른쪽에서부터는 더 작은 데이터를 탐색
탐색 후 큰 데이터와 작은 데이터의 위치를 서로 교환
왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값 위치가 서로 엇갈라면, 작은 데이터와 피벗의 위치를 서로 교환 → 분할 완료
분할 후 각각의 영역에서 다시 퀵 정렬 수행 → 재귀 함수와 유사
퀵 정렬 코드
파이썬의 장점을 살린 퀵 정렬 코드

시간 복잡도 : O(NlogN)

최악의 경우 시간 복잡도는 O(N²)
이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작

계수 정렬 (Count Sort)

모든 원소를 비교하고 위치를 바꾸는 게 아니라, 필요할 때만 위치를 바꾸는 정렬 → 특정한 데이터를 적절한 위치에 삽입 → 데이터가 거의 정렬되어 있을 때 훨씬 효율적
특정한 조건이 부합할 때만 사용 가능하지만 매우 빠른 정렬 알고리즘
데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때가 효과적
모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문
계수 정렬 코드

시간 복잡도 : 최악의 경우에도 O(N+K)

데이터의 개수 N, 데이터 중 최대값 K
이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작
데이터의 크기가 한정되어 있고, 만힝 중복되어 있을수록 유리, 항상 사용은 불가

파이썬의 정렬 라이브러리

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]
Python
sort() : 리스트 객체의 내장 함수
리스트 변수가 하나 있을 때 내부 원소를 바로 정렬 가능
별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬됨
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]
Python
key : sorted(), sort() 이용할 때 입력받을 수 있는 매개 변수
key 값으로 하나의 함수가 들어가야 하며 정렬 기준이 됨.
# 튜플로 구성되어 있는 리스트 array = [('바나나', 2), ('사과'), 5), ('당근', 3)] def setting(data): return data[1] result = sorted(array, key=setting) print(result) # [('바나나', 2), ('사과'), 3), ('당근', 5)]
Python

정렬 라이브러리의 시간 복잡도 : O(NlogN)

1.
정렬 라이브러리로 풀 수 있는 문제
단순 정렬 기법을 알고 있는지, 라이브러리 사용법 숙지 필요
2.
정렬 알고리즘의 원리에 대해 물어보는 문제
선택, 삽입, 퀵 정렬 등의 원리 숙지 필요
3.
더 빠른 정렬이 필요한 문제
퀵 기반으로는 불가, 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 기존에 알려진 알고리즘의 구조적인 개선 필요

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.