LoginGustBookCategories
Categories
Algorithms

Introduce Sorting Algorithms

thumbnailCreatehb21·2022년 01월 12일 15:43

https://www.crio.do/blog/content/images/2021/04/Sorting-Algorithms.png


What is sorting ?

정렬 알고리즘이라고 하면, 모여 있는 요소들을 재배치하는 과정을 의미한다. 예를 들면 스트링을 정렬할 수도 있고 문장 안에 들어있는 개별 글자들을 정렬할 수도 있음. 보통은 배열을 가지고 정렬 작업을 하게 된다. 추후에는 리스트나 트리 같은 다른 데이터 구조들에 대해서도 다뤄볼 것이다. 그렇지만 지금 우선은 배열에 집중해보자.

배열로 된 데이터가 있다고 가정해보자. 우리는 순환하면서 순서가 재배치된 배열을 출력하는 함수를 작성해야 한다.
  • 작은 숫자에서 큰 숫자로, 또는 그 반대로 정렬
  • 이름을 알파벳 순서대로 정렬
  • 객체로 구성된 데이터를 정렬(예를 들어, 영화에 관한 데이터를 개봉 년도에 따라 정렬하거나 수익에 따라 정렬하는 방식, 혹은 이 둘을 합쳐서 정렬해야 하는 방식)
기억해야 할 점은 무엇에 대해 정렬하는지와 어떻게 비교하는가는 알고리즘 상에서는 중요하지 않다는 것이다. 알고리즘은 이런 것들에 영향을 받지 않는다.


간단한 예제

숫자를 작은 수에서부터 큰 수로 정렬하는 함수를 만들어보자.

function sort(arr) {
	return arr
}

사실 위와 같은 문제를 풀어내는 알고리즘은 수십가지이다. 또한 이러한 수십개의 방법들중에서 더 나은 방법이 있을 터이고, 또한 특정한 알고리즘은 특정한 경우에 대해서만 정말 좋다. 우리는 이처럼 수많은 알고리즘들을 어떻게 활용할 수 있을까를 학습해보도록 하자.

Why do we need to learn this ?

수십개의 알고리즘들이 많이 있고, 우리는 그 중에 몇가지를 배울것이다. 하지만 왜 우리는 정렬 알고리즘을 알아야할까
  • 정렬은 프로그래밍에서 정말 정말 자주 쓰인다.
  • 정렬에는 많은 알고리즘이 있고, 각 알고리즘마다 장단점이 있다. 일부 알고리즘은 확실히 다른 알고리즘보다 빠르지만, 특정한 상황 속에서는 오히려 좋지 않은 경우가 있다. 이는 알아둘 필요가 있다.
  • 면접에 자주 나온다. 정말 많은 접근법이 있고, 제대로 된 비판적 사고를 할 줄 알아야 하는 부분이기 때문.



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

기본 내장 정렬 메소드(Array.sort( ))는 comparator 함수를 사용할 수 있는데 이걸 가지고 자바스크립트에게 우리가 어떻게 정렬하고자 하는지를 말해줄 수 있다.

이 함수에는 두 가지 요소를 넣을 수 있다. 이 두가지 요소가 a와 b라고 하고, 자바스크립트에게 우리가 원하는 것에 대해 정렬 명령을 내린다. 만약에 그 결과가 음수값이라면 자바스크립트는 a가 b보다 항상 먼저 오게끔 한다. 반대로 양수값이라면 b가 a보다 먼저 온다. 만약 그 결과가 0이라면 a와 b를 같은 것으로 취급하고 같이 두게 된다.
  • 예시
// 크기에 따라 숫자를 정렬
function numberCampare(num1, num2) {
	return num1 - num2;
}

[6, 4, 15, 10].sort(numberCampare);
// [4, 6, 10, 15]

// 스트링의 길이에 따라 정렬
function compareByLen(str1, str2) {
	return str1.length - str2.length;
}

['Steel', 'Colt', 'Data Structures', 'Algorithms'].sort(compareByLen)
// ['Colt', 'Steel', 'Algorithms', 'Data Structures']

위와 같이 따로 comparator 함수를 만들어서 sort에 전달해줘도 되지만, 화살표 함수를 이용해 sort() 내에서 바로 코드를 작성해도 된다.

// 예시
let sortedHeroes = heroes.sort((a, b) => a.hourlyPayment - b.hourlyPayment);

여기까지는 정렬 알고리즘에 대한 소개와 자바스크립트의 내장 정렬 메소드를 comparator 함수를 정의해서 사용할 수 있는 방법에 대해 다루었다.다음 포스트에서부터는 직접 정렬 알고리즘을 짜는 다양한 방식에 대해서 다루도록 한다.
# algorithms# sorting
© 2021 Createhb21.