시간복잡도 O(NlogN)정렬 알고리즘 알아보기 with Python
이전에 시간 복잡도 O(N^2)인 정렬 알고리즘들에 대해 포스팅했었는데요. 오늘은 시간 복잡도가 O(NlogN)인 정렬 알고리즘에 대해 알아보려 합니다! 시간복잡도가 O(NlogN)인 대표적인 정렬에는 퀵 정렬, 합병 정렬, 힙 정렬이 있습니다. 1. 퀵 정렬 분할 정복(divide and conquer)기법을 사용한 정렬로, 평균적으로 아주 빠른 성능을 갖는 알고리즘입니다. 정렬 방법 1. 주어진 리스트에서 하나의 원소를 고른다. (피벗) 2. 피벗을 기준으로 두 개의 파티션으로 분할한다. 파티션 1: 피벗보다 작은 원소, 파티션 2: 피벗보다 큰 원소 3. 분할된 파티션에 대해서도 리스트의 크기가 0 혹은 1이 될 때까지 1,2 과정을 반복한다. 소스코드(파이썬) def quick_sort(a: li..
기본 정렬 알고리즘 알아보기 with Python
오늘은 기초적인 정렬 알고리즘을 알아보려 합니다. 대표적인 정렬 알고리즘으로는 선택 정렬, 버블 정렬(거품 정렬), 삽입 정렬, 셸 정렬(쉘 정렬), 병합 정렬, 퀵 정렬 등이 있는데요. 간단하게 선택 정렬, 버블 정렬, 삽입 정렬, 쉘 정렬 네 가지 정렬의 정의와 코드를 정리하고 각각의 알고리즘 실행 속도를 측정하여 성능을 비교해 보려 합니다. 1. 선택 정렬 주어진 배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고 두 번째 작은 원소를 찾아 두 번째 원소와 교환하고... 반복하는 정렬 방법 정렬 방법 1. 주어진 배열 중 최솟값을 찾는다. 2. 그 최솟값을 맨 앞의 원소와 교환한다. 3. (N-1)원소에 대해 1-2 방법 반복 소스코드(파이썬) def select_sort(a: list) ->..