sort

개념 계수정렬은 굉장히 특이한 녀석이다. 똑같은 수가 많이 존재하는 배열을 정렬하는데 가장 좋다. 로직은 무식하게 각 숫자의 갯수를 세는 것 괜히 영어로 CountingSort가 아니다. 구현 const countingSort = (inputArray) => { const maxNumber = Math.max(...inputArray); const result = []; const countArray = Array.from({ length: maxNumber + 1 }).map(() => 0); inputArray.forEach((num) => { countArray[num]++; }); countArray.forEach((numberCount, index) => { for (let x = 0; x < ..

큐 큐는 간단하다. FIFO. First In First Out 먼저들어온게 먼저나가는 자료구조이다. 원래는 링크드리스트로 구현하지만, 배열로 간단하게 구성해주었다. class Queue { constructor() { this.queue = []; } inqueue(value) { this.queue.push(value); } dequeue() { const [node, ...newQueue] = this.queue; this.queue = newQueue; return node; } isEmpty() { return this.queue.length === 0; } } module.exports = Queue; 기수정렬 개념 양수를 정렬하는경우, 0부터 9까지의 각각 큐를 준비한다. 제일 큰 숫자의 자..

개념 파티션 퀵정렬은 임의의 값인 피봇을 지정(나같은 경우 배열의 첫값을 설정했다.)하고, 그 인덱스를 제외한 배열 들을 좌측과 우측끝에서 비교하며 진행한다. 좌측은 pivot보다 작은 경우 진행하고 우측은 pivot보다 큰 경우 진행한다. 좌측이 pivot보다 크면 좌측인덱스는 거기서 정지한다. 우측이 pivot보다 작으면 우측 인덱스는 거기서 정지한다. 더이상 진행이 되지않는데 좌측인덱스가 우측인덱스보다 왼쪽에 있으면 좌우측값을 교환한다. 이후, 좌측인덱스가 우측인덱스보다 커지면 pivot과 오른쪽인덱스를 교환하고, 오른쪽 인덱스를 반환한다. 이때 pivot은 배열에서 자기 위치에 맞는 위치를 갖게된다. 분할정복 파티션이 완료되면 해당 인덱스를 기준으로 왼쪽 배열과 오른쪽 정렬에 대해 파티션을 진행한..

개념 전체 배열을 돌면서 현재 인덱스를 진행시키는데, 이때 값은 key라고 한다면, key가 현재인덱스값보다 작을때까지, 현재 인덱스를 배열의 왼쪽끝까지 옮겨가며 값을 비교한 뒤에, 현재인덱스값을 현재인덱스-1의 값으로 바꾸고 인덱스를 줄인다. 이 과정이 끝나면, key를 현재 인덱스에 넣어준다. 구현 const insertSort = (inputArray) => { for (let index = 1; index 0 && inputArray[currentIndex - 1] > key) { inputArray[cu..