[Algorithm] ์ •๋ ฌ (Sorting)

task11ยท2022๋…„ 2์›” 28์ผ
0

์•Œ๊ณ ๋ฆฌ์ฆ˜๋ฝ€๊ฐœ๊ธฐ

๋ชฉ๋ก ๋ณด๊ธฐ
8/20

๐Ÿ’ก ๋ชจ๋“  ์ •๋ ฌ์˜ ๊ธฐ๋ฒ•์„ ์ดํ•ดํ•˜์—ฌ ์†์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์ด ๋ชฉํ‘œ

๊ฐœ์š” ๐Ÿ›ซ


์ •๋ ฌ(Sorting)์ด๋ž€ ๋ฐฐ์—ด ๋‚ด ์›์†Œ๋“ค์„ ์ผ์ •ํ•œ ์ˆœ์„œ๋Œ€๋กœ ์—ด๊ฑฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

๋Œ€ํ‘œ ์ •๋ ฌ ๊ธฐ๋ฒ• :

  • ๋ฒ„๋ธ” ์ •๋ ฌ(Bubble Sort)
  • ์„ ํƒ ์ •๋ ฌ(Selection Sort)
  • ์‚ฝ์ž… ์ •๋ ฌ(Insertion Sort)
  • ํ•ฉ๋ณ‘ ์ •๋ ฌ(Merge Sort)
  • ํ€ต ์ •๋ ฌ(Quick Sort)

ํ•™์Šต ๋‚ด์šฉ ๐Ÿ“–


๋ฒ„๋ธ” ์ •๋ ฌ(Bubble Sort)

์„œ๋กœ ์ธ์ ‘ํ•œ ๋‘ ์›์†Œ๋ฅผ ๋น„๊ตํ•˜๋ฉด์„œ ์ •๋ ฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n^2)

๋™์ž‘ ์›๋ฆฌ

๊ฐ€๊นŒ์šด ๋‘ ์ˆ˜๋ฅผ ๋น„๊ตํ•ด ํฐ ์ˆ˜์˜ ์ธ๋ฑ์Šค๋ฅผ ๋’ค๋กœ ๋ฏธ๋ค„์คŒ.

๋ฒ„๋ธ” ์ •๋ ฌ ๊ตฌํ˜„ (1)

๊ฐ€์žฅ ๋‹จ์ˆœํ•˜๊ฒŒ ๊ตฌํ˜„ํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™์ด ๋œ๋‹ค.

