[알고리즘] 정렬 알고리즘 간단구현

🔴 정렬 알고리즘

정렬 알고리즘은 원소들을 순서대로 sorting하는 알고리즘이다. 이미 어느 정도 알고 있지만 기본적인 정렬 알고리즘인 선택정렬, 삽입 정렬, 버블 정렬 등을 직접구현해보고 더 자세히 알아보았다.

✔ 선택정렬

선택 정렬 원리

 선택정렬 알고리즘은 배열의 첫번째 index의 값을 최소값target으로 보고 배열의 모든 요소를 순회하면서 target의 값보다 작은 값과 스왑하며 순회하는 알고리즘이다.

구현

arr.forEach((num,index) =>{
    let minIndex = index 
    for(let i = index+1 ; i < arr.length - index ; i++){
        if(arr[i] < arr[minIndex]){
            minIndex = i
        }
    }
  /**구조분해 할당으로 위치 바꿔주기*/
    [arr[index] , arr[minIndex]] = [arr[minIndex], arr[index]] 
})

시간복잡도 및 효율

 최소 값을 찾기 위해 모든 요소들을 순회해야 하기 때문에 효율이 그렇게 좋지는 않다. 시간복잡도로 표현하면 최고, 평균, 최악 모두 O(n제곱)이다.

✔ 삽입정렬

삽입 정렬 원리

 삽입정렬의 경우는 두번째 index부터 시작한다. 앞의 요소들과 값을 비교하여 알맞은 자리에 삽입된다.

구현

for(let i = 1 ; i < arr.length-1 ; i++){
    for(let j = i ; j > 0 ; j--){
        if(arr[j] < arr[j-1]){
  			/**구조분해 할당으로 위치 바꿔주기*/
            [arr[j], arr[j-1]] = [arr[j-1], arr[j]]
        }else{
          	/**만족하지 않다면 바로 loop탈출*/
            break;
        }
    }
}

시간복잡도 및 효율

 삽입 정렬의 경우 평균과 최악의 경우에 O(n제곱)으로 선택 정렬과 크게 다를게 없다. 하지만 어느 정도 정렬이 되어있는 경우 swap단계를 단축할 수 있으므로 최선의 경우에서는 O(n)으로 효율이 크게 상승한다.

✔ 버블정렬

버블정렬 원리

 버블정렬은 인접한 두 요소를 번갈아면서 비교하여 스왑하는 방식이다. 계속해서 순회를 해야하는 점이 특징이다.

구현

arr.forEach((num, index) =>{
    for(let i = 1 ; i< arr.length-1  ; i++){
        if(arr[i-1] > arr[i]){
            [arr[i-1] , arr[i]] = [arr[i] , arr[i-1]]  
        }
    }
})

시간복잡도 및 효율

 버블 정렬도 선택정렬과 마찬가지로 계속 순회를 해야하기 때문에 효율이 좋지않다. O(n제곱)

Reference
https://jinhyy.tistory.com/9

👍올바른 피드백은 언제든지 환영입니다~!