회사 직원들과 잡담중에 알고리즘에대한 얘기가 나왔다.
그래서 적어본다.
조금있다가 정리해본다
const A = [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
const maxValue = 6;
const B: number[] = [];
const sortArray: number[] = [];
console.log(B); //[]
for (let i = 0; i < maxValue + 1; i += 1) {
B[i] = 0;
}
console.log(B); // [0, 0, 0, 0, 0, 0, 0]
for (let i = 0; i < A.length; i += 1) {
B[A[i]] = B[A[i]] + 1;
}
console.log(B); // [0, 2, 2, 2, 2, 2, 1]
for (let i = 0; i < B.length; i += 1) {
let targetSum = B[i - 1];
if (targetSum === undefined) {
targetSum = 0;
}
B[i] = B[i] + targetSum;
}
console.log(B, "서포트 배열"); // [0, 2, 4, 6, 8, 10, 11] 서포트 배열
console.log(A); // [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5]
for (let i = 0; i < A.length; i += 1) {
sortArray[B[A[i]] - 1] = A[i];
B[A[i]] = B[A[i]] - 1;
}
console.log(sortArray); //[1, 1, 2, 2, 3,3, 4, 4, 5, 5,6]
console.log(B, "소트"); // [0, 0, 2, 4, 6, 8, 10]