TIL 날짜
2023.11.30
Contents
- 의미 및 장단점
- 자바스크립트 내장 메소드
- 종류
- 각 종류들의 차이점
정렬 알고리즘의 의미
의미: 데이터를 특정한 기준에 따라 순서대로 나열하는 알고리즘
장점
- 간단한 알고리즘이 많아 구현이 쉽다.
- 정렬된 상태에서의 성능이 우수한 알고리즘이 존재한다.
단점
- 데이터 크기가 커지면 성능이 떨어지는 알고리즘이 존재
- 특정한 상황에 따라 최적화된 알고리즘이 필요
- 일부 알고리즘은 추가적인 메모리를 사용하여 효율성이 떨어진다.
자바스크립트 내장 메소드
Sort
- sort(): 문자열 순서대로 정렬
- sort(): 숫자열을 하면 앞에 있는 맨앞 숫자로 비교한다.
- sort((a,b)=>a-b): 숫자열 오름차순으로 정렬
- sort((a,b)=>b-a): 숫자열 내림차순으로 정렬
정렬 알고리즘의 종류
버블 정렬
의미: 서로 인접한 두원소를 검사하여 정렬하는 알고리즘
- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환한다.
과정
장점
- 구현이 매우 간단하다.
단점
- 순서에 맞지 않는 요소를 인접한 요소와 교환
- 불 필요한 연산이 많다.
- 안정적인 정렬 알고리즘에서 성능이 좋지 않다.
예시
function BubbleSort(arr){
for(let i=arr.length; i>0; i--){
for(let j=0; j<i-1; j++){
if(arr[j]>arr[j+1]){
let temp = arr[j]
arr[j] = arr[j+1];
arr[j+1] = temp
}
}}
return arr;
}
BubbleSort([37,45,29,8) //[8,29,37,45]
선택 정렬
의미: 주어진 리스트에서 최소값을 찾아 해당 위치에 있는 원소와 교환하는 알고리즘
과정
장점
- 구현이 간단하고 코드가 직관적이다.
단점
- 최선, 평균,최악의 경우 모두 비슷한 성능이므로 입력 데이터의 정렬 여부에 관계 없이 항상 동일한 시간복잡도
- 안정성이 없는 정렬 알고리즘
예시
function SelectionSort(arr){
for(let i = 0; i < arr.length; i++){
let lowest = i;
for(let j = i+1; j < arr.length; j++){
if(arr[j] < arr[lowest]){
lowest = j;
}
}
if(i !== lowest){
let temp = arr[i];
arr[i] = arr[lowest];
arr[lowest] = temp;
}
}
return arr;
}
SelectionSort([3,10,15,12,22,0]); //[0,3,10,12,15,22]
삽입 정렬
의미: 매 순서마다 해당 원소를 삽입할수 있는 위치를 찾아 삽입하는 알고리즘
과정
장점
- 안정된 정렬 방법
- 자료의 수가 적을 경우 알고리즘 구현이 매우 간단
- 이미 정렬 되어 있는 경우나 자료의수가 적을 경우 매우 효율적
단점
- 비교적 많은 레코듣들의 이동을 포함
- 자료의 수가 많고 자료의 크기가 클 경우 적합하지 않는다.
예시
function InsertionSort(arr){
for(let i=arr.length; i>0; i--){
let currentVal =arr[i]
for(let j=i-1; j>=0 && arr[j] > currentVal; j--){
arr[j+1] = arr[j]
}
arr[j+1] = currentVal;
}
return arr
}
InsertionSort([2,1,9,76,4]) //[1,2,4,9,76]
정렬 알고리즘 종류들 차이점
| 시간 복잡도(Best) | 시간 복잡도(Average) | 시간 복잡도(Worst) | 공간 복잡도 | |
| 버블 정렬 | O(n^2) | O(n^2) | O(n^2) | O(1) |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) | O(1) |
| 삽입 정렬 | O(n) | O(n^2) | O(n^2) | O(1) |