[자료 구조 & 알고리즘] 삽입 정렬(Insertion sort), 선택 정렬(Selection sort), 버블 정렬(Bubble sort) 그림 및 시간 복잡도 이해하기

각 정렬 방법의 기본 개념을 설명하고, 시각적인 그림을 통해 각 단계를 자세히 설명함으로써 여러분이 이 중요한 알고리즘들을 보다 쉽게 이해할 수 있도록 돕고자 합니다.

---

삽입 정렬 (Insertion Sort)

삽입 정렬은 마치 카드 게임을 할 때 카드를 한 장씩 뽑아 적절한 위치에 삽입하는 방식과 유사합니다. 각 반복에서 하나의 데이터 요소를 현재 정렬된 배열 부분과 비교하여 적절한 위치를 찾아 삽입합니다. 이 방법은 작은 데이터 세트에 효율적이며, 거의 정렬된 상태의 데이터에 매우 빠릅니다.

 

"삽입 정렬 시간 복잡도"

최악의 경우( Best Case)	평균의 경균 (Average Case)	최선의 경우 (Worst Case)
O(n²)	O(n²)	O(n)

 

• 초기 상태 : 

8

5

6

2

4

 

• 1회전

8

5

6

2

4

=>

5

8

6

2

4

 

두 번째 값을 첫 번째 값과 비교하여 5를 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동시킨다.

• 2회전

5

8

6

2

4

=>

5

6

8

2

4

 

세 번째 값을 첫 번째, 두 번째 값과 비교하여 6을 8자리에 삽입하고 8을 한 칸 뒤로 이동시킨다.

• 3회전

5

6

8

2

4

=>

2

5

6

8

4

 

네 번째 값 2를 처음부터 비교하여 맨 처음에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

• 4회전

2

5

6

8

4

=>

2

4

5

6

8

 

다섯 번째 값 4를 처음부터 비교하여 5자리에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

 

---

 

선택 정렬 (Selection Sort)

선택 정렬은 각 단계에서 배열에서 최소값(또는 최대값)을 찾아 선택한 후, 배열의 앞쪽에 위치한 요소와 교환합니다. 이 방식은 배열의 각 요소를 순회하며 직관적이지만, 대규모 데이터에는 비효율적일 수 있습니다.

 

"선택 정렬 시간 복잡도"

최악의 경우( Best Case)	평균의 경균 (Average Case)	최선의 경우 (Worst Case)
O(n²)	O(n²)	O(n²)

 

• 초기 상태 : 

8

5

6

2

4

 

• 1회전

5

8

6

2

4

 

=================>

5

8

6

2

4

 

=================>

2

8

6

5

4

바뀜.

=================>

2

8

6

5

4

 

• 2회전

2

6

8

5

4

바뀜.

=================>

2

5

8

6

4

바뀜.

=================>

2

4

8

6

5

바뀜.

• 3회전

2

4

6

8

5

바뀜.

=================>

2

4

5

8

6

바뀜.

• 4회전

2

4

5

6

8

 

---

버블 정렬 (Bubble Sort)

버블 정렬은 이름에서 알 수 있듯이, 데이터 요소들이 거품처럼 배열을 통해 상승하는 모습을 연상시킵니다. 인접한 요소들을 반복적으로 비교하고 교환하여, 가장 큰 요소를 배열의 맨 끝으로 밀어내는 과정을 반복합니다. 이 방법은 구현이 쉽지만, 효율성 면에서는 다른 정렬 방법에 비해 뒤떨어질 수 있습니다.

"버블 정렬 시간 복잡도"

최악의 경우( Best Case)	평균의 경균 (Average Case)	최선의 경우 (Worst Case)
O(n²)	O(n²)	O(n²)

 

• 초기 상태 : 

8

5

6

2

4

 

• 1회전

5

8

6

2

4

바뀜.

=================>

5

6

8

2

4

바뀜.

=================>

5

6

2

8

4

바뀜.

=================>

5

6

2

4

8

바뀜.

• 2회전

5

6

2

4

8

 

=================>

5

2

6

4

8

바뀜.

=================>

5

2

4

6

98

바뀜.

• 3회전

2

5

4

6

8

바뀜.

=================>

2

4

5

6

8

바뀜.

• 4회전

2

4

5

6

8