function bubbleSort(arr) {

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

let swap = function (arr, idx_1, idx_2) {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
}


console.log(bubbleSort([6, 5, 1, 3, 2])); // [1,2,3,5,6]

๋ฒ„๋ธ” ์ •๋ ฌ ๊ตฌํ˜„ (2)

์ธ๋ฑ์Šค ์กฐ์ •์œผ๋กœ ์ตœ์ ํ™” ( i = step ์ˆ˜ = ์ •๋ ฌ๋œ ๊ฐœ์ˆ˜์ด๋ฏ€๋กœ ๋‹ค์Œ step์—์„œ ๋Œ์ง€ ์•Š์•„๋„ ๋œ๋‹ค. )

function bubbleSort(arr) {

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

let swap = function (arr, idx_1, idx_2) {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
}


console.log(bubbleSort([6, 5, 1, 3, 2])); // [1,2,3,5,6]

๋ฒ„๋ธ” ์ •๋ ฌ ๊ตฌํ˜„ (3)

์ธ๋ฑ์Šค ์กฐ์ • ๋ฐ swapped flag๋ฅผ ํ†ตํ•ด step์— swap ์‹œํ‚ฌ ์ˆ˜๊ฐ€ ์—†์œผ๋ฉด ์ •๋ ฌ์„ ๋ฉˆ์ถ˜๋‹ค. (swap์„ ์•ˆํ•œ๋‹ค = ์ •๋ ฌ ๋๋‹ค)

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

let swap = function (arr, idx_1, idx_2) {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
}


console.log(bubbleSort([6, 5, 1, 3, 2])); // [1,2,3,5,6]

๋ฒ„๋ธ” ์ •๋ ฌ ๊ตฌํ˜„ (4) ๐Ÿ‘๐Ÿฝ

์ตœ์ข… ๋ฆฌํŽ™ํ† ๋ง ๋ฒ„์ „, ๋ฒ„๋ธ” ์ •๋ ฌ์˜ ์˜ค๋ฆ„์ฐจ์ˆœ ๋‚ด๋ฆผ์ฐจ์ˆœ์„ ๊ณ ์ฐจํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•ด ๊ตฌํ˜„ํ–ˆ๋‹ค.

const swap = (arr, idx_1, idx_2) => {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

const ascending = (x, y) => {
  return x > y;
};

const descending = (x, y) => {
  return x < y;
};

const bubbleSort = (arr, compare) => {
  let isSwapped;
  for (let i = 0; i < arr.length - 1; i++) {
    isSwapped = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (compare(arr[j], arr[j + 1])) {
        swap(arr, j, j + 1);
        isSwapped = true;
      }
    }
    if (!isSwapped) break;
  }
};

input = [6, 1, 4, 5, 2, 3];

bubbleSort(input, ascending)

console.log(input);

์„ ํƒ ์ •๋ ฌ(Selection Sort)

์ตœ์†Ÿ๊ฐ’์„ ์ฐพ์•„ ๋ฐ์ดํ„ฐ์˜ ๊ฐ€์žฅ ์•ž์œผ๋กœ ์ด๋™์‹œํ‚ค๋Š” ๋ฐฉ์‹์„ ๋ฐ˜๋ณตํ•˜๋Š” ์ •๋ ฌ

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n^2)

๋™์ž‘ ์›๋ฆฌ

๋งจ ์•ž์˜ ์ธ๋ฑ์Šค ๋ถ€ํ„ฐ ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ์•„์„œ swapํ•ด์คŒ

์„ ํƒ ์ •๋ ฌ ๊ตฌํ˜„ ๐Ÿ‘๐Ÿฝ

์ตœ์ข… ๋ฆฌํŽ™ํ† ๋ง ๋ฒ„์ „, ์„ ํƒ ์ •๋ ฌ์˜ ์˜ค๋ฆ„์ฐจ์ˆœ ๋‚ด๋ฆผ์ฐจ์ˆœ์„ ๊ณ ์ฐจํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•ด ๊ตฌํ˜„ํ–ˆ๋‹ค. ( swap ํ•จ์ˆ˜์˜ ๊ต์ฒด๊ฐ€ i๋ฒˆ ์ด๋ฃจ์–ด์ง )

const swap = (arr, idx_1, idx_2) => {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

const ascending = (x, y) => {
  return x > y;
};

const descending = (x, y) => {
  return x < y;
};

const selectionSort = (arr, compare) => {
  let minIdx;
  for (let i = 0; i < arr.length - 1; i++) {
    minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (compare(arr[minIdx], arr[j])) minIdx = j;
    }
    swap(arr, i, minIdx);
  }
};

input = [6, 1, 4, 5, 2, 3, 12, 7, 20, 23, 18];

selectionSort(input, ascending);

console.log(input);

์‚ฝ์ž… ์ •๋ ฌ(Insertion Sort)

์ด๋ฏธ ์ •๋ ฌ๋œ ์˜์—ญ๊ณผ ๋น„๊ตํ•˜๋ฉด์„œ ์ž์‹ ์˜ ์œ„์น˜๋ฅผ ์ฐพ์•„ ์š”์†Œ๋ฅผ ์‚ฝ์ž…ํ•˜๋ฉฐ ์ •๋ ฌ

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n^2)

๋™์ž‘ ์›๋ฆฌ

๋‘ ๋ฒˆ์งธ ์ธ๋ฑ์Šค ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ์•ž์˜ ์ธ๋ฑ์Šค ์š”์†Œ์˜ ๊ฐ’๋ณด๋‹ค ์ž‘์œผ๋ฉด shiftํ•˜๊ณ  ๊ฐ’์„ ๋„ฃ๋Š”๋‹ค. ์ด ๊ฒƒ์„ ๋ฐ˜๋ณตํ•˜๋Š”๊ฒŒ ์‚ฝ์ž… ์ •๋ ฌ

์‚ฝ์ž… ์ •๋ ฌ ๊ตฌํ˜„ ๐Ÿ‘๐Ÿฝ

for break ์กฐ๊ฑด : ์ •๋ ฌ๋˜์–ด์žˆ๋Š” ์š”์†Œ๋“ค๋ณด๋‹ค ํฌ๊ธฐ๊ฐ€ ํฌ๋ฉด ๋ฉˆ์ถค (์˜ค๋ฆ„์ฐจ์ˆœ)
์ •๋ ฌ๋˜์–ด์žˆ๋Š” ์š”์†Œ๋“ค๋ณด๋‹ค ํฌ๊ธฐ๊ฐ€ ์ž‘์œผ๋ฉด ๋ฉˆ์ถค (๋‚ด๋ฆผ์ฐจ์ˆœ)

