- 검색은 자료 구조 내에 특정 항목을 찾는 일을 말하며, 배열이 정렬됐는지 여부에따라 두 가지 주요 기법이 있다.
선형 검색
배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작한다.
시간 복잡도 : O(n)
배열의 정렬 여부와는 관계없이 동작하기때문에 좋으므로 정렬되지 않은 배열을 검색하기 좋다.
function linearSearch(arr, n) {
for(var i = 0; i < arr.length; i++){
if (arr[i] == n) return true;
}
return false;
}
이진 검색 (탐색)
중간 값을 확인해서 원하는 값보다 중간 값이 작은지 큰지를 확인하면서 동작한다.
시간 복잡도: O(logn)
이진 탐색은 빠르지만 배열이 정렬된 경우에만 사용할 수 있다.
function binarySearch(arr, n) {
var lowIdx = 0, highIdx = arr.length - 1;
while (lowIdx <= highIdx) {
var midIdx = Math.floor((highIdx + lowIdx) / 2);
if (arr[midIdx] == n) return arr[midIdx];
else if (n>arr[midIdx]) lowIdx = midIdx;
else highIdx = midIdx;
}
return -1;
}
정렬 (sort)
거품 정렬 (bubble sort)
가장 간단한 알고리즘으로, 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다.
시간 복잡도: O(n^2) (중첩 루프)
거품 정렬은 모든 가능한 짝을 비교하기 때문에 최악의 정렬이라 할 수 있다.
function bubbleSort(array) {
for (var i = 0, arrayLength = array.length; i < arrayLength; i++) {
for (var j = 0; j <= i; j++) {
if (array[i] < array[j]) {
swap(array, i, j);
}
}
}
return array;
}
책의 예시는 인접 두 항목을 교환하는 코드가 아니어서 제로초님의 블로그글을 참고하여 공부하였다.
function bubbleSort(array) {
for (var i = 0, arrayLength = array.length; i < arrayLength - 1; i++) {
for (var j = 0; j < arrayLength - 1 - i; j++) {
if (array[j] > array[j+1]) { // 인접항목 교환
swap(array, j, j+1);
}
}
}
return array;
}
선택 정렬 (selection sort)
가장 작은 항목을 찾아서 해당 항목을 배열의 현 위치에 삽입한다.
시간 복잡도 : O(n^2) (중첩 루프)
function selectionSort(items) {
var len = items.length, min;
for (var i = 0; i < len; i++) {
min = i;
for (j = i+1; j < len; j++) {
if (items[j] < items[min]) {
min = j; // 최솟값의 위치를 min값에 할당
}
}
if (i != min) { // 현재 위치가 최솟값의 위치가 아니면 교환
swap(items, i, min);
}
}
return items;
}
삽입 정렬 (insertion sort)
배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다.
시간 복잡도 : O(n^2) (중첩 루프)
function insertionSort(items) {
var len = items.length, value, i, j;
for (i=0; i < len; i++) {
value = items[i]; // 현재 값 덮어써질수 있으므로 저장함
for (j = i-1; j > -1 && items[j] > value; j--) { // value가 검사값보다 작다면 검사값 위치 +1
items[j+1] = items[j];
} // j는 검사값이 크지 않을 때 까지 감소한다.
items[j+1] = value; // 감소한 j값 +1이 value의 위치(가장 작은값)
console.log(items);
}
return items;
}
빠른 정렬 (quick sort)
기준점을 획득한 다음 해당 기준점을 기준으로 왼쪽은 작은 항목, 오른쪽은 큰 항목으로 배열을 나눈다.
시간복잡도: 평균 - O(nlog_2(n)), 최악 - O(n^2)
기준점을 항상 잘못 선택하는 경우는 시간 복잡도가 O(n^2)이 될 수 있다.
function quickSort(items) {
return quickSortHelper(items, 0, items.length - 1);
}
function quickSortHelper(items, left, right) {
var index;
if (items.length > 1) {
index = partition(items, left, right);
if (left < index - 1) { // 기준점 왼쪽 빠른정렬
quickSortHelper(items, left, index - 1);
}
if (index < right) { // 기준점 오른쪽 빠른정렬
quickSortHelper(items, index, right);
}
}
return items;
}
function partition(array, left, right) { // 기준점 중앙으로
var pivot = array[Math.floor((right + left) / 2)];
while (left <= right) {
while (pivot > array[left]) {
left++;
}
while (pivot < array[right]) {
right--;
}
if (left <= right) {
var temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
return left;
}
빠른 선택 (quick select)
정렬되지 않은 목록에서 k번째로 작은 항목을 찾는 선택 알고리즘이다.
빠른 정렬과 같은 접근법을 사용하지만, 기준점의 양쪽 모두를 재귀적으로 수행하는 대신 한쪽만을 재귀적으로 수행한다는 차이점이있다.
JS 자료구조&알고리즘 (4) - 검색과 정렬
10장. 검색과 정렬
검색 (search)
- 검색은 자료 구조 내에 특정 항목을 찾는 일을 말하며, 배열이 정렬됐는지 여부에따라 두 가지 주요 기법이 있다.
선형 검색
이진 검색 (탐색)
정렬 (sort)
거품 정렬 (bubble sort)
책의 예시는 인접 두 항목을 교환하는 코드가 아니어서 제로초님의 블로그글을 참고하여 공부하였다.
선택 정렬 (selection sort)
삽입 정렬 (insertion sort)
빠른 정렬 (quick sort)
빠른 선택 (quick select)
병합 정렬 (merge sort)
계수 정렬 (count sort)
자바스크립트 내장 정렬
요약
'cs지식 > 자료구조' 카테고리의 다른 글