LeetCode - 75. Sort Colors

leetcode.com/problems/sort-colors/

Sort Colors - LeetCode

 

 

 

Answer

 

 QuickSort를 이용해서 풀었다

 

 이번에 알아본 QuickSort은 다음과 같이 진행된다.

1. Pivot index를 정한다

2. Pivot index보다 작은 값은 왼쪽으로 옮긴다

3. Pivot index보다 큰 값은 오른쪽으로 옮긴다

4. 위 과정을 반복한다

 

 

 구현은 Partition이라는 함수를 통해 진행되는데

Partition은 Pivot이 들어가야 하는 인덱스를 추적하는 'i'변수를 통해 진행된다

'i'변수는 Pivot보다 작은 값이 들어있는 값을 추적하는 변수여서

 

31번라인에 보면 i+1과 현재 Pivot인 high를 swap해주며 Partition index를 찾아낸다