정렬 (Sort)

Jun 2k (Jun2)·2023년 9월 27일

CS지식 WIL cs공부 자료구조&알고리즘 정렬

자료구조&알고리즘

목록 보기

13/19

정렬

요소들을 일정한 순서대로 열거하는 알고리즘

정렬의 특징

정렬 기준은 사용자가 정하기 나름이다.
크게 비교식과 분산식 정렬로 구분한다.
대부분의 언어가 빌트인으로 제공한다.
삽입, 선택, 서블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재한다.

어떤 정렬이 제일 빠를까?

비교 시뮬레이션 사이트 : https://www.toptal.com/developers/sorting-algorithms

비교식 정렬

다른 요소와 비교를 통해 정렬하는 방식

버블 정렬

서로 인접한 두 요소를 검사하여 정렬하는 알고리즘이다. 하나씩 단계별로 비교하면서 바꾼다. O(n^2) 시간 복잡도를 가진다.

출처: 이선협 강사님 데브코스 강의자료

선택 정렬

선택적 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘이다. 사람이 정렬하는 방식과 가장 흡사하다. O(n^2) 시간 복잡도를 가진다.

출처: 이선협 강사님 데브코스 강의자료

삽입 정렬

선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘이다.
O(^2) 시간 복잡도를 가진다.

출처: 이선협 강사님 데브코스 강의자료

분산식 정렬

분할 정복 알고리즘

문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능할 때 처리한 후 합치는 전략이다. 다양한 알고리즘에 응용된다.

합병 정렬

분할 정복 알고리즘을 이용한 최선과 최악이 같기에 안정적인 정렬 알고리즘이다.
O(n log n) 시간 복잡도를 가진다.

출처: 이선협 강사님 데브코스 강의자료

퀵 정렬

분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우 O(n^2) 시간 복잡도를 가지는 최악의 경우가 존재하는 불안정 정렬이다.
O(n log n) 시간 복잡도를 가진다.
첫 번째 요소를 피벗으로 설정하여 정렬하는 과정을 반복

출처: 이선협 강사님 데브코스 강의자료

JavaScript에서의 정렬

기본적인 정렬 메서드가 존재하나 이는 ASCII 기준으로 정렬을 한다.
따라서 우리가 아는 기준을 적용하려면 내부 함수를 통해 조건을 설정해주어야 한다.'

const array = [10, 48, 51, 13, 31, 3];

array.sort();
console.log(array); // [ 10, 13, 3, 31, 48, 51 ]

array.sort((a, b) => a - b); // 오름차순 정렬
console.log(array); // [ 3, 10, 13, 31, 48, 51 ]

array.sort((a, b) => b - a); // 내림차순 정렬
console.log(array); // [ 51, 48, 31, 13, 10, 3 ]