[OJ.leetcode] sort-colors

https://oj.leetcode.com/problems/sort-colors/

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

/* O(n) 이자 multi pass(2회 순회)로 푸는 알고리즘은 금방 떠올릴 수 있음. 2회 순회(1회: 2는 무조건 맨 마지막으로 swap, 2회: 1은 무조건 마지막 2의 앞으로 swap. 0은 자동으로 맨앞에 위치) 사전질문: 0,1,2가 최소한 1번씩은 존재하는가? no could be like [0,0,0,0,0,0] 목표 : onepass, constant space 결과 : 1시간 동안 고민한 끝에, swap 솔루션에 거의 근접했지만 swap 후 처리를 제대로 못해 좌절(if the swaped element is 2 or 1, how handle this?) 0은 앞에, 2는 맨뒤에 정렬하고 0과 2를 가리키는 포인터를 두어 불변식 A[0..i-1]은 0또는 1만 존재 && A[i+1...n-1]은 반드시 2만 존재함을 매 루프마다 만족시켜가면 정답임을 확신 가능함. (1은 따로 처리하지 않아도 자동 처리된다는 것을 알아채는 것이 point) other solutions: void sortColors(int A[], int n) { int i = 0, j = n-1; for (int k = 0; k <= j; k++) { switch (A[k]) { case 0: A[k] = 1; A[i++] = 0; break; case 1: break; case 2: A[k--] = A[j]; A[j--] = 2; break; } } } void sortColors(int A[], int n) { int colorIndex[3] = {0}; for(int i = 0; i < n; i++) { int color = A[i]; for (int j = 2; j >= color; j--) A[colorIndex[j]++] = j; } } */ class Solution { public: void sortColors(int A[], int n) { int zeroPos = 0; int twoPos = n; for(int i=0; i<twoPos ; ++i) { if(A[i] == 0) { swap(A[i], A[zeroPos++]); } else if(A[i] == 2) { swap(A[i--], A[--twoPos]); } } } };