[알고리즘] 버블정렬 (Bubble Sort)

  목  차

• 버블정렬이란?
• 버블정렬 예시
• 버블정렬 설계
• 버블정렬 후기

 

---

 

 

  버블정렬이란?

 

버블정렬 알고리즘은 인접한 두 개의 요소를 비교하고, 필요하다면 두 요소의 위치를 바꾸는 과정을 반복하여 전체 배열을 정렬하는 방식이다.

 

 

 

  버블정렬 예시

 

숫자 5, 3, 8, 4, 2 가 요소로 들어있는 배열이 존재한다고 할 때.

이 배열을 버블정렬 알고리즘으로 정렬을 해보려고 한다.

 

1. 첫 번째 요소와 두 번째 요소를 비교한다. 만약 왼쪽의 요소가 더 크다면 두 요소의 자리를 바꾼다.

 

2. 두 번째 소요와 세 번째 요소를 비교한다. 만약 왼쪽의 요소가 더 크다면 두 요소의 자리를 바꾼다.

 

3. 세 번째 요소와 네 번째 요소를 비교한다. 

 

4. 네 번째 요소와 다섯 번째 요소를 비교한다.

 

이렇게 여러번 반복을 하면 정렬이 된다. 버블정렬의 시간 복잡도는 최대 O(n^2)이다.

 

이 배열의 마지막 모습은 이렇게 정렬되어 있을 것이다.

 

  버블정렬 설계

 

설계는 다음과 같이 Notion으로 했다.

 

 

  버블정렬 후기

 

정렬 알고리즘을 처음 하는거라 힘들지 않을까 했는데, 15분 내외로 끝낸 것 같다.

바깥 for문과 내부 for문의 역할을 이해하였더니 설계하기 쉬운 것 같았다.