정렬 알고리즘에서 많이 쓰이는 유형과 sort() 원리와 콜백함수를 넣었을때의 작동 구조를 보자

참고 사이트: Tim sort에 대해 알아보자, 형님 감사합니다.

정렬 유형

정렬을 구현하는 유형도 여러가지다.

버블 정렬

매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법
가장 쉬운 정렬

• 오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장
• 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장 되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복!

기본 로직

1. 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.
2. 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
3. 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.
4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

시간복잡도

이 정렬 알고리즘은 1부터 비교를 시작하여, n-1개, n-2개,,,1개씩 비교를 반복하며, 선택 정렬과 같이 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 0(n^2)이다.
공간복잡도도 이 또한 단 하나의 배열에서만 진행하므로 0(n)이다.

소스 코드

function bubbleSort (array) {
  for (let i = 0; i < array.length; i++) {
    let swap;
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        swap = array[j];
        array[j] = array[j + 1];
        array[j + 1] = swap;
      }
    }
    // console.log(`${i}회전: ${array}`);
    if (!swap) {
      break;
    }
  }
  return array;
}
// console.log(bubbleSort([5, 4, 3, 2, 1]));

삽입 정렬

현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입

기본로직

1. 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.
2. 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.
4. 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.

시간복잡도

이 정렬 알고리즘 또한 최악의 경우(역으로 정렬되어있을 경우)엔 n-1개,n-2개 ... 1개씩 비교를 반복하여 시간복잡도는 0(n^2)이지만, 이미 정렬되어 있는 경우에는 한번씩 밖에 비교를 하지 않아 시간 복잡도는 0(n)이다.

하지만 상한을 기준으로 하는 Big-0 notation은 최악의 경우를 기준으로 평가하므로 삽입 정렬의 시간복잡도는 0(n^2)이다.
공간복잡도는 단 하나의 배열에서만 진행하므로 0(n)이다.

소스 코드

	
function insertionSort (array) {
  for (let i = 1; i < array.length; i++) {
    let cur = array[i];
    let left = i - 1;
 
    while (left >= 0 && array[left] > cur) {
      array[left + 1] = array[left];
      left--;
    }
    array[left + 1] = cur;
    // console.log(`${i}회전: ${array}`);
  }
  return array;
}
// console.log(insertionSort([5, 4, 3, 2, 1]));

힙 정렬

기본로직

시간복잡도

소스코드

병합(합병) 정렬

Divide and Conquer, 데이터들을 잘게 쪼갠 다음에 하나로 합치는 과정에서 정렬하는 방법

기본로직

1. 분할 과정의 기본 로직은 다음과 같다.
   1. 현재 배열을 반으로 쪼깬다. 배열의 시작 위치와, 종료 위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다.
   2. 이를 쪼갠 배열의 크기가 0이거나 1일때 까지 반복한다.
2. 합병 과정의 기본 로직은 다음과 같다.
   1. 두 배열 A,B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 로 가정하자.
   2. i에는 A배열의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.
   3. A[i]와 BT]를 비교한다. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장한다.
      ATi]가 더 컸다면 ATI의 값을 배열 C에 저장해주고, 1의 값을 하나 증가시켜준다.
   4. 이를 1나 i 둘중 하나가 각자 배열의 끝에 도달할 때 까지 반복한다.
   5. 끝까지 저장을 못한 배열의 값을, 순서대로 전부 다 C에 저장한다.
   6. C배열을 원래의 배열에 저장해준다.

걍 한마디로

1. 쪼개기
   1. 가장 간단한 경우로 기본 단계를 찾는다.
   2. 주어진 문제를 가능한 한 작게 줄여서 기본 단계가 되게끔 만드는 법을 찾는다.
   3. 가장 작은 단위까지 쪼갠다.
2. 합병하기
   기본 단위로 쪼개진 각 요소들을 비교하여 조건에 따라 정렬한 뒤 concat이든 뭐든 합쳐주기

시간복잡도

