알고리즘 & 자료구조 8주차 스터디 [sort]

May 27, 2023 🐰

🤯 오늘 배울 개념은 SortSort!!!!

재밌는것. : bubble pop, insertion, selection, 앞으로 배울 sorting들의 실시간 변화를 볼 수 있다.

• sort Algorithmes는 무엇일까?
  정렬 알고리즘은 컬렉션의 항목을 재배열하는 과정이다. 영화, 데이터, 객체, 연도, 국내 수익 등등에 사용할 수 있다.

🔑 Bubble Sort

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
• 선택 정렬과 기본 개념이 유사하다.
• 배열을 가장 작은 숫자에서 가장 큰 숫자순으로, 오름차순을하면 더 큰 숫자가 한번에 하나씩 뒤로 이동하는 것이다.

visualgo.net-> Bubble sorting

👩🏻‍🌾 Bubble Sort function

function swap(arr, idx1, idx2) {
  var temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

let a = [5, 4, 3, 2, 1];
var noSwaps;
for (let i = a.length; i > 0; i--) {
  noSwaps = true;
  for (let j = 0; j < i - 1; j++) {
    if (a[j] > a[j + 1]) {
      swap(a, j, j + 1);
      noSwaps = false;
    }
  }
  if (noSwaps) break;
}

console.log(a);

코드를 보면 항상 반복이 끝날 때까지 for문을 다 돌렸지만 noSwaps 변수를 넣어 swap이 끝나면 바로 return 해서 메모리를 줄이는 Tip

• 버블 정렬(bubble sort)의 시간복잡도
  T(n) = O(n^2)

🔑 Selection Sort

• 선택 정렬은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
• 주어진 리스트 중에 최소값을 찾는다.
• 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체

👩🏻‍🌾 Insertion Sort function

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    var min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }
    console.log(arr);

    var temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
    console.log(arr);

  }
  return arr;
}

let r = selectionSort([34, 22, 10, 19, 17]);
console.log(r);

🔑 Insertion Sort

삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다

👩🏻‍🌾 Insertion Sort function

function insertionSort(arr) {
  var currentVal;
  for (var i = 1; i < arr.length; i++) {
    currentVal = arr[i];
    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currentVal;
  }
  return arr;
}

insertionSort([2, 1, 9, 76, 4]);

🔑 Big O of sorting Algorithms

🔑 Review

• bubble, selection Sort들은 익숙해서 이해하기 쉬웠지만 insertion sort가 처음에 이해가 되지않아 어려웠다.
• 앞으로 계속해서 다른 정렬들도 배우겠지만 문제에 맞게 시간이 절약되는 정렬을 그때마다 사용하면 좋을거 같다.

💻 Source

• ✏️ Best JavaScript Data Structures & Algorithms Course by Udemy, last updated January 2022, accessed April 5, 2023 - https://www.udemy.com/
• ⌨️ reference gitHub - https://github.com/seunghyun0522/JavaScript-Algorizms-Data-Structure