자바스크립트 정렬 알고리즘 1 : 왜 정렬 알고리즘을 배워야 할까?

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

1. 정렬 알고리즘을 배워야 하는 이유

const letters = ['a', 'd', 'z', 'e', 'r', 'b'];
const basket = [2, 65, 34, 2, 1, 7, 8];

basket.sort(); // [1, 2, 2, 34, 65, 7, 8]

basket 배열에서 자바스크립트에 내장된 정렬 메소드를 사용할 경우, 우리가 원하는대로 정렬이 이루어지지 않는다. 왜 그럴까?

 

자바스크립트에 내장된 sort 메소드는 각 element를 string으로 변환한 뒤, 캐릭터코드로 치환한 후, 캐릭터코드가 낮은 순서대로 정렬하는 로직으로 이루어져 있다. 예를 들면, 숫자 65는 문자열 '65'가 된 뒤, 캐릭터코드를 찾는데 문자열 6은 캐릭터코드는 unicode로 54에 해당된다. (unicode 표)

console.log('2'.charCodeAt(0)); // 50
console.log('65'.charCodeAt(0)); // 54
console.log('34'.charCodeAt(0)); // 51
console.log('7'.charCodeAt(0)); // 55

세부적으로 보자면, '65'의 캐릭터코드는 54, '7'의 캐릭터코드는 55이기 때문에 숫자로는 7이 65보다 작은 수임에도 불구하고 정렬 순서 상 뒤쪽에 위치하는 것이다. 그러다보니 원하는대로 정렬이 되지 않을 뿐 아니라, 이 메소드를 실행하는 브라우저마다 sort 메소드의 정렬 로직이 조금씩 다를 수 있다. 

 

물론 sort 메소드에 콜백 함수를 이용해서 원하는 값을 얻을 수는 있다. 

const letters = ['a', 'd', 'z', 'e', 'r', 'b'];
const basket = [2, 65, 34, 2, 1, 7, 8];

basket.sort((a, b) => a - b); // [1, 2, 2, 7, 8, 34, 65]

숫자의 경우 a-b를 하면 오름차순으로, b-a를 하면 내림차순으로 정렬이 되지만, 만약 스페인어나 한국어 같은 문자라면 어떻게 정렬할 수 있을까? 결론적으로, 기업에서 수 많은 데이터들을 여러 방식으로 필터를 걸어 추출하고, 원하는 기준대로 정렬하는 것은 필수적인 업무인데 이를 단순히 내장된 sort 메소드에 의존해서 하기에는 정확도와 효율성을 보장할 수 없기 때문에, 다양한 정렬 방식 그리고 각 정렬 알고리즘 마다의 장단점을 정확히 알고 있어야 한다.

---

마지막으로, 정렬 알고리즘을 이해하고 직접 구현해보는 것은 무척 중요하지만, 사실 실무에서 내가 직접 로직을 구현할 일은 거의 없다고 한다. 대부분 프레임워크를 이용해서 구현하기 때문이다. 그럼에도 정렬 알고리즘이라는 주제를 배우는 이유는 아래를 이해하기 위함이다.

각 정렬 알고리즘의 시간/공간 복잡도와 장/단점(Tradeoff)를 이해하여,
어떤 상황에 어떤 정렬 알고리즘을 사용하는 것이 효율적인지를 알고 적용해야 한다.

 

각 정렬 알고리즘은 모두 제각기 필요한 용도가 다르며, 각 상황에 따라서 정렬 속도도 모두 다르다. 아래 사이트에서 이를 확인할 수 있다.

정렬 알고리즘 별 속도 차이