분할 하는 시간은 포함되지 않음, 2개씩 쪼갠 것들을 병합할 때 시간이 걸리기에 좋든 나쁘든 O(nlogn)(O(nlog₂n))로 걸린다. 즉! 데이터 분포에 영향을 덜 받는다.
하지만 쪼갤 때 어디에 담아둘 메모리가 발생하기에 '참조 지역성 원리'에 의해

소스코드

로직에서 봤듯이 병합정렬은

1. 쪼개기
2. 합병하기

이렇게 코드를 짜야한다.

function mergeSort (array) {
  if (array.length < 2) {
    return array;
  }
  const mid = Math.floor(array.length / 2);
 
  const left = array.slice(0, mid);
  const right = array.slice(mid);
 
  return merge(mergeSort(left), mergeSort(right));
 
  function merge (left, right) {
    const resultArray = [];
    let leftIndex = 0;
    let rightIndex = 0;
 
    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        resultArray.push(left[leftIndex]);
        leftIndex++;
      } else {
        resultArray.push(right[rightIndex]);
        rightIndex++;
      }
    }
    return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
  }
}
// console.log(mergeSort([5, 4, 3, 2, 1]));

퀵 정렬

기본로직

시간복잡도

소스코드

arr.sort(fuc)

• Tim sort의 원리를 가지고 있음, sort()의 기원에 대해 궁금하면 다음 벨로그 글을 보라!
• sort()의 기본값은 배열의 element들은 문자열로 취급되어, 유니코드 값 순서대로 정렬
• 소괄호 안에는 0보다 큰 값, 0보다 작은 값 0(권장x)만 리턴해야한다.
• ⭐️⭐️⭐️⭐️ 원본 수정함!! ⭐️⭐️⭐️⭐️
• 기본값

  const months = ['March', 'Jan', 'Feb', 'Dec'];
  months.sort();
  console.log(months);
  // expected output: Array ["Dec", "Feb", "Jan", "March"]
  const array1 = [1, 30, 4, 21, 100000];
  array1.sort();
  console.log(array1);
  // expected output: Array [1, 100000, 21, 30, 4]

sort() 작동 방식

()안에 함수가 들어감
함수의 파라미터로 두개의 값만 받고, 보통 a, b로 작성함
이 함수가 리턴하는 값이 0보다 작을 경우, a가 b보다 앞에 오도록 정렬
이 함수가 리턴하는 값이 0보다 클 경우, b가 a보다 앞에 오도록 정렬
만약 0을 리턴하면, a와 b의 순서를 변경하지 않음(권장x)
걍 단순하게 생각해서 a>b를 1로 두면 오름차순, a<b를 1로 두면 내림차순임

기본값을 도출하는 공식은 arr.sort((a,b) => (a > b) - (a < b));이다. 이게 어떻게 가능하냐면 맨 밑에 있으니 차근차근 보라

const arr = [2, 1, 3, 10, 1];
arr.sort()
// = arr.sort((a,b) => (a > b) - (a < b));
// [1, 1, 10, 2, 3]
const arr2 = ['banana', 'apple', 'orange']
arr2.sort()
// ['apple', 'banana', 'orange']

숫자 정렬

• 기본적으로 없으면 문자열 취급이기에 십의 자리 이상의 숫자가 있으면 파라미터를 넣어주고 숫자이고, 파라미터가 들어가면 데이터 그대로 인자로 받는다.
• 그래서 숫자 자체를 계산해버려 0보다 큰지 안큰지를 리턴해 a, b의 위치를 얻는다.

const arr = [2, 1, 3, 10, 1];
arr.sort()
// [1, 1, 10, 2, 3]
arr.sort((a, b) => a - b);
// 오름차순, [1, 1, 2, 3, 10]
arr.sort((a, b) => b - a);
// 내림차순, [10, 3, 2, 1, 1]

문자열 정렬

• 문자열은 계산이 안되기에 유니코드를 이용해 조건을 붙여 위치를 정한다.
  • 문자열끼리 대소 비교를 할 수 있는 이유는 유니코드

