알고리즘/분할 정복3 퀵 정렬(Quick Sort) in Python 목차 머리말 들어가기 전에 합병 정렬에 이어 분할 정복 알고리즘을 이용한 두 번째 정렬인 퀵 정렬에 대해 알아 보자. 퀵 정렬(Quick Sort) 정의 기준 데이터(피벗, pivot)를 설정하여, 그 기준보다 큰 데이터와 작은 데이터를 구분하는 '분할(partition) 알고리즘'을 재귀적으로(recursively) 반복하여 다시 조합해 나가는 정렬 알고리즘 배열 중에서 임의의 데이터를 '피벗(pivot)'이라 불리는 기준 데이터로 설정한다. 피벗을 기준으로 자기보다 크기가 작은 그룹과 큰 그룹을 최대한 분할한 이후 조합하면서 정렬을 해 나가는 알고리즘이다. 동작 과정 Sorting quicksort animation - Quicksort - Wikipedia 동작 과정 분할 정복 알고리즘에 맞게 세 .. 2023. 4. 4. 합병 정렬(병합 정렬; Merge Sort) in Python 지난 글에 분할 정복 알고리즘의 개념에 대해 알아 보았다. 이제는 실제로 이를 적용한 합병 정렬에 대해 알아 보자. [알고리즘] 분할 정복(Divide and Conquer) 개요 정렬 알고리즘에서 버블 정렬과 선택 정렬, 삽입 정렬에 대해 알아 보았다 이 세 가지 정렬 알고리즘은 코드가 직관적이긴 하지만 $n$(데이터의 크기)에 대한 이중 for 문으로 되어 있기에 굉장히 andy-archive.tistory.com 📌 정의 합병 정렬(merge sort)은 주어진 배열을 더 이상 쪼갤 수 없을 때까지 재귀적으로 데이터 크기의 절반으로 계속 나누고, 다시 정렬을 통합하여 정렬하는 알고리즘이다. 📌 동작 과정 합병 정렬은 요소가 하나가 될 때까지 계속해서 절반으로 나눈 뒤, 조합해 가면서 정렬해 나간다... 2023. 3. 30. 분할 정복 알고리즘(Divide and Conquer Algorithm) 목차 머리말 들어가기 전에 정렬 알고리즘 저번에 포스팅한 정렬 알고리즘에서 버블 정렬과 선택 정렬, 삽입 정렬에 대해 알아 보았다. 효율성 이 세 가지 정렬 알고리즘은 코드가 직관적이긴 하지만 데이터 크기 n에 대한 이중 for 문으로 되어 있기에 굉장히 비효율적이다. 분할 정복 알고리즘 이들의 시간복잡도는 $O(n^2)$이다. 보다 효율적인 정렬 알고리즘을 배우기 위해 분할 정복(Divide and Conquer)에 대해 알아 보자. 배우기 전 알아야 할 개념 재귀 그렇다면 위의 3단계는 어떻게 구현할 수 있을까? 분할과 정복, 통합은 재귀적으로(recursively) 하는 것이다. 따라서 재귀 알고리즘에 대해 먼저 알아야 분할 정복 알고리즘을 제대로 알 수 있다. 분할 정복 알고리즘(Divide an.. 2023. 3. 29. 이전 1 다음 반응형
