버블정렬, 삽입정렬, 선택정렬 완전분석

0. 개요

- 본격적으로 알고리즘 공부를 시작하면서, 가장 기초인 정렬 알고리즘을 배웠다.

- 수학공식 외우듯, 개념을 이해하고 외워야겠다는 태도로 접근했는데 쉽지 않았다. 

- 개념은 이해가 가지만, 코드로 구현했을 때 왜 이렇게 작성하는지 이해가 가지 않는 부분이 있었다. 

- 그래서 내가 완벽히 이해하기 위해 분석한 내용을 공유한다. 

- 아래 글의 사진이 잘 안보이는 분들을 위해 PDF 파일을 제공합니다. 

 

버블,삽입,선택정렬.pdf

9.70MB

---

1. Bubble Sort

a) 정렬과정 

 

b) 코드 기반 개념 이해 

 

c) 완성 코드

from typing import List

def bubble_sort(case: List[int]) -> List[int]:
   for idx in range(len(case) - 1):
      for i in range(len(case) - idx - 1):
         if case[i] > case[i + 1]:
            case[i], case[i + 1] = case[i + 1], case[i]
   return case

 

---

2. Insertion Sort

a) 정렬과정 

 

b) 코드 기반 개념 이해 

- 여기서부터 기준배열과 비교배열이라고 작성했는데, 배열이 아니라 요소를 의미하는 것임을 정정합니다. 

※ 기준 배열 → 기준 요소 

※ 비교 배열 → 비교 요소 

 

c) 완성 코드

from typing import List

def insertion_sort(case: List[int]) -> List[int]:
   for idx in range(1, len(case)):
      flag = idx - 1
      current = case[idx]
      while flag >= 0 and current < case[flag]:
         case[flag + 1] = case[flag]
         flag = flag - 1
      case[flag + 1] = current
   return case

---

3. Selection Sort

a) 정렬과정 

 

b) 코드 기반 개념 이해 

 

c) 완성 코드

from typing import List

def selection_sort(case: List[int]) -> List[int]:
   for idx in range(len(case)):
      min_num = case[idx]
      min_idx = idx
      for i in range(idx, len(case)):
         if min_num > case[i]:
            min_num = case[i]
            min_idx = i
      case[min_idx], case[idx] = case[idx], case[min_idx]
   return case