알고리즘 10강 :: 버블정렬, 선택정렬, 삽입정렬, 셸정렬

알고리즘 10강을 보며 배운내용

 

 

정리(TL;DR)

밑의 4가지 정렬 모두 시간 복잡도 On²

1. 버블 정렬
  1. 인접한 두 값 비교
  2. 왼쪽 값이 크면 자리 바꾸기
안정적 정렬 ✅
제자리 정렬 ✅

2. 선택 정렬
  1. 최솟값 찾고
  2. 작은 값부터 나열
안정적 정렬 ❌
제자리 정렬 ✅

3. 삽입 정렬
  1. 정렬 부분(첫 번째 값), 미정렬 부분(두 번째 값부터)으로 잡고
  2. 정렬 부분 뒤부터 비교
  3. 정렬 부분의 값보다 크거나 같으면 오른쪽에 삽입
안정적 정렬 ✅
제자리 정렬 ✅

4. 셸 정렬
  삽입 정렬을 개선하고자 나온 정렬
  삽입 정렬을 크기가 변하는 부분 배열로 실행
안정적 정렬 ❌
제자리 정렬 ✅

 

정렬

• 내부 정렬
  모든 데이터가 주기억장치에 저장
• 외부 정렬
  보조기억장치에 저장하고 필요할 때 주기억장치로 가져온다

 

 

내부 정렬 알고리즘

비교 기반, 데이터 분포 기반

 

1. 비교 기반

• 일반적으로 비교 기반 사용
• 키값의 비교 횟수

버블, 선택, 삽입, 셸

⌛ O(n²)

 

합병, 퀵, 힙

⌛ O(nlogn)

 

2. 데이터 분포 기반

• 데이터를 분포 상태를 알고 있을 때
• 데이터 이동 횟수

계수, 기수

⌛ O(n)

 

 

안정적(Stable) 정렬
동일한 값을 갖느 데이터 여러개 있을 때
정렬 후에도 순서 유지

제자리(In-place) 정렬
추가적인 저장 공간 증가하지 않는 것

 

 

버블 정렬

1. 인접한 두 값을 비교해서
2. 왼쪽 값이 큰 경우 자리 바꾸는 과정 반복

 

✨ 특징

안정적 & 제자리 정렬 알고리즘

입력 데이터가 역순일 때 가장 성능이 떨어진다

 

버블 정렬이 한 번 돌아갈 때(한 번 '패스'라고 한다)

왼쪽에서 오른쪽으로 진행하면

➡️ 가장 큰 값이 맨 오른쪽에 위치

오른쪽에서 왼쪽으로 진행하면

➡️ 가장 작은 값이 맨 왼쪽에 위치

 

🤖 코드

// 버블정렬
function bubbleSort(배열, n){
  for(let i = 0; i < n - 1; i++) {
    for(let j = 0; j < (n - 1) - i; j++) {
      // 왼쪽이 크면 자리 바꾸기
      if(배열[j] > 배열[j+1]) {
        [배열[j], 배열[j+1] = [배열[j+1], [배열[j]]
      }
    }
  }
  return 배열
}

 

🦾🤖 개선된 코드

// 개선된 버블정렬
function bubbleSort(배열, n){
  let exchange = false
  for(let i = 0; i < n - 1; i++) {
    exchange = false
    for(let j = 0; j < (n - 1) - i; j++) {
      // 왼쪽이 크면 자리 바꾸기
      if(배열[j] > 배열[j+1]) {
        [배열[j], 배열[j+1] = [배열[j+1], [배열[j]]
        exchange = true
      }
    }
    if(!exchange) break;
  }
  return 배열
}

자리 바꿈이 일어나지 않으면 반복문을 나오게 만들어줬다

 

 

선택 정렬

가장 작은 값부터 차례대로 선택해서 나열

 

✨ 특징

언제나 동일한 시간 복잡도

제자리 정렬 알고리즘

 

🤖 코드

// 선택 정렬
function selectionSort(배열, n) {
  for(let i = 0; i < n - 1; i++) {
    let 최솟값 = i;
    // 우선 최솟값 찾기
    for(let j = i + 1; j < n; j++) {
      if(배열[최솟값] > 배열[j] {
        최솟값 = j
      }
    }
    // 첫 번째 원소와 최솟값 교환
    [배열[i], 배열[최솟값]] = [배열[최솟값], 배열[i]]
  }
  return 배열
}

 

 

삽입 정렬

데이터 하나씩 뽑아서 바른 위치에 삽입해서 나열

1. 정렬 부분과 미정렬 부분으로 구분하고
2. 미정렬 부분에서 첫 번째 데이터 뽑고
3. 정렬 부분에서 들어갈 위치에 삽입

➡️ 정렬 부분 뒤부터 비교하면서 넣어주면 된다

 

✨ 특징

안정적 & 제자리 정렬

데이터 하나씩 비교하는 비효율 가지고 있다

➡️ 그래서 나온 셸 정렬

 

🤖 코드

// 삽입 정렬
function insertionSort(배열, n) {
  let i, j
  for(i = 1; i < n; i++) {
    let 첫번째데이터 = 배열[i]
    for(j = i; j > 0 && 배열[j - 1] > 첫번째데이터; j++) {
      배열[j] = 배열[j - 1]
    }
    배열[j] = 첫번째데이터
  }
  return 배열
}

i = 1부터 하는 이유는 첫 번째 데이터를 정렬 데이터로 취급

 

 

셸 정렬

삽입 정렬의 단점 보완

멀리 떨어진 데이터와 비교/교환

 

부분 배열로 나눠서 삽입 정렬 수행

부분 배열 크기와 개수 변화시키면서 반복

 

✨ 특징

제자리 정렬 알고리즘

 

🤖 코드

// 셸 정렬
function shellSort(배열, n) {
  let i, j, val
  for(let D = n / 2; D >= 1; D = D / 2) {
    for(i = D; i < n; i++) {
      val = 배열[i]
      for(j = i; j >= D && 배열[j - D] > val; j = j - D) {
        배열[j] = 배열[j - D]
      }
      배열[j] = val
    }
  }
}

 

 

Bubble by Alexander Dummer #unsplash