5장 정렬과 검색

[48] 정렬(소트)이란 대상을 특정한 규칙에 따라 정렬하는 것

정렬이란 대상이 갖고 있는 특성을 기준으로 나열하는 것이다.
정렬 순서에는 ‘오름차순(작은 순서)’과 '내림차순(큰 순서)'이 있다.

[49] 정렬 알고리즘에는 다양한 종류가 있다.

데이터 정렬은 알고리즘의 핵심 과제 중 하나이며, 다양한 정렬 알고리즘이 고안되어 있다.

버킷 정렬

최대값의 개수만큼 물통을 준비한 다음, 그곳에 데이터를 저장하고 정렬한다.

기수 정렬

숫자의 각 자리를 기준으로 차례대로 데이터를 정렬한다.

단순 선택 정렬

데이터 중에서 최소 값(또는 최대값)을 찾아, 1번째 요소 (또는 마지막 요소)의 데이터와 교환한다.

단순 교환 정렬 (버블 정렬)

서로 이웃한 데이터끼리 크고 작음을 비교해서 올바를 위치로 데이터를 이동 시킨다.

단순 삽입 정렬

정렬할 데이터를 이미 정렬된 데이터들 사이의 올바를 위치에 삽인한다.

셸 정렬

정렬할 데이터들의 일정한 개수의 그룹으로 묶어서 정렬한다.

병합 정렬

정렬할 데이터를 반으로 자르고, 자른 데이터를 다시 반으로 자를 작업을 되풀이 한다.
데이터를 더이상 자를 수가 없다면, 자른 데이터들을 정렬한 후 다른 부분들과 병합하고 다시 정렬시키는 작업을 자른 순서의 역순으로 반복해서 정렬한다.

퀵 정렬

정렬할 데이터 안에서 임의의 숫자를 선택하고 그 값의 크고 작음을 기준으로 데이터들을 반으로 쪼갠다.
이 과정을 반복해서 정렬한다.

힙 정렬

힙 구조를 이용하여 정렬한다.

[50] 다른 배열(양동이)에 데이터를 저장하고 정렬하는 ‘버킷정렬’

빈 양동이 배열을 준비하고, 양동이의 번호와 일치하는 모든 데이터를 저장한 다음, 1번째 양동이의 데이터부터 꺼내는 것이 버킷정렬이다.

const bucketSort = (input) => {
  const bucket = new Array(Math.max(...input));
  input.forEach((i) => {
    bucket[i] = i;
  })
  bucket.filter(b => b !== undefined);
}

[51] 아래 자릿수부터 윗 자릿수까지 버킷 정렬을 반복하는 ‘기수 정렬’

각 자릿수의 숫자 값을 기준으로 정렬하는 것이 기수 정렬이다.
k 자릿수의 숫자들을 정렬 하려면 k개를 버킷 정렬한다.

let counter = [[]];
const radixSort = (array, maxDigit) => {
    let mod = 10;
    let dev = 1;
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for (let j = 0; j < array.length; j++) {
            let bucket = parseInt((array[j] % mod) / dev);
            if (counter[bucket] == null ) {
                counter[bucket] = [];
            }
            counter[bucket].push(array[j]);
        }
        let pos = 0;
        for (let j = 0; j < counter.length; j++) {
            let value = null ;
            if (counter[j] != null ) {
                while ((value = counter[j].shift()) != null ) {
                    array[pos++] = value;
                }
            }
        }
    }
    return array;
}
const test = [123, 602, 82, 777, 57, 510, 396, 196, 843, 138];
console.log(radixSort(test, 3));

[52] 최소 값(최대 값)을 골라서 이미 정렬된 마지막 요소와 교환하는 ‘단순 선택 정렬’

단순 선택 정렬은 ‘정렬되지 않은 부분’안의 최소 값 (또는 최대값)을 선택해서 ‘정렬된 부분’의 끝으로 옮긴다.