const swap = (arr, idx_1, idx_2) => {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

const ascending = (x, y) => {
  return x > y;
};

const descending = (x, y) => {
  return x < y;
};

const insertionSort = (arr, compare) => {
  for (let i = 1; i < arr.length; i++) {
    let tmp = arr[i];
    let j;
    for (j = i - 1; j >= 0; j--) {
      arr[j + 1] = arr[j];
      if (compare(tmp, arr[j])) {
        break;
      }
    }
    arr[j + 1] = tmp;
  }
};

input = [6, 1, 4, 5, 2, 3, 12, 7, 20, 23, 18];

insertionSort(input, ascending);

console.log(input);

ํ•ฉ๋ณ‘ ์ •๋ ฌ(Merge Sort)

ํ•˜๋‚˜์˜ ๋ฐฐ์—ด์„ ๋‘ ๊ฐœ์˜ ๊ท ๋“ฑํ•œ ํฌ๊ธฐ๋กœ ๋ถ„ํ• ํ•˜๊ณ , ๋ถ€๋ถ„ ์ •๋ ฌํ•œ ๋’ค์— ํ•ฉ์น˜๋ฉด์„œ ์ „์ฒด๋ฅผ ์ •๋ ฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n log n)

๋™์ž‘ ์›๋ฆฌ

๋ฐฐ์—ด์˜ length๊ฐ€ 1์ผ ๋•Œ ๊นŒ์ง€ ๋ถ„ํ•  ํ•œ ํ›„ ๋ณ‘ํ•ฉํ•˜๋ฉฐ ํฌ๊ธฐ ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.

ํ•ฉ๋ณ‘ ์ •๋ ฌ ๊ตฌํ˜„ ๐Ÿ‘๐Ÿฝ

n-way ํ•ฉ๋ณ‘ ์ •๋ ฌ์˜ ๊ฐœ๋…์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  1. ์ •๋ ฌ๋˜์ง€ ์•Š์€ ๋ฐฐ์—ด์„ ๊ฐ๊ฐ ํ•˜๋‚˜์˜ ์›์†Œ๋งŒ ํฌํ•จํ•˜๋Š” n๊ฐœ์˜ ๋ถ€๋ถ„๋ฆฌ์ŠคํŠธ๋กœ ๋ถ„ํ• ํ•œ๋‹ค. (ํ•˜๋‚˜์˜ ์š”์†Œ๋งŒ ์žˆ๋Š” ๋ฐฐ์—ด์€ ์ •๋ ฌ๋œ ๊ฒƒ๊ณผ ๊ฐ™์œผ๋ฏ€๋กœ)

  2. ๋ถ€๋ถ„๋ฆฌ์ŠคํŠธ๊ฐ€ ํ•˜๋‚˜๋งŒ ๋‚จ์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•ด์„œ ๋ณ‘ํ•ฉํ•˜๋ฉฐ ์ •๋ ฌ๋œ ๋ถ€๋ถ„๋ฆฌ์ŠคํŠธ๋ฅผ ์ƒ์„ฑํ•œ๋‹ค. ๋งˆ์ง€๋ง‰ ๋‚จ์€ ๋ถ€๋ถ„๋ฆฌ์ŠคํŠธ๊ฐ€ ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ์ด๋‹ค.

ํ•˜ํ–ฅ์‹ 2-way ํ•ฉ๋ณ‘ ์ •๋ ฌ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ž‘๋™ํ•œ๋‹ค.

