JavaScript 알고리즘 (3) 삽입정렬 (Insertion Sort)

알고리즘 세번째 시간 😀 삽입정렬에 대해 알아보자

---

삽입정렬

삽입정렬은 각 숫자를 적절한 위치에 삽입하는 방법이다.

선택정렬, 버블정렬은 이중포문으로 원소들을 몽땅 검사하면서 위치를 바꾸는 정렬이었지만, 

삽입정렬은 조건을 걸어 필요할 때만 위치를 바꾸게 된다.

그래서 버블정렬과 선택정렬보다 더 빠르지만 시간복잡도는 O(N^2)으로 엄청 막 효율적이라고는 말할 수 없다

안정적인 정렬 알고리즘이고, 제자리 정렬 알고리즘 이다. (비교와 교환을 통해 정렬하는 알고리즘이므로 다른 메모리 공간을 필요로 하지 않음)

 

뒤죽박죽인 배열 내의 숫자들을 오름차순(1, 2, 3, ... 10)으로 정렬해보자

자, 준비물은 array, temp 다. 이 변수들 안에 숫자들을 담아 능력껏 줄세워보자.

let array = [1, 5, 4, 2, 3]; //오름차순 정렬할 배열
let temp; //두 원소를 바꿔치기하는 임시장소

// 1. 포문으로 배열을 검사한다.
for (let i = 0; i < 4; i++) {
  let j = i; // j값을 i값으로 놓는다. (그래야 while문에서 j를 인덱스로 동시에 사용가능하니까)
  
  // 2. 현재원소가 > 다음원소보다 크고 && j가 0이상이면, while문 실행!
  while (array[j] > array[j + 1] && j >= 0) {
    // 3. 두 원소 서로 스와핑
    temp = array[j]; 		 // temp에 현재 원소(array[j])의 값을 넣어준다.
    array[j] = array[j + 1]; 	 // 현재 원소(array[j])의 값을 다음 원소값으로 바꿔주고,
    array[j + 1] = temp; 	 // temp, 즉 현재 원소 자리에는 다음 원소값으로 대체한다.
    // 4. j--로 이전 숫자들을 같은 조건으로 한번 더 검사해서 걔네들도 스와핑 해준다.
    j--; 	
  }
}

 

실행 과정을 자세히 살펴보자

항상 왼쪽에 있는 부분은 이미 정렬이 되있기 때문에 전체를 살펴볼 필요없이 해당 원소들의 위치만 바꾸면 된다.

while문안에서 j--를 해줘서 조건에 안 맞아서 튕겨나갈 때까지 그 하위 배열을 검사해줘야 한다.

 

 

ref: https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz