[2023-09-26] TIL - 자료구조 & 알고리즘 - 정렬

정렬

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

 

정렬의 특징

- 정렬 기준은 사용자가 정할 수 있다.

- 크게 비교식과 분산식 정렬로 나눌 수 있다.

- 대부분의 언어가 빌트인으로 제공해준다.

- 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재한다.

 

 

비교식 정렬

버블 정렬

- 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘

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

버블정렬 이 과정을 반복한다.(가장 큰 수가 뒤로간다.)

 function solution(arr){
    let answer=arr;
    for(let i=0; i<arr.length-1; i++){
        for(let j=0; j<arr.length-i-1; j++){
            if(arr[j]>arr[j+1]){
                [arr[j], arr[j+1]]=[arr[j+1], arr[j]];
            }
        }   
    } 
    return answer;
}

let arr=[13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

 

선택 정렬

- 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘

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

function solution(arr){
    let answer=arr;
    for(let i=0; i<arr.length; i++){
        let idx=i;
        for(let j=i+1; j<arr.length; j++){
            if(arr[j]<arr[idx]) idx=j;
        }
        [arr[i], arr[idx]] = [arr[idx], arr[i]];
    } 
    return answer;
}

let arr=[13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

 

삽입 정렬

- 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘

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

function solution(arr){
    let answer=arr;
    for(let i=0; i<arr.length; i++){
        let tmp=arr[i], j;
        for(j=i-1; j>=0; j--){
            if(arr[j]>tmp) arr[j+1]=arr[j];
            else break;
        }
        arr[j+1]=tmp;
    } 
    return answer;
}

let arr=[11, 7, 5, 6, 10, 9];
console.log(solution(arr));

 

 

 

분산식 정렬

- 요소를 분산하여 정렬하는 방법

 

분할 정복

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

- 다양한 알고리즘에 응용된다.

 

합병 정렬

- 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘

- O(n log n) 시간 복잡도를 가진다.

 

퀵 정렬

- 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬

- O(n log n) 시간복잡도를 가진다.

 

 

자바스크립트의 정렬 방법

오름차순

const arr = [2, 1, 3, 10];

arr.sort(function(a, b)  {
  return a - b;
});
console.log(arr + '<br>'); // [1, 2, 3, 10]

내림차순

const arr = [2, 1, 3, 10];

arr.sort(function(a, b)  {
  return b - a;
});
console.log(arr + '<br>'); // [10, 3, 2, 1]