[알고리즘] 버블 정렬

학습 목표

버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다.

1. 정렬 알고리즘

• 정렬되지 않은 리스트를 탐색하느 것보다 정렬한 뒤 탐색하는 것이 더 효율적이다.
• 정렬 알고리즘 중 하나인 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다.

2. 에시

숫자 8개가 임의의 순서로 나열 되어 있다.

6 3 8 5 2 7 4 1

이 숫자들을 오름차순으로 정렬하기 위해 버블 정렬을 이용해보자.

• 3 6 8 5 2 7 4 1
• 3 6 5 8 2 7 4 1
• 바로 다음에 있는 숫자와 비교해서 정렬을 해나가면 아래와 같이 정렬이 된다.
• 3 6 5 2 7 4 1 8
• 오름차순으로 정렬이 되지 않았기 때문에 다시 처음으로 돌아가서 같은 작업을 반복한다.
• 3 5 2 6 4 1 7 8
• 조금 더 정렬된 모습이지만 완벽히 정렬되지 않았으므로 다시 반복하자.
• 1 2 4 3 5 6 7 8