[알고리즘 공부] 자바스크립트 정렬(sort) #2

☘️ 정렬

정렬 정의

정렬이란 요소들을 일정한 순서대로(오름차순 or 내림차순) 열거하는 알고리즘이다.

 

정렬 방식
삽입 정렬
선택 정렬
버블 정렬
머지 정렬
힙 정렬
퀵 정렬
등。。。 

 

버블 정렬

버블 정렬은 인접한 두 요소의 크기를 비교하여, 자리를 교환하면서 정렬하는 방식이다.

 

예) 오름차순 정렬

6과 4를 비교했을 때, 앞에 있는 6이 더 크기 때문에 자리를 교환한다.

 

다음으로 6과 1을 비교했을 때, 앞에 있는 6이 더 크기 때문에 자리를 교환한다.

 

다음으로 6과 2를 비교했을 때, 앞에 있는 6이 더 크기 때문에 자리를 교환한다.

 

6과 8을 비교했을 때, 정렬 순서가 맞기 때문에 자리를 교환하지 않는다.

(첫번째 순회 완료)

 

첫 번째 순회를 완료했다. 그러면 맨 끝에 있는 8은 정렬이 완료 된 것이다.

이를 계속 반복하여

 

(두번째 순회 완료)

 

(세번째 순회 완료)

 

(네번째 순회 완료)

 

버블 정렬은 인접한 두 요소를 비교하여,

배열의 길이-1 만큼 순회하면서 정렬을 수행하는 방식이다.

그래서 O(n^2) 시간 복잡도를 가진다.

 

선택 정렬

선택 정렬은 선택한 요소와 나머지 요소 중에서 가장 크거나 작은 요소를 교환하는 방식이다.

 

예) 오름차순 정렬

오름차순 정렬이기 때문에, 선택한 요소 7과 나머지 요소 중에서 가장 작은 요소 1을 교환한다.

 

그러면 1은 제자리를 찾게 되었다.

(첫번째 순회 완료)

 

이를 계속 반복하여

 

(두번째 순회 완료)

 

(세번째 순회 완료)

 

(네번째 순회 완료)

 

이렇게 선택 정렬은 선택한 요소끼리 교환하여, 

배열의 길이-1 만큼 순회하면서 정렬을 수행하는 방식이다.

그래서 O(n^2) 시간 복잡도를 가진다.

 

삽입 정렬

삽입 정렬은 선택한 요소를 앞과 비교하여 삽입 할 위치를 찾아 요소를 삽입하는 방식이다.

참고로 삽입 정렬은 두번째 요소부터 시작한다.

 

예) 오름차순 정렬

두번째 요소인 4부터 시작해서, 4가 7보다 작기 때문에 7 앞으로 4를 삽입한다.

(첫번째 순회 완료)

 

이를 계속 반복하여

 

5는 7보다 작기 때문에, 7 앞으로 5를 삽입한다.

 

5는 4보다 크기 때문에, 알맞은 자리라서 삽입할 필요가 없다.

(두번째 순회 완료)

 

1은 7보다 작기 때문에, 7 앞으로 1을 삽입한다.

 

1은 5보다 작기 때문에, 5 앞으로 1을 삽입한다.

 

1은 4보다 작기 때문에, 4 앞으로 1을 삽입한다.

(세번째 순회 완료)

 

(네번째 순회 완료)

 

삽입 정렬은 요소를 알맞은 위치로 삽입하며,

배열의 길이-1 만큼 순회하면서 정렬을 수행하는 방식이다.

그래서 O(n^2) 시간 복잡도를 가진다.

 

이는 복잡하지만, 어느 정도 정렬되어 있을 때 사용하면 매우 빠르다.

 

합병 정렬

합병 정렬은 분할 정복 알고리즘을 사용한 정렬 방식이다.

최선과 최악의 경우가 같은 안정적인 정렬 알고리즘으로 O(n log n) 시간 복잡도를 가진다.

분할 정복
문제를 작은 2개의 문제로 분리하고
더 이상 분리가 불가능 할 때 처리한 후, 합치는 전략

 

합병 정렬

 

퀵 정렬

퀵 정렬은 분할 정복 알고리즘을 사용한 정렬 알고리즘이다.

 

이름부터 빠른 정렬 방식이라는 것을 알 수 있지만,

최악의 경우 O(n^2) 시간 복잡도가 소요되고

평균 O(n log n) 시간 복잡도가 소요되는 불안정 정렬이다.

 

예) 오름차순 정렬

5를 pivot 으로 설정하고, 양 끝을 low 와 high 로 설정한다.

low 는 pivot 보다 작은 수, high 는 pivot 보다 큰 수이다.

low 과 high 모두 적합하기 때문에 옆으로 이동한다.

 

low 는 pivot 보다 크고, high 는 pivot 보다 작아,

둘을 서로 교환해준다.

 

low 과 high 각각 pivot 보다 작고, 크기 때문에 옆으로 이동한다.

 

low 는 pivot 보다 크고, high 는 pivot 보다 작아,

둘을 서로 교환해준다.

 

그러면 high 와 low 가 역전되는 순간이 오게 되는데

이 때 pivot 을 둘 사이로 옮겨준다.

 

그러면 pivot 을 기준으로 왼쪽은 pivot 보다 작은 값, 오른쪽은 pivot 보다 큰 값이 배치된다.

 

기존 pivot 이었던 5를 기준으로 다시 새로운 pivot을 설정하여 위에 했던 과정을 계속 반복하여 정렬한다.

 

자바스크립트에서 정렬 사용

자바스크립트에서 정렬을 사용하는 방법은 내장되어 있는 sort() 함수를 사용한다.

 

const arr = [5, 8, 1, 4, 10, 2];

// 오름차순 정렬
arr.sort((a, b) => a - b);
console.log(arr);

// 내림차순 정렬
arr.sort((a, b) => b - a);
console.log(arr);

 

결과

 

---

 

해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)

코딩테스트 광탈 방지 A to Z : JavaScript