욤미의 개발일지

3. 퀵 정렬 기준을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘이다. 책 에서는 다루지 않지만 퀵 정렬만큼 빠른 알고리즘으로 병합 정렬이 있다. 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다. 특징 큰 숫자와 작은 숫자를 교환할때, 교환하기 위한 기준을 피벗(Pivot)이라고 한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분한다. 여기서는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 설명한다. 동작 예시 - 호어 분..

CHAPTER 6. 정렬 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적으로 문제 상황에 따라서 적절한 알고리즘이 공식처럼 사용된다. ex) 데이터의 개수가 적을 때, 데이터 개수가 많더라도 데이터 범위가 한정적일 때, 이미 정렬되어 있는 경우 등... 사람은 직관적으로 데이터를 파악하고 계산할 수 있지만 컴퓨터는 정렬을 어떻게 수행할지 알고리즘을 구체적으로 명시해야한다. 선택정렬 삽입정렬 합병정렬 퀵정렬 계수정렬 Best Avg Worst Stable In-Place 삽입 정렬(Insertion Sort) N N² N² O O 거품 정렬(Bubble Sort) N² N² N² O O 선택 정렬(Selection Sort) N² N² N² X O 퀵 정렬(Quick Sort) NlogN Nlog..