- 버블 정렬, 합병 정렬, 파이썬 내장 정렬함수에 대해 정리했다
- 파이썬을 사용한다.
🐥정렬 알고리즘
정렬 알고리즘은 두 가지 시간 복잡도로 분류할 수 있다.
| Insertion sort | Quick sort |
| Selection sort | Merge sort |
| Bubble sort | Heap sort |
시간 복잡도
시간 복잡도란 문제를 푸는데 걸리는 시간을 입력 n의 함수 관계를 사용하여 나타낸 것이다.
알고리즘의 시간복잡도는 주로 Big-O 표기법을 사용하는데, 이는 계수를 모두 없앤 뒤 최대 차항만을 표기하는 방법이다.
예를 들어, 어떤 문제를 푸는데 최대 번의 연산이 필요하다면 계수를 모두 없앤 식은 이 된다.
이 상태에서 최대 차항은 이므로, 결과적으로 시간 복잡도는 로 표기된다.
💧버블 정렬
버블 정렬은 가장 간단한 정렬 방법이다.
- 인접한 두 원소를 비교한다.
- [왼쪽 원소] > [오른쪽 원소] 라면 swap! 한다.
- 가장 큰 원소부터 오른쪽에 정렬된다.
- 데이터가 하나씩 정렬되면서 비교에서 제외된다.
📝 문제
🤝합병 정렬
합병 정렬은 분할 정복(Divide and Conquer) 방식으로 설계된 알고리즘이다.
분할 정복 알고리즘은 주로 재귀 함수로 구현되며 다음의 3단계로 이루어진다.
- Divide : 문제 분할
- Conquer : 쪼개진 작은 문제 해결
- Combine : 해결된 작은 문제들을 다시 합침
📝 문제
🥧파이썬 정렬함수
하지만 정렬할 일은 많고, 매번 정렬함수를 구현하기는 어렵다.
파이썬에 내장된 정렬함수를 사용하면 편리하게 구현할 수 있다.
list.sort()
- 리스트의 메소드로, 리스트의 원본을 정렬된 형태로 바꾸어 놓으며 None을 반환한다.
- 디폴트 값은 오름차순 정렬이지만, key 값에 함수(람다함수)를 보내면 원하는 조건대로 정렬이 가능하다.
ex) 내림차순 정렬 : reverse에 true를 보내줌
sorted()
- 정렬된 리스트를 반환하는 함수입니다. 인자로 iterable 객체를 받는다.
- 역시 key 값을 통해 원하는 조건으로 정렬이 가능하다.
- 예시 코드
sorted(student_objects, key=attrgetter('age'), reverse=True) [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
📝 문제
📚 과제
백준 10804 : 카드 역배치 - Bronze 2
백준 12840 : 창용이의 시계 - Bronze 3
백준 11651 : 좌표 정렬하기2 - Silver 2
백준 1758 : 알바생 강호 - Silver 4
백준 1431 : 시리얼 번호 - Silver 3
백준 1946 : 신입 사원 - Silver 1
백준 1026 : 보물 - Silver 4
