정렬

정렬 알고리즘

• Quic Sort

• DFS ( Depth Frist Search)
코드 예제

const TREE =  {
    A: ["B", "C"],
    B: ["A", "D"],
    C: ["A", "E"],
    D: ["B", "F"],
    E: ["C","G"],
    F: ["D","H","I"],
    G: ["E","J","K"],
    H: ["F","L"],
    I: ["F", "M"],
    J: ["G","N"],
    K: ["G","O"],
    L: ["H"],
    M: ["I","P"],
    N: ["J"],
    O: ["K"],
    P: ["M"]
}


/**
 * 깊이 우선 탐색 (depth first search)
 *
 *
 * @param {*} tree
 * @param {*} start
 */
const quest_dfs = (tree, start) => {
    const checked = []; // 탐색 완료 데이터
    const willCheck = []; //탐색 예정 데이터

    willCheck.push(start);
    console.log(`탐색 예정 데이터 추가 : ${willCheck}`);

    while(willCheck.length !== 0){
        const node = willCheck.pop(); //스택 (Last In First Out)

        if(!checked.includes(node)){ //체크된 리스트에 없으면
            checked.push(node) // 노드 추가 후
            console.log(`${node} 탐색 종료`);
            console.log(`${node}의 하위 노드 탐생 예정 데이터 추가 : ${tree[node].join(' ')}`);
            willCheck.push(...tree[node].reverse()); // 해당 노드의 하위 노드들을 체크리스트에 추가
            console.log(`탐색 예정 데이터 : ${willCheck}`);
        }

    }

    return checked;
}

console.log('결과 : ',quest_dfs(TREE, 'A'));


탐색 예정 데이터 추가 : A
A 탐색 종료
A의 하위 노드 탐생 예정 데이터 추가 : B C
탐색 예정 데이터 : C,B
B 탐색 종료
B의 하위 노드 탐생 예정 데이터 추가 : A D
탐색 예정 데이터 : C,D,A
D 탐색 종료
D의 하위 노드 탐생 예정 데이터 추가 : B F
탐색 예정 데이터 : C,F,B
F 탐색 종료
F의 하위 노드 탐생 예정 데이터 추가 : D H I
탐색 예정 데이터 : C,I,H,D
H 탐색 종료
H의 하위 노드 탐생 예정 데이터 추가 : F L
탐색 예정 데이터 : C,I,L,F
L 탐색 종료
L의 하위 노드 탐생 예정 데이터 추가 : H
탐색 예정 데이터 : C,I,H
I 탐색 종료
I의 하위 노드 탐생 예정 데이터 추가 : F M
탐색 예정 데이터 : C,M,F
M 탐색 종료
M의 하위 노드 탐생 예정 데이터 추가 : I P
탐색 예정 데이터 : C,P,I
P 탐색 종료
P의 하위 노드 탐생 예정 데이터 추가 : M
탐색 예정 데이터 : C,M
C 탐색 종료
C의 하위 노드 탐생 예정 데이터 추가 : A E
탐색 예정 데이터 : E,A
E 탐색 종료
E의 하위 노드 탐생 예정 데이터 추가 : C G
탐색 예정 데이터 : G,C
G 탐색 종료
G의 하위 노드 탐생 예정 데이터 추가 : E J K
탐색 예정 데이터 : K,J,E
J 탐색 종료
J의 하위 노드 탐생 예정 데이터 추가 : G N
탐색 예정 데이터 : K,N,G
N 탐색 종료
N의 하위 노드 탐생 예정 데이터 추가 : J
탐색 예정 데이터 : K,J
K 탐색 종료
K의 하위 노드 탐생 예정 데이터 추가 : G O
탐색 예정 데이터 : O,G
O 탐색 종료
O의 하위 노드 탐생 예정 데이터 추가 : K
탐색 예정 데이터 : K
결과 :  [
  'A', 'B', 'D', 'F',
  'H', 'L', 'I', 'M',
  'P', 'C', 'E', 'G',
  'J', 'N', 'K', 'O'
]

• BFS(Bridth Frist Search)
코드 예제

const quest_bfs = (tree, start) => {
    const checked = []; // 탐색 완료 데이터
    const willCheck = []; //탐색 예정 데이터

    willCheck.push(start);
    console.log(`탐색 예정 데이터 추가 : ${willCheck}`);

    while(willCheck.length !== 0){
        const node = willCheck.shift(); //스택 (First In First Out)

        if(!checked.includes(node)){ //체크된 리스트에 없으면
            checked.push(node) // 노드 추가 후
            console.log(`${node} 탐색 종료`);
            console.log(`${node}의 하위 노드 탐생 예정 데이터 추가 : ${tree[node].join(' ')}`);
            willCheck.push(...tree[node]); // 해당 노드의 하위 노드들을 체크리스트에 추가
            console.log(`탐색 예정 데이터 : ${willCheck}`);
        }

    }

    return checked;
}
console.log(quest_bfs(TREE, 'A'));

탐색 예정 데이터 추가 : A
A 탐색 종료
A의 하위 노드 탐생 예정 데이터 추가 : B C
탐색 예정 데이터 : B,C
B 탐색 종료
B의 하위 노드 탐생 예정 데이터 추가 : A D
탐색 예정 데이터 : C,A,D
C 탐색 종료
C의 하위 노드 탐생 예정 데이터 추가 : A E
탐색 예정 데이터 : A,D,A,E
D 탐색 종료
D의 하위 노드 탐생 예정 데이터 추가 : B F
탐색 예정 데이터 : A,E,B,F
E 탐색 종료
E의 하위 노드 탐생 예정 데이터 추가 : C G
탐색 예정 데이터 : B,F,C,G
F 탐색 종료
F의 하위 노드 탐생 예정 데이터 추가 : D H I
탐색 예정 데이터 : C,G,D,H,I
G 탐색 종료
G의 하위 노드 탐생 예정 데이터 추가 : E J K
탐색 예정 데이터 : D,H,I,E,J,K
H 탐색 종료
H의 하위 노드 탐생 예정 데이터 추가 : F L
탐색 예정 데이터 : I,E,J,K,F,L
I 탐색 종료
I의 하위 노드 탐생 예정 데이터 추가 : F M
탐색 예정 데이터 : E,J,K,F,L,F,M
J 탐색 종료
J의 하위 노드 탐생 예정 데이터 추가 : G N
탐색 예정 데이터 : K,F,L,F,M,G,N
K 탐색 종료
K의 하위 노드 탐생 예정 데이터 추가 : G O
탐색 예정 데이터 : F,L,F,M,G,N,G,O
L 탐색 종료
L의 하위 노드 탐생 예정 데이터 추가 : H
탐색 예정 데이터 : F,M,G,N,G,O,H
M 탐색 종료
M의 하위 노드 탐생 예정 데이터 추가 : I P
탐색 예정 데이터 : G,N,G,O,H,I,P
N 탐색 종료
N의 하위 노드 탐생 예정 데이터 추가 : J
탐색 예정 데이터 : G,O,H,I,P,J
O 탐색 종료
O의 하위 노드 탐생 예정 데이터 추가 : K
탐색 예정 데이터 : H,I,P,J,K
P 탐색 종료
P의 하위 노드 탐생 예정 데이터 추가 : M
탐색 예정 데이터 : J,K,M
[
  'A', 'B', 'C', 'D',
  'E', 'F', 'G', 'H',
  'I', 'J', 'K', 'L',
  'M', 'N', 'O', 'P'
]