**버블 정렬(Bubble Sort)**은 인접한 두 개의 원소를 비교하여 조건에 맞지 않으면 자리를 교환하며 정렬하는 알고리즘입니다. 정렬하는 과정에서 가장 큰 원소가 맨 뒤로 이동하므로 버블(bubble) 정렬이라고 부릅니다.
버블정렬의 **시간복잡도는 O(n^2)**이다. 이는 정렬하고자 하는 리스트의 크기가 커질수록 연산 횟수가 기하급수적으로 증가하기 때문에, 대규모 데이터를 정렬하는 데에는 적합하지 않다. 따라서 정렬 시간을 효율적으로 줄일 수 있는 다른 정렬 알고리즘을 사용하는 것이 좋다.
버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
즉, 버블정렬이 1회 실행시 모든값을 지나가며 두개의 값을 비교해 큰값을 계속해서 뒤로 옮기고 마지막에 모든값중 가장 큰값이 뒤에 오게된다. 그러므로 마지막값은 다음 연산에서 제외하여도 된다.
1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
버블 정렬을 사용하여 데이터를 정렬 하는 모습
