검색과 정렬

검색

선형 검색 : 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작

function linearSearch(array, n) {
    for (var i = 0; i < array.length; i++) {
        if (array[i] == n) {
            return true;
        }
    }
    return false;
}

console.log(linearSearch([1,2,3,4], 4));
console.log(linearSearch([1,2,3,4], 5));

시간복잡도: O(n)

 

이진 검색 : 중간 값을 확인해 원하는 값보다 해당 중간 값이 큰지 작은지 확인한다. 원하는 값이 중간 값보다 작은 경우 이진 검색 알고리즘은 중간 값보다 작은 쪽을 검색하고 원하는 값이 중간 값보다 중간 값보다 큰 경우 중간 값보다 큰 쪽을 검색한다.

function binarySearch(array, n) {
    var lowIndex = 0,
        highIndex = array.length - 1;

    while (lowIndex <= highIndex) {
        var midIndex = Math.floor((highIndex + lowIndex) / 2);
        if (array[midIndex] == n) {
            return midIndex;
        } else if (n > array[midIndex]) {
            lowIndex = midIndex+1;
        } else {
            highIndex = midIndex-1;
        }
    }
    return -1;
}
console.log(binarySearch([1,2,3,4], 4));
console.log(binarySearch([1,2,3,4], 5));

정렬

거품 정렬 : 가장 간단한 정렬 알고리즘. 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환

function bubbleSort(array) {
    for (var i = 0, arrayLength = array.length; i < arrayLength; i++) {
        for (var j = 0; j <= i; j++) {
            if (array[j] > array[j+1]) {
                swap(array, i, j);
            }
        }
    }
    return array;
}

function swap(array, index1, index2) {
    var temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

bubbleSort([6, 1, 2, 3, 4, 5]); // [1,2,3,4,5,6]

시간 복잡도:O(n^2))

공간 복잡도:O(1)

최악이야

 

선택 정렬 : 가장 작은 항목을 찾아서 해당 항목을 배열의 현 위치에 삽입하는 방식. 거품 정렬보단 괜찮아

function selectionSort(items) {
    var len = items.length,
        min;

    for (var i = 0; i < len; i++) {
        // set minimum to this position
        min = i;
        //check the rest of the array to see if anything is smaller
        for (j = i + 1; j < len; j++) {
            if (items[j] < items[min]) {
                min = j;
            }
        }
        //if the minimum isn't in the position, swap it
        if (i != min) {
            swap(items, i, min);
        }
    }

    return items;
}
selectionSort([6, 1, 23, 4, 2, 3]); // [1, 2, 3, 4, 6, 23]
//위에 swap함수 생략

시간 복잡도:O(n^2)

공간 복잡도:O(1)

 

삽입 정렬 : 배열을 순간적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다.

function insertionSort(items) {
  var len = items.length, // number of items in the array
      value, // the value currently being compared
      i, // index into unsorted section
      j; // index into sorted section

  for (i = 0; i < len; i++) {
      // store the current value because it may shift later
      value = items[i];

      // Whenever the value in the sorted section is greater than the value
      // in the unsorted section, shift all items in the sorted section over
      //by one. This creates space in which to insert the value.

      for (j = i - 1; j > -1 && items[j] > value; j--) {
          items[j + 1] = items[j];
      }
      items[j + 1] = value;
  }
  return items;
}
insertionSort([6, 1, 23, 4, 2, 3]); // [1, 2, 3, 4, 6, 23]

시간 복잡도:O(n^2)

공간 복잡도:O(1)

 

빠른 정렬 : 기준점을 획득한 다음 해당 기준점을 기준으로 배열을 나눈다. 일반적으로 분할 부분의 첫번째 항목과 중간 항목, 마지막 항목의 중간 값을 취해 기준점을 얻는다.

코드 이해안돼

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;
}

quickSort([6, 1, 23, 4, 2, 3]); // [1, 2, 3, 4, 6, 23]

