Bubble Sort, Insertion Sort 구현해보기

이번 글에서는 정렬 알고리즘 중에서 Bubble 정렬, Insertion 정렬에 대해서 알아보고 구현해보려고 한다.

 

Bubble Sort

버블 정렬은 최악의 시나리오에서 가장 비효율적인 정렬 알고리즘이지만,

우리가 이해하기 가장 쉬운 방식이다.

 

버블 정렬은 배열을 반복하고 각 인덱스를 옆에 있는 인덱스와 비교한다.

그리고 서로 크기 비교를 하며 모든 값들이 순서에 맞게 위치할 때까지 루프를 반복한다.

 

인덱스를 스왑 하는지를 확인하는 내부 루프와 교체된 항목이 있는지 확인하는 외부 루프가 있다.

따라서 버블 정렬의 시간 복잡도는 O(n^2)이다.

 

버블 정렬을 아래 코드로 구현해보았다.

function bubbleSort (nums) {
  let i = 0;
  
  while(i < nums.length) {
    nums.reduce((acc, cur, index) => {
      if (acc > cur) {
        let swap = cur;
        
        nums.splice(index, 1, acc);
        nums.splice(index - 1, 1, swap);
  
        return acc;
      }
  
      return cur;
    });
    
    i += 1;
  }
}

이 코드를 통해 배열의 요소가 이동하는 과정은 다음과 같이 이루어진다.

---

 

nums = [10,5,3,8,2,6,4,7,9,1]

버블 정렬에서 요소의 이동 과정

 

 

 

Insertion Sort

삽입 정렬은 단계가 조금 더 복잡하지만 버블 정렬보다 약간 더 유용하다.

 

최악의 시나리오에서 버블 정렬과 비슷하지만,

최상의 시나리오에서는 배열이 거의 정렬되었거나 이미 정렬되었을 가능성이 있는 경우에 적합하다.

 

배열의 시작 부분에서 시작하여 길이 1의 정렬된 목록이 있다고 가정하며, 첫 번째 요소가 해당된다.

그리고 두 번째 요소를 가져와 정렬된 배열에서 크기 비교를 한 후, 올바른 위치에 삽입한다.

정렬된 배열 옆의 요소를 가져와 위 과정을 반복하면서 정렬해 나간다.

 

요소를 삽입할 올바른 위치를 찾기 위해 정렬된 배열을 살펴보는 내부 루프와 모든 숫자를 살펴보는 외부 루프가 있다.

따라서 두 개의 루프는 곧 O(n^2)을 의미한다.

그러나 배열이 거의 정렬되었을 경우와 같이 최상의 시나리오에서는 O(n)이 될 수 있다.

 

Insertion Sort를 구현해 보았다.

function insertionSort (nums) {
  let searchIndex = 1;
  
  while(searchIndex < nums.length) {
    let target = nums[searchIndex];
    
    nums.splice(searchIndex, 1);
    
    for (let i = 0; i < searchIndex; i++) {
      if (target <= nums[i] && (target > nums[i - 1] || !i)) {
        nums.splice(i, 1, target, nums[i]);
        searchIndex += 1;
      }
    }
  }
  
  return nums;
}

배열의 요소가 변화하는 과정은 아래 그림과 같다.

 

---

nums = [10,5,3,8,2,6,4,7,9,1]

 

삽입 정렬에서 요소의 이동 과정

 

 

 

출처

https://btholt.github.io/four-semesters-of-cs/

Four Semesters of Computer Science in Six Hours