const array = [35, 80, 21, 54, 11, 45, 92, 39];
const selectSort = (array) => {
  const sortedArray = [];
  while (array.length > 1) {
    sortedArray.push(Math.min(...array));
    array = array.filter(a => a !== Math.min(...array));
  };
  return sortedArray;
};
console.log(selectSort(array));

[53] 이웃한 데이터들을 교환해 나가는 '단순 교환 정렬 (버블정렬)'

단순 교환 정렬 (버블정렬)은 이웃한 데이터 2개의 크고 작음을 비교한 뒤, 정렬 조건에 맞추어 이동시킨다.

const array = [19, 80, 77, 11, 54];
const bubbleSort = (arr) => {
   for(let count = 0 ; count < arr.length ; count++){
       for(let i = 1 ; i < arr.length-count ; i++){
           if(arr[i-1]>arr[i]){
               const temp = arr[i-1];
               arr[i-1] = arr[i]; 
               arr[i] = temp;
           }
       }
   }
   return arr;
}
console.log(bubbleSort(array));

[54] 정렬된 데이터를 비교해서 올바른 위치에 삽입하는 ‘단순 삽입 정렬’

단순 삽입 정렬은 배열 안의 ‘정렬된 부분’안에 ‘정렬되지 않은 부분’의 데이터들을 정렬 조건에 맞추어 삽입해 나가는 알고리즘이다.

const array = [77, 19, 80, 79, 20, 11];
const insertionSort = (arr) => {
  for (let i = 1; i < array.length; i++) {
    let currentValue = array[i];
    let leftIndex = i - 1;
    while (leftIndex >= 0 && arr[leftIndex] > currentValue) {
      arr[leftIndex + 1] = arr[leftIndex];
      leftIndex--;
    }
    arr[leftIndex + 1] = currentValue;
  }
  return arr;
}
console.log(insertionSort(array));

[55] 데이터 열을 일정한 길이의 그룹으로 나누어 정렬하는 ‘셸 정렬’

셸 정렬은 정렬할 데이터 배열을 일정 길이의 그룹으로 나누고, 그 그룹 안에서 정렬조건에 맞추어 정렬한다.

const arr = [67, 19, 26, 55, 11, 92, 2, 77, 20, 10, 80, 35];

const shellSort = (arr) => {
  const interval = parseInt(arr.length/2);
  
  for (let i=interval; i>0; i=parseInt(i/2)) {
    for (let j=0; j<interval; j++) {
      arr = intervalSort(i, j, arr);
    }
  }
  return arr;
};
const intervalSort = (interval, start, arr) => {
  const end = arr.length - interval + start;
  let idx = end;
  while (idx > start) {
    if (arr[idx-interval] > arr[idx]) {
      const temp = arr[idx];
      arr[idx] = arr[idx-interval];
      arr[idx-interval] = temp;
    }
    idx -= interval;
  }
  return arr;
};

console.log(shellSort(arr))

[56] 정렬된 여러 개의 데이터 열을 합체시키는 '병합(merge)'

오름차순으로 정렬된 여러 개의 데이터 열이 있을 때, 전체 열의 최소 값은 항상 각 데이터 열의 1번째에 있다.

[57] 병합 (merge) 알고리즘을 이용하여 정렬하는 ‘병합정렬’

병합정렬은 병합 알고리즘을 이용한 정렬이다.
병합정렬은 2개로 나누는 단계와 병합하는 단계로 구성된다.

const arr = [8, 2, 4, 12, 1, 9, 6, 3];

const mergeSort = (arr) => {
  if (arr.length < 2) {
  return arr;
  }
  const centre = Math.floor(arr.length/2);
  const left = arr.slice(0, centre);
  const right = arr.slice(centre);
  return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex ++;
    } else {
      result.push(right[rightIndex]);
      rightIndex ++;
    }
  }
  return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
console.log(mergeSort(arr));
 

[58] 기준 데이터와 크기를 비교해서 데이터를 2등분 하는 '퀵 정렬'