시간 복잡도:평균 O(nlog₂n), 최악의 경우 O(n^2)

공간 복잡도:O(log2n)

 

빠른 선택 : 정렬되지 않은 목록에서 k번째로 작은 항목을 찾는 선택 알고리즘이다.

var array = [1, 3, 3, -2, 3, 14, 7, 8, 1, 2, 2];
// sorted form: [-2, 1, 1, 2, 2, 3, 3, 3, 7, 8, 14]

function quickSelectInPlace(A, l, h, k) {
  var p = partition(A, l, h);
  if (p == k - 1) {
    return A[p];
  } else if (p > k - 1) {
    return quickSelectInPlace(A, l, p - 1, k);
  } else {
    return quickSelectInPlace(A, p + 1, h, k);
  }
}

function medianQuickselect(array) {
  return quickSelectInPlace(
    array,
    0,
    array.length - 1,
    Math.floor(array.length / 2)
  );
}

quickSelectInPlace(array, 0, array.length - 1, 5); // 2
// 2 - because it's the fifth smallest element
quickSelectInPlace(array, 0, array.length - 1, 10); // 7
// 7 - because it's the tenth smallest element

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;
}

시간 복잡도:O(n)

 

병합 정렬 : 각 하위 배열에 하나의 항목이 존재할 때까지 배열을 하위 배열로 나눈다. 그러고 나서 각 하위 배열을 정렬된 순서로 연결(병합)한다.

function merge(leftA, rightA){
    var results= [], leftIndex= 0, rightIndex= 0;

    while (leftIndex < leftA.length && rightIndex < rightA.length) {
        if( leftA[leftIndex]<rightA[rightIndex] ){
            results.push(leftA[leftIndex++]);
        } else {
            results.push(rightA[rightIndex++]);
        }
    }
    var leftRemains = leftA.slice(leftIndex),
        rightRemains = rightA.slice(rightIndex);

    // add remaining to resultant array
    return results.concat(leftRemains).concat(rightRemains);
}

function mergeSort(array) {
    if(array.length<2){
        return array; // Base case: array is now sorted since it's just 1 element
    }

    var midpoint = Math.floor((array.length)/2),
        leftArray = array.slice(0, midpoint),
        rightArray = array.slice(midpoint);

    return merge(mergeSort(leftArray), mergeSort(rightArray));
}
mergeSort([6,1,23,4,2,3]); // [1, 2, 3, 4, 6, 23]

시간 복잡도:O(nlog2(n))

공간 복잡도:O(n)

 

계수 정렬 : 숫자에 대해서만 동작하며 특정 범위가 주어져야 한다. 항목들을 교환하면서 정렬하는 대신에 배열의 각 항목의 등장 횟수를 센다. 각 항목의 등장 횟수를 센 다음 해당 등장 횟수를 사용해 새로운 배열을 생성할 수 있다.

function countSort(array) {
    var hash = {},
        countArr = [];
    for (var i = 0; i < array.length; i++) {
        if (!hash[array[i]]) {
            hash[array[i]] = 1;
        } else {
            hash[array[i]]++;
        }
    }

    for (var key in hash) {
        // for any number of _ element, add it to array
        for (var i = 0; i < hash[key]; i++) {
            countArr.push(parseInt(key));
        }
    }

    return countArr;
}
countSort([6, 1, 23, 2, 3, 2, 1, 2, 2, 3, 3, 1, 123, 123, 4, 2, 3]); // [1, 2, 3, 4, 6, 23]

시간 복잡도:O(k+n)

공간 복잡도:O(k)

제한된 범위의 정수를 정렬할 때는 계수 정렬을 사용한다. 이러한 종류의 자료에 대해서는 계수 정렬이 가장 빠른 정렬이다.

 

자바스크립트 내장 정렬 sort

ms3864.tistory.com/56

자바스크립트 배열 메소드2(sort)