정렬이란?

정렬 알고리즘은 컬렉션의 항목을 재배열하는 과정을 의미합니다.

예를들어 숫자를 정렬하거나 알파벳을 정렬하는 것입니다.

왜 정렬을 배워야할까? 🤔

• 정렬은 프로그래밍에서 정말 흔하게 사용되고 알아두면 유용하다.
• 정렬하는 기술은 많이 존재하고 각 기술마다 장단점이 존재한다.

내장 자바스크립트 정렬 sort()

자바스크립트에는 내장 정렬 함수가 있습니다. 하지만 동작 사용 방법에대해서 알아둘 필요가 있는데요..
MDN에서 sort()를 살펴보면

기본 정렬 순서는 문자열 유니코드 코드 포인트에 따른다.
...
compareFunction이 제공되지 않으면 요소를 문자열로 변환하고 유니 코드 코드 포인트 순서로 문자열을 비교하여 정렬됩니다. 예를 들어 "바나나"는 "체리"앞에옵니다. 숫자 정렬에서는 9가 80보다 앞에 오지만 숫자는 문자열로 변환되기 때문에 "80"은 유니 코드 순서에서 "9"앞에옵니다.

아무것도 입력하지 않고 .sort()를 입력하면 원하지 않는 결과가 나올거라는 것을 알 수 있습니다...

sort() 사용 방법

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

이 비교함수에 어떻게 정렬할것인지 정의해준다.

비교 함수는 기본적으로 a와 b 라는 2개 요소의 쌍이고, return 값에 의해서 정렬 순서를 결정한다.

만약 음수이면, a가 b 앞에 오게된다.

양수이면 a가 b 뒤에 오게된다.

0을 반환하면 자바스크립는 a와 b를 동일하게 취급한다.

예를 들어, compareNumbers라는 비교함수를 정의하고 sort()메소드에 인자로 던져보겠습니다.

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

[ 6, 5, 15, 10, 11].sort(compareNumbers);
// 출력 : [ 5, 6, 10, 11, 15] 

버블 정렬

이제 버블 정렬에 대해서 알아보도록 하겠습니다.
버블 정렬은 흔하게 쓰이거나 효율적인 코드는 아니지만 쓰이는 곳이 있기는 합니다. 그리고 다양한 정렬 방법중에 하나이고 다른 정렬들이 얼마나 효율적인지 알기위해서는 배워둘 가치가 있다고 생각합니다.

버블 정렬의 개념은 배열을 가장 작은 숫자에서 가장 큰 숫자순으로 정렬해주는 것입니다. 즉 오름차순이면 큰 숫자가 한번에 하나씩 뒤로 이동을 하는 형태이다. (영어로 'bubble up'의 의미는 '거품을 내다.' 라는 뜻입니다. 거품이 점점 커지는 것을 연상하면 될것같네요.)

버블 정렬에서는 swap과 반복이 중요합니다!

배열을 예로 들어 보겠습니다.

[5, 3, 4, 1, 2] 라는 배열이 있다고 가정하겠습니다.
첫번째 두번째 즉, 5와 3을 비교해서 큰 숫자가 뒤로가게 됩니다.
[3, 5, 4, 1, 2]에서 두번째 세번째 즉, 5와 4를 비교합니다.
이런식으로 두개 요소를 비교 및 swap하면서 정렬이 될때까지 이 과정을 반복하게 됩니다.

버블 정렬의 Big O

일반적으로는 O(n제곱) 입니다. 중첩 반복문으로 구현을 할 수 있기 때문입니다.
하지만 조금 더 나은 방법으로는 O(n)으로 구현을 할 수 있습니다.