퀵 정렬은 고속 정렬 알고리즘으로 기준값보다 작은 그룹과 큰 그룹을 분류하는 작업을 반복해서 정렬한다.

const arr = [8, 2, 4, 11, 1, 9, 6, 3, 12, 7, 10];
const quickSort = (arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr[0];
  const smaller = [];
  const larger = [];
  const result = [];
  for (let i=1; i<arr.length; i++) {
    if (arr[i] > pivot) {
      larger.push(arr[i]);
    } else {
      smaller.push(arr[i]);
    }
  }
  return quickSort(smaller).concat(pivot, quickSort(larger));
};
console.log(quickSort(arr));

[59] 힙 구조를 이용해서 정렬하는 ‘힙 정렬’

힙 정렬은 힙의 특성을 이용한 정렬 알고리즘 이다.

const arr = [ 3, 2, 4, 9, 1 ];

const heapSort = (arr) => {
  const result = [];
  while (arr.length > 0) {
    arr = swap(arr)
    result.unshift(swap(arr)[0]);
    arr.splice(0,1);
  }
  return result;
};
const swap = (arr) => {
  if (arr.length < 2) {
    return arr;
  }
  let index = Math.floor(arr.length/2);  
  while (index > 0) {
    if (arr[index -1] < arr[2*index -1]) {
      const temp = arr[index-1];
      arr[index-1] = arr[2*index -1];
      arr[2*index -1] = temp;
    }
    else if (arr[index -1] < arr[2*index]) {
      const temp = arr[index-1];
      arr[index-1] = arr[2*index];
      arr[2*index] = temp;    
    }
    else { l 
      index -= 1;
    }
  }
  return arr;
};
console.log(heapSort(arr))

[60] 검색이란 여러 개의 데이터 안에서 원하는 데이터를 찾아내는 것

순차 검색 (리니어 서치)

1번째 데이터부터 샅샅이 검색

이진 검색 (바이너리 서치)

데이터들이 이미 정렬되어 있는 경우에 효율적으로 검색할 수 있음

간단한 문자열 검색

문자열 안에서 문자 패턴을 검색

KMP 알고리즘을 사용한 문자열 검색

일치하지 않는 문자와 부분 문자열의 구성 정보를 통해 효율적으로 문자를 검색함

BM 알고리즘을 사용한 문자열 검색

부분 문자열의 끝부터 앞부분의 순서대로 문자를 비교함

[61] 처음부터 끝까지 샅샅이 데이터를 비교하는 '순차검색 (리니어 서치)'

순차검색은 랜덤(무작위)로 나열된 데이터 열 안에서 원하는 데이터를 찾아내는 알고리즘이다.

const arr = [2, 9, 5, 1, 7, 8, 3, 4];
const linearSearch = (arr, target) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return;
}

console.log(linearSearch(arr, 7));

[62] 정렬된 데이터 안에서 고속 검색 하는 ‘이진 검색 (바이너리 서치)’

검색할 데이터 열이 정렬되어 있다면, 이진 검색으로 원하는 데이터를 빠르게 찾을 수 있다.

const arr = [2, 5, 6, 9, 12, 15, 16, 19, 24, 27, 30];
const binarySearch = (arr, target) => {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const centre = left + Math.floor((right - left) / 2);
    if (arr[centre] === target) {
      return centre;
    }
    arr[centre] < target ? (left = centre + 1) : (right = centre - 1);
    console.log(centre, left, rigth)
  }
  return;
}
console.log(binarySearch(arr, 9));

[63] 주어진 문자열 안에서 원하는 문자열의 위치를 찾아내는 ‘문자열 검색’

문자열 검색 알고리즘 에서는 ‘검색 대상이 여러 개의 문자로 이루어진 문자열’ 이라는 점을 고려한다.

const text = "ABBBACBBA";
const word = "BBA";

