บทความนี้สาธิตการจัดเรียงอาร์เรย์ที่มีค่าเพียง -1, 0, 1 แบบ in-place และ linear time (Dutch National Flag algorithm)
ตัวอย่างโค้ด
const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1];
const sortSpecialArray = (arr = []) => {
const swap = (a, b) => {
let middle = arr[a];
arr[a] = arr[b];
arr[b] = middle;
};
let left = 0;
let middle = 0;
let right = arr.length - 1;
while (middle <= right) {
if (arr[middle] === -1) {
swap(left++, middle++);
} else if (arr[middle] === 0) {
middle++;
} else if (arr[middle] === 1) {
swap(right--, middle);
}
}
};
sortSpecialArray(arr);
console.log(arr);
ผลลัพธ์
[-1, -1, 0, 0, 0, 0, 1, 1, 1, 1, 1]
คำอธิบาย
ใช้ 3 pointers: left (ขอบ -1), middle (current), right (ขอบ 1)
-1: swap กับ left, ขยับ left และ middle
0: ขยับ middle อย่างเดียว
1: swap กับ right, หด right (middle ไม่ขยับ เพราะต้องตรวจสอบค่าใหม่)
Time: O(n), Space: O(1)
