정리 노트

이 글은 제가 저번에 적은 글에 이어서 작성하는 글입니다. 그러니 이전 글을 읽고 이 글을 읽어주시기 바랍니다. 2022.10.22 - [개념 정리/알고리즘] - 퀵 정렬(Quick Sort) (with Lomuto) 두 번째 Partiton 방법 이번에 소개하는 partition 방법은 Hoare가 제시한 방법입니다.(사실 퀵 정렬 알고리즘을 제안한 사람이 Hoare입니다.) 이번 partition도 pivot 값을 배열의 가장 왼쪽 값으로 정하고 시작합니다. i와 j의 초기값은 각각 -1, 배열의 길이로 배열의 양 끝을 지정하는 인덱스입니다. 먼저 i의 값을 하나 증가시키고 i번째 원소가 pivot값보다 작으면 다시 i값을 늘려줍니다. 이 과정을 배열의 i번째 값이 pivot보다 크거나 같을 때까지 ..

이 글은 Divide & Conquer에 대해 기본적인 내용을 알고 계신다는 가정 하에 작성되었습니다. 따라서 분할 정복 기법에 대해 잘 모르시는 분들은 제가 저번에 썼던 글을 참고하셔도 됩니다. 2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer) 퀵 정렬 이름 그대로 빠르게 정렬하는 알고리즘입니다. 퀵 정렬도 분할 정복 기법 방식으로 설명할 수 있습니다. Divide: 배열의 원소들 중 임의의 원소 하나를 기준(pivot)으로 정하고 기준보다 작은 원소들의 그룹과 큰 원소들의 그룹으로 나눕니다. Conquer: 기준점을 중심으로 나누어진 두 그룹을 recursive 하게 quick sort를 수행합니다. 이 설명에서는 'combine' 과정이 빠져있습니다...