정렬 알고리즘

정렬 알고리즘이 무엇인가?
간단히 말하면 배열을 원하는 방식으로 재배열하는 알고리즘 입니다.
예를 들면 배열을 입력받아 오름차순 혹은 내림차순으로 정렬하는 것을 말할 수 있습니다.

왜 배워야할까요?
1. 정렬이 프로그래밍에서 정말 흔하게 쓰이기 때문입니다.
2. 정렬하는 방법은 많고 각각 장단점이 있기 때문에 상황에 맞게 써야하기 때문에 알아야 합니다.

기본 내장 자바스크립트 정렬

sort() 메서드는 배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환합니다. 정렬은 stable sort가 아닐 수 있습니다. 기본 정렬 순서는 문자열의 유니코드 코드 포인트를 따릅니다.

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]

기본 정렬 순서가 문자열의 유니코드 코드 포인트를 따르기 때문에 우리가 원하는 값을 받기가 어려울 수도 있습니다.

그렇지만 정렬 방식, 정렬의 기준이 되는 속성(property), 비교 대상을 실제로 지정할 수 있다면 완전히 다른 결과를 낼 수 있습니다.

내장 정렬 메소드는 선택적 비교 함수(optional comparator function)를 인자로 전달받습니다.

이 함수를 사용해서 자바스크립트에 우리가 원하는 정렬 방식을 알릴 수 있습니다.

기본적으로 이 함수는 A와 B라는 2개의 항목이 있는 구조로 작성하고요.

반환되는 값을 토대로 만들 정렬 순서를 자바스크립트에 알립니다.

MDN에서 가져온 코드 예시를 첨부하겠습니다.

const stringArray = ['Blue', 'Humpback', 'Beluga'];
const numberArray = [40, 1, 5, 200];
const numericStringArray = ['80', '9', '700'];
const mixedNumericArray = ['80', '9', '700', 40, 1, 5, 200];

function compareNumbers(a, b) {
  return a - b;
}

stringArray.join(); // 'Blue,Humpback,Beluga'
stringArray.sort(); // ['Beluga', 'Blue', 'Humpback']

numberArray.join(); // '40,1,5,200'
numberArray.sort(); // [1, 200, 40, 5]
numberArray.sort(compareNumbers); // [1, 5, 40, 200]

numericStringArray.join(); // '80,9,700'
numericStringArray.sort(); // ['700', '80', '9']
numericStringArray.sort(compareNumbers); // ['9', '80', '700']

mixedNumericArray.join(); // '80,9,700,40,1,5,200'
mixedNumericArray.sort(); // [1, 200, 40, 5, '700', '80', '9']
mixedNumericArray.sort(compareNumbers); // [1, 5, '9', 40, '80', 200, '700']
Sorting array of objects
Arrays of objects can be sorted by comparing the value of one of their properties.

const items = [
  { name: 'Edward', value: 21 },
  { name: 'Sharpe', value: 37 },
  { name: 'And', value: 45 },
  { name: 'The', value: -12 },
  { name: 'Magnetic', value: 13 },
  { name: 'Zeros', value: 37 }
];

// sort by value
items.sort((a, b) => a.value - b.value);

// sort by name
items.sort((a, b) => {
  const nameA = a.name.toUpperCase(); // ignore upper and lowercase
  const nameB = b.name.toUpperCase(); // ignore upper and lowercase
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }

  // names must be equal
  return 0;
});

버블 정렬 개요

왜 버블 정렬일까요?
버블 정렬 : 가장 큰 값을 bubble up to the top (탑으로 올려주는) 알고리즘 입니다.
동작 원리 : 배열의 0,1번은 비교해서 크기가 작은 것은 낮은 인덱스로, 큰 값은 높은 인덱스로 유지or스왑(교환)해서 동작합니다. 0번부터 마지막번까지 진행되면 다시한번 처음부터 (index 0번)부터 동작할 것 입니다. 언제까지? 스왑이 0회가 될 때까지 동작하게 되는 것이죠.

function swap(arr,idx1,idx2){
// 스왑의 예시 코드 입니다. 
	var temp = arr[idx1]; 
    // index가 낮은(값은 높은) inx1을 임시로 빼놓고
    arr[idx1] = arr[idx2]; 
    // index는 높고 값은 낮은 inx2의 값을 inx1에 저장시켜 줍니다
    arr[idx2] = temp;
    // 마지막으로 임시로 저장해놨던 inx1값(temp에 저장)을 inx2에 저장시켜줍니다
}

버블 정렬 구현

의사코드 작성

• 배열을 정렬될 때까지 반복해줄 for문 작성합니다 let i를 이용해서
• let j를 이용해서 i-1까지 배열 안에서 반복하는 for문을 작성합니다
• 만약 arr[j] > arr[j+1] 상황이면 두 값을 스왑(교환)해줍니다
• 이렇게 두개의 for문이 끝나면 정렬이 완료된 배열을 반환합니다.

코드 구현

// UNOPTIMIZED VERSION OF BUBBLE SORT
function bubbleSort(arr){
  for(var i = arr.length; i > 0; i--){
    for(var j = 0; j < i - 1; j++){
      console.log(arr, arr[j], arr[j+1]);
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;         
      }
    }
  }
  return arr;
}

// ES2015 Version
function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

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

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

버블 정렬 최적화 (빅오)

구체적인 시나리오... 이미 거의 다 정리된 배열을 정렬할때
이미 정렬이 다 됐지만 계속 (for문 let i로 지정된) 반복을 하는 것을 볼 수 있습니다. 그렇기 때문에 code에 만약 swap이 한번도 안됐으면 정렬이 완료 됐다는 것을 추가해야합니다.

빅오는 기본적으로 O(n^2)로 표현할 수 있고 최적의 상황의 경우 (이미 다 정렬된 상태) O(n)으로 나타낼 수 있습니다.

// Optimized BubbleSort with noSwaps
function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;         
      }
    }
    if(noSwaps) break;
  }
  return arr;
}

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