거품 정렬(Bubble Sort)이란?

거품 정렬(Bubble Sort)은 인접한 두 원소의 대소 관계를 비교하여 작은 값의 원소를 앞으로, 큰 값의 원소를 뒤로 교환하면서 정렬하는 알고리즘이다. 자료구조와 알고리즘을 공부해본 사람이라면 알겠지만, 가장 먼저 배우는 정렬 기법이기도 하다. 왜냐하면 이 알고리즘은 구현하기도, 이해하기에도 정말 쉽다는 게 장점이다. 하지만 으레 모든 방법이 장점이 있다면, 그에 수반하는 단점도 있는 법. 거품 정렬은 비교와 교환을 반복하면서 시간 복잡도가 O(n^2)으로 비효율적이며 정렬된 데이터에 대해서도 비교를 계속 하므로 최선의 경우에도 O(n^2)의 시간복잡도를 가지게 된다. 아래는 자바로 구현한 거품 정렬이다. public static void main(String[] args) { int[] arr =..

2023.03.15