1. 프로젝트 시작 계기

부트캠프가 끝나고.. 알고리즘 공부를 열심히 하던 중 유튜브에서 정렬 알고리즘에 대한 프로젝트를 접하게 되었다.

출처: https://www.youtube.com/watch?v=pFXYym4Wbkc&feature=share

특히 부트캠프에서 진행했던 프로젝트에서는 다뤄보지 못했던 상태관리 라이브러리도 다뤄보고 렌더링에 대한 공부도 다시 할 겸, 'Sorting Bars'라는 프로젝트를 진행하게 되었다.

진행했던 프로젝트 내용에 대한 전반적인 설명은 아래 Github에서 확인 가능하다.

Github : https://github.com/wongee93/sorting_bars

2. 프로젝트를 진행하며

1) 사용한 기술 스택

redux-toolkit

app.js의 구조는 정렬 알고리즘을 실행하는 버튼 컴포넌트와 바차트 컴포넌트로 구성하였기 때문에 20개의 랜덤한 높이의 bar들로 이루어진 배열을 다루기 위해서는 앞서 얘기했듯이 전역에서 상태를 관리할 필요가 있었다. redux-toolkit을 이용하여 상태를 관리해 주기로 했다.

2) 구현 기능

Reset

바차트를 생성하기 위해 랜덤으로 중복되지 않는 20개의 숫자들을 랜덤하게 생성해내는 함수를 작성하였다.

Sort

사용한 정렬 알고리즘

• Bubble Sort
  : 인접한 두 요소를 비교하여 정렬하는 방법. 배열 전체를 순회하며 비교하기 때문에 시간복잡도는 O(n²)이며 배열 하나만 사용하기 때문에 공간복잡도는 O(n)이다.

• Merge Sort
  : 배열을 2등분하여 정렬한 후, 병합하여 다시 정렬하는 방법. 시간복잡도는 O(nlogn)이며 공간복잡도는 O(n)이다.

3) 문제점

정렬이 진행되는 동안의 과정을 화면에 모두 렌더링하기 위해 어떻게 하면 좋을까 생각하며 많이 삽질(?)했었다. 처음에 랜덤 배열을 생성하고 정렬 로직을 적용했더니 정렬 후의 결과만 화면에 출력되어서 이를 위해선 어떻게 해야하나 고민하게 되었다.

4) 해결 방안

화면에 정렬 과정을 모두 출력하기 위해서는 각 Bar들의 상태를 기록할 필요가 있었다. 따라서 stateQueue 배열을 선언하여 그 안에 Bar의 상태를 기록하는 operation 객체를 넣었다.

operation 객체 안에는 1) 선택된 요소(selectedIdx) 2) 비교되는 요소(compareIdx) 3) 교체되는 요소(swapIdx) 4) 기존 요소(defaultIdx)로 상태를 기록하였다.

• bubbleSort 예시

const bubbleSort = (randomArray) => {
    const array = [...randomArray];
    const stateQueue = [];

    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - (i + 1); j++) {
            // 선택되는 index
            let operations = { selectedIdx: j };
            stateQueue.push(operations);

            // 비교하는 두 index 중, 이전 index 값이 더 클때(swap)
            if (array[j].value > array[j + 1].value) {
                operations = { selectedIdx: j, compareIdx: j + 1 };
                stateQueue.push(operations);
                operations = { selectedIdx: j, swapIdx: j + 1 };
                stateQueue.push(operations);

                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
            // 모든 비교를 마쳤을 때
            if (j === array.length - (i + 2)) {
                operations = { selectedIdx: j + 1, defaultIdx: j };
                stateQueue.push(operations);
            } else {
                operations = { defaultIdx: j };
                stateQueue.push(operations);
            }
        }
    }
    stateQueue.push({ selectedIdx: 0 });
    return stateQueue;
};

이처럼 stateQueue에 Bar들의 상태를 담아준 후 setTimeout을 이용하여 각 상태(selectedIdx, compareIdx, swapIdx, defaultIdx)에 따른 색상코드를 달리 주어 화면에 표시하도록 하였다.

3. 느낀점

리덕스를 이용해서 프로젝트를 해본적은 처음이었는데, 확실히 리덕스를 왜 쓰는지 체감되었던 것 같다. 컴포넌트를 단 3개만 쓰는 프로젝트였음에도 불구하고 리덕스를 쓰지 않았더라면 어떻게 구현해야할지 생각만으로도 막막하다..

그리고 이번 프로젝트를 진행하면서 렌더링에 대한 이해도 높일 수 있었다고 생각한다. 단순히 알고리즘 뿐 아니라 브라우저 구동 원리라던가 전반적인 웹 구동 과정에 대해서도 꾸준히 공부할 필요가 있음을 느끼게 되는 프로젝트였다.