[JS/알고리즘] Sort Colors : Dutch national flag problem

Dutch national flag problem

array[0] ~ [low-1] zeros (red)  
array[low] ~ [mid-1] onew (white)  
array[mid] ~ [high] unknown  
array[high+1] ~ [length-1] twos (blue)

처음에 모든 요소는 unknown 상태이기 때문에
low = 0

mid = 0

high = length-1

이다.

 

 

 

Dutch national flag problem

 

 

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

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.

Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

 

---

 

 

var sortColors = function (nums) {
  const { length } = nums;
  let low = 0; // red
  let mid = 0; // white
  let high = length - 1; // blue

  while (mid <= high) {
    if (nums[mid] === 0) {
      swap(nums, low, mid);
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      swap(nums, mid, high);
      high--;
    }
  }
};

function swap(array, a, b) {
  const temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

 

 

출처1 : en.wikipedia.org/wiki/Dutch_national_flag_problem

출처2 : www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/

출처3 : leetcode.com/problems/sort-colors/