[이론] 버블 정렬 알고가기

버블 정렬은 왜 버블 정렬일까? 🤔

버블 정렬이라는 이름은 딱 들었을 때 뭔가 귀엽고 친근한 느낌을 받았습니다. 처음 들었을 때 이름이 너무 매력적이라 "왜 이런 이름이 붙었을까?" 궁금했는데, 그 이유를 알고 나니 정말 딱 맞는 이름이라는 생각이 들었습니다!

 

"버블"의 의미 🫧

버블 정렬(Bubble Sort)은 배열의 요소들이 거품처럼 위로 보글보글 올라가는 모습과 비슷하다고 해서 붙여진 이름입니다.

• 오름차순 기준 큰 값이 반복적으로 비교되어 점점 위로 올라가고, 가장 큰 값이 맨 끝에 위치하게 됩니다.
• 마치 물속의 거품이 위로 올라가며 터지는 것과 유사하죠!

 

버블 정렬의 작동 원리 ✍️

버블 정렬은 인접한 두 값을 비교하여 잘못된 순서를 가진 값들을 서로 교환합니다.
가장 큰 값이 배열의 끝으로 밀려나면서 정렬이 이루어지죠.

 

버블 정렬 수행 방식

 

만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬 됐다는 뜻이므로 프로세스를 종료해도 됩니다.

 

버블 정렬의 시간 복잡도 ⏳

버블 정렬은 단순하고 이해하기 쉽지만, 데이터가 많아질수록 비효율적이라는 단점이 있습니다.

버블 정렬은 반복문이 두 개 중첩되어 있습니다. 따라서 O(n^2)으로 다른 정렬 알고리즘 보다 속도가 느린 편입니다.

 

개발자들의 센스 

사실 알고리즘의 이름은 기능적이거나 딱딱한 경우가 많은데, 버블 정렬은 그 이미지 자체가 친근하고 귀여운 느낌이다.

어쩌면 이름을 지은 개발자들도 "이왕이면 이름이라도 친근하게 지어보자!" 라는 마음으로 "버블 정렬"이라는 이름을 지었을 수도 있다는 상상을 해보았다. 😊