알고리즘 기초 (버블정렬)

Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다.

 

버블 정렬

 

버블정렬

• 정렬 알고리즘중 하나인 버블정렬은 두 개의 인접한 자료의 값을 비교하며 위치를 교환하는 방법 (A - B)

 

버블정렬에 대해서

버블정렬은 한번에 단 두개의 자료만 정렬하기 때문에 좁은 범위의 정렬로 단 하나의 자료를 정렬하기 위해 불필요한 교환과 낭비가 발생할 수도 있습니다.  예를 들어 4, 3, 1, 0 과 같이 내림차순으로 정렬된 경우 오름차순으로 정렬하기 위해선 총 3번을 수행해야 합니다. 즉 n개의 요소를 정렬하기 위해 n-1번을 수행해주어야 하며 이는 곧 비효율적인 최악의 상황의 경우 최대횟수를 실행해줘야 하는 것을 의미합니다. 결론적으로 버블정렬은 한번의 수행으로 모든 범위가 정렬되지 않기때문에 인접한 데이터들의 상관관계가 존재하며 어느정도 정렬이 된 적은 데이터를 검색할 때 효율적입니다.

 

 

Ex) 4, 30, 49, 11, 5 정렬순서

 

1. 4, 30, 11, 5, 49
2. 4, 11, 5, 30, 49
3. 4, 5, 11, 30, 49