function searchWord(text, word) {
  let textIndex = 0;
  let wordIndex = 0;
  const result = [];
  while (textIndex < text.length) {
    if (text[textIndex] === word[wordIndex]) {
      let temp = textIndex;
      while (text[textIndex] === word[wordIndex]) {
        if (wordIndex === (word.length - 1)) {
          result.push(temp);
          temp = textIndex;
          wordIndex = 0;
          continue;
        }
        textIndex++;
        wordIndex++;
      }
    }
    textIndex = textIndex - wordIndex + 1;
    wordIndex = 0;
  }
  if (result.length > 0) {
    return result;
  }
  return -1;
}

console.log(searchWord(text, word));

const text = "ABBBACBBA";
const word = "BBA";

function searchWord(text, word) {
  let textIndex = 0;
  let wordIndex = 0;
  const result = [];
  while (textIndex < text.length) {
    if (text[textIndex] === word[wordIndex]) {
      if (wordIndex === (word.length - 1)) {
        result.push(textIndex - wordIndex);
        wordIndex = 0;
        continue;
      }
      textIndex++;
      wordIndex++;
    } else {
      textIndex = textIndex - wordIndex + 1;
      wordIndex = 0;
    }
  }
  if (result.length > 0) {
    return result;
  }
  return -1;
}

console.log(searchWord(text, word));

[64] 비교할 필요가 없는 문자열은 건너 뛰고 고속으로 검색하는 'KMP' 알고리즘

KMP 알고리즘에서는 검색할 부분의 문자열이 불이치한 위치와, 부분 문자열의 정보를 바탕으로 다음 비교 위치를 구한다.

const text = "ABCABCDA";
const word = "ABCD";

const createPattern = (word) => {
  const patternTable = [0];
  let prefixIndex = 0;
  let suffixIndex = 1;

  while (suffixIndex < word.length) {
    if (word[prefixIndex] === word[suffixIndex]) {
      patternTable[suffixIndex] = prefixIndex + 1;
      suffixIndex++;
      prefixIndex++;
    } else if (prefixIndex === 0) {
      patternTable[suffixIndex] = 0;
      suffixIndex++;
    } else {
      prefixIndex = patternTable[prefixIndex - 1];
    }
  }
  return patternTable;
}
const KMPSearch = (text, word) => {
  if (word.length === 0) {
    return 0;
  }
  let textIndex = 0;
  let wordIndex = 0;
  const patternTable = createPattern(word);
  while (textIndex < text.length) {
    if (text[textIndex] === word[wordIndex]) {
      if (wordIndex === word.length - 1) {
        return textIndex - word.length + 1;
      }
      wordIndex++;
      textIndex++;
    } else if (wordIndex > 0) {
      wordIndex = patternTable[wordIndex - 1];
    } else {
      wordIndex = 0;
      textIndex++;
    }
  }
  return -1;
}
console.log(KMPSearch(text, word))

[65] 문자열을 끝에서부터 검색하는 'BM' 알고리즘

BM 알고리즘은 검색할 문자열을 끝에서부터 비교하는 특징이 있다.

const text = "ABCFABCDF";
const word = "ABCD";

const BMSearch = (text, word) => {
  let textCursor;
  let wordCursor;
  let textLen = text.length;
  let wordLen = word.length;

  let skip = new Map();
  for (let i of text) {
    skip.set(i, wordLen);
  }
  for (textCursor = 0; textCursor < wordLen; textCursor++) {
    if (skip.has(word[textCursor])) {
      skip.set(word[textCursor], wordLen - textCursor - 1);
    }
  }
  while (textCursor < textLen) {
    wordCursor = wordLen - 1;
    while (text[textCursor] == word[wordCursor]) {
      if (wordCursor == 0) {
        return textCursor;
      }
      wordCursor--;
      textCursor--;
    }
    textCursor += Math.max(skip.get(text[textCursor]), wordLen - wordCursor);
  }
  return -1;
}
console.log(BMSearch(text, word));