์กฐ๊ฑด๋ถ€ : ๋ฐฐ์—ด ๊ธธ์ด๊ฐ€ 1 ์ดํ•˜์ด๋ฉด ์ด๋ฏธ ์ •๋ ฌ๋œ ๊ฒƒ์œผ๋กœ ๋ณธ๋‹ค.

  1. ๋ถ„ํ• (divide): ์ •๋ ฌ๋˜์ง€ ์•Š์€ ๋ฐฐ์—ด ์ ˆ๋ฐ˜์œผ๋กœ ์ž˜๋ผ(๋ฐ˜์˜ฌ๋ฆผ-toFixed) ๋น„์Šทํ•œ ํฌ๊ธฐ์˜ ๋‘ ๋ถ€๋ถ„ ๋ฐฐ์—ด๋กœ ๋‚˜๋ˆˆ๋‹ค.
  2. ์ •๋ณต(conquer): ๊ฐ ๋ถ€๋ถ„ ๋ฐฐ์—ด์„ ์žฌ๊ท€์ ์œผ๋กœ ํ•ฉ๋ณ‘ ์ •๋ ฌ์„ ์ด์šฉํ•ด ์ •๋ ฌํ•œ๋‹ค.
  3. ๊ฒฐํ•ฉ(combine): ๋‘ ๋ฐฐ์—ด์„ ๋‹ค์‹œ ํ•˜๋‚˜์˜ ์ •๋ ฌ๋œ ๋ฐฐ์—ด๋กœ ํ•ฉ๋ณ‘ํ•œ๋‹ค.
const ascending = (x, y) => {
  return x > y;
};

const descending = (x, y) => {
  return x < y;
};

const mergeSort = (arr, compare) => {
  if (arr.length === 1) return arr;

  let m = (arr.length / 2).toFixed(0);
  let left = mergeSort(arr.slice(0, m), compare);
  let right = mergeSort(arr.slice(m), compare);

  let i = 0;
  j = 0;
  k = 0;
  while (i < left.length && j < right.length) {
    arr[k++] = compare(left[i], right[j]) ? right[j++] : left[i++];
  }

  while (i < left.length) arr[k++] = left[i++];
  while (j < right.length) arr[k++] = right[j++];

  return arr;
};



input = [6, 1, 4, 5, 2, 3, 12, 7, 20, 23, 18];

mergeSort(input, ascending);

console.log(input);

ํ€ต ์ •๋ ฌ(Quick Sort)

ํŠน์ • ๊ฐ’(pivot)์„ ๊ธฐ์ค€์œผ๋กœ ์‚ผ๊ณ  ํฐ ์ˆซ์ž์™€ ์ž‘์€ ์ˆซ์ž๋ฅผ ๋ถ„ํ• ํ•˜์—ฌ ์ •๋ ฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n log n)

๋™์ž‘ ์›๋ฆฌ

ํ€ต ์ •๋ ฌ์€ ๋ถ„ํ•  ์ •๋ณต(divide and conquer) ๋ฐฉ๋ฒ•์„ ํ†ตํ•ด ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•œ๋‹ค.

ํ€ต ์ •๋ ฌ ๊ตฌํ˜„ ๐Ÿ‘๐Ÿฝ

ํ€ต ์ •๋ ฌ๋„ ๋ถ„ํ• /์ •๋ณต ๋ฐฉ๋ฒ•์„ ํ†ตํ•ด ๊ตฌํ˜„ํ•œ๋‹ค. ์žฌ๊ท€

const swap = (arr, idx_1, idx_2) => {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

const ascending = (x, y) => {
  return x > y;
};

const descending = (x, y) => {
  return x < y;
};

const quickSort = (arr, compare, s = 0, e = arr.length - 1) => {
  let start = s;
  let pivot = arr[e];

  for (let i = s; i <= e; i++) {
    if (compare(pivot, arr[i])) {
      swap(arr, start, i);
      start++;
    }
  }
  swap(arr, start, e);

  if (start - 1 > s) {
    quickSort(arr, compare, s, start - 1);
  }
  if (start + 1 < e) {
    quickSort(arr, compare, start + 1, e);
  }

};

input = [6, 1, 4, 5, 2, 3, 12, 7, 20, 23, 18];

quickSort(input, ascending);

console.log(input);

Review ๐Ÿ’ก

์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋‹ค์–‘ํ•œ ๊ธฐ๋ฒ•๋“ค์„ ์˜ˆ์ œ๋ฅผ ํ†ตํ•ด ์ดํ•ดํ•ด ๋ณด์•˜๋‹ค.

ํ•ฉ๋ณ‘์ •๋ ฌ๊ณผ ํ€ต ์ •๋ ฌ์€ ๋ถ„ํ• ์ •๋ณต ์ด๋ก (์žฌ๊ท€)์„ ์กฐ๊ธˆ ๋” ์ดํ•ดํ•ด์•ผ ํ•œ๋ฒˆ์— ์ดํ•ด๊ฐ€ ๊ฐ€๋Šฅํ•  ๊ฒƒ ๊ฐ™๋‹ค.

0๊ฐœ์˜ ๋Œ“๊ธ€