정렬

정렬

정렬은 탐색을 위함

bubble

function bubbleSort(arr) { for (let i = arr.length; i > 1; i--) { for (let j = 0; j < i - 1; j++) { if (arr[j] > arr[j+1]) { [arr[j], arr[j+1]] = [arr[j+1], arr[j]]; } } } return arr; }

insertion sort

• 정렬 중간 단계에서 배열 중간에 삽입할 원소를 밀어 넣는 과정에서 헤맸다

function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { if (arr[i] > arr[i-1]) continue; let cur = i; for (let j = i-1; j >= 0; j--) { if (arr[cur] < arr[j]) { [arr[cur], arr[j]] = [arr[j], arr[cur]]; cur = j; } else { break; } } } return arr; }

• 꼭 원소를 밀어 넣지 않아도 원소의 값만 따로 저장하고 덮어쓰는 방식으로도 구현 할 수 있었다

quick sort

• 구현할 때 조건문의 경계에 등호를 붙일 지 안 붙일 지가 매우 헤맸다

function quickSort(arr, leftIndex, rightIndex) { if (leftIndex < rightIndex) { let index = partition(arr, leftIndex, rightIndex); quickSort(arr, leftIndex, index - 1); quickSort(arr, index + 1, rightIndex); } function partition(dataSet, left, right) { let pivotIndex = left; // * 1 let pivot = dataSet[left] left++; while (left <= right) { // * 2 while (dataSet[left] <= pivot && left < right) { // * 3 left++; } while (dataSet[right] > pivot && left <= right) { // * 4 right--; } if (left < right) { [dataSet[left], dataSet[right]] = [dataSet[right], dataSet[left]]; } else { // * 5 break; } } [dataSet[right], dataSet[pivotIndex]] = [dataSet[pivotIndex], dataSet[right]]; return right; } }

1. js는 C언어 처럼 포인터로 swap이 안되기 때문에 인덱스값으로 swap하기 위해 피벗의 인덱스 저장
2. 피벗에 첫 값을 넣고 left 값을 1 증가 시켰기 때문에 탐색 범위가 2라면 최초에 left값과 right값이 같을 때에도 정렬을 해야 하므로 등호를 넣어줌
3. 피벗과 좌우 탐색 포인터 중 하나라도 가리키는 값이 같을 때를 조건에 넣지 않으면 같은 값이 있을 때 left나 right가 증감할 수 있는 조건이 없어지므로 무한 루프에 빠짐
4. 왼쪽 탐색 포인터가 탐색을 끝냈을 때 오른쪽 탐색 포인터가 가리키는 값이면 오른쪽 탐색 포인터가 왼쪽으로 cross하면서 탐색을 종료하기 위해 등호를 넣어줌
5. 좌우 탐색 포인터가 서로 만났지만 오른쪽 탐색 포인터가 가리키는 값이 피벗보다 작아서 cross되지 않았을 때 left == right가 되어 무한 루프에 빠짐 (ex. [3,2,1])