const arr2 = ['banana', 'apple', 'orange']
arr2.sort()
// 오름차순, ['apple', 'banana', 'orange']
arr2.sort((a, b) => {
  if (a < b) return 1;
  if (a > b) return -1;
  if (a === b) return 0;
  // return a < b ? 1 : -1;
})
// 내림차순, ['orange', 'banana', 'apple']

• 대소문자 구별함, 대문자가 유니코드 코드 포인트 순으로 앞에 오므로 대문자, ... 소문자 이렇게 반환한다. 말 드럽게 안듣는다. 그래서 만약 대소문자 구분 없이 정렬하고 싶으면 소문자나 대문자로 통일 후 정렬해야한다

let a = ['ant', 'Bug', 'cat', 'Dog']
a.sort()
// ["Bug", "Dog", "ant", "cat"]
a.sort((a, b) => {
  const upperCaseA = a.toUpperCase();
  const upperCaseB = b.toUpperCase();
  // return upperCaseA > upperCaseB ? 1 : -1;
  if (upperCaseA > upperCaseB) return 1;
  if (upperCaseA < upperCaseB) return -1;
  if (upperCaseA === upperCaseB) return 0;
});

객체 정렬

배열에 감싸진 객체도 가능 각각 key와 value를 뽑아 문자열, 숫자처럼 정렬 가능하다!

// value
const arr = [
  {name: 'banana', price: 3000}, 
  {name: 'apple', price: 1000},
  {name: 'orange', price: 500}
];
arr.sort(function(a, b) {
  return a.price - b.price;
});
/*
[
  { name: 'orange', price: 500 },
  { name: 'apple', price: 1000 },
  { name: 'banana', price: 3000 }
]
*/

➡️팁: 배열에 안감싸져있어? 고차함수와 push 조합으로 배열 만들고 하면 되지~

문제

배열타입의 데이터가 입력되고 각 요소는 문자열을 입력받는다. 각 문자열의 2번째 문자를 기준으로 정렬하라는 문제
진짜 어려웠다.
문자열 내 마음대로 정렬하기

초기 코드

1. 요소를 새로 담을 것들, 인덱스도
2. 각 요소를 돌며 slice(n)을 하여 정렬한 뒤 넣어주고
3. 넣어준 요소별로 인덱스가 붙여있으니 stirngs에 넣어주고 어쩌고,,

function solution(strings, n) {
  let newArr = [];
  let idx = [];
  strings.forEach((str, i) => {
    newArr.push(str.slice(n));
    idx.push(i);
  });
  newArr.sort();
  let veryNewArr = [];
  newArr.forEach((newStr, j) => {
    veryNewArr.push(`${strings[idx[j]].slice(0, n)}${newStr}`);
  });
  return veryNewArr
}

문제: 허무맹랑한 함정에 빠져 광명을 찾지 못하였음, sort를 1도 이해 못했음,, sort()의 기준에 대해 이해하고있음 쉬운 문젠데

답

초기 코드를 다 지우고 다시 했는데 머리가 맑아지며 다시 의사코드를 짰다.

1. sort()로 정렬하는데 기준을 잡아주기
2. 문자열도 순환되는 객체 취급을 받기에 인덱스(n)를 붙여 기준 잡아주기
3. ⭐️포인트: n번째 문자열을 비교하는데 문자열이 같을 시 sort()의 디폴트공식인 (a > b) - (a < b)을 이용하기

function solution(strings, n) {
  return strings.sort((a, b) => {
    if (a[n] > b[n]) {
      return 1;
    } else if (a[n] < b[n]) {
      return -1;
    } else {
      return (a > b) - (a < b);
    }
  });
}

참고: 왜 (a > b) - (a < b) 이게 가능? JS에선 가능
⭐️ truthy, falsy 규칙으로 인해 true == 1, false == 0으로 취급돼서 true - false는 곧 1이고 반대는 -1 이다.