버블 정렬이란?
서로 인접한 두 원소를 검사하는 방법으로 인접한 2개의 값을 비교하여 크기가 순서대로 되어 있지 않으면 교환하는 단순 정렬 알고리즘 중 하나
정렬 과정은 다음과 같다.
첫번째 원소와 두번째 원소를 비교하여 왼쪽 값(첫 번째)이 크면 자리를 바꾸고 다시 두번째 원소와 세번재 원소를 비교한다. 위 과정을 반복하여 1회전이 끝나면 n번째(마지막)에 가장 큰 수가 오게 된다.
두번째 회전에서 마지막을 제외하고 반복하면 n-1번째에 두번째로 큰 수가 자리하게 된다. 위 과정을 n-1번 반복하면 모든 데이터가 순서대로 정렬된다.
버블정렬은 인접한 값끼리 반복해서 비교하는 방식이기 때문에 구현이 쉽고 코드가 직관적이라는 장점을 가지고 있다. 또한 n개의 원소에 대해 n개의 메모리를 사용하기 때문에 데이터를 하나씩 정밀 비교가 가능하다.
하지만 원소의 갯수가 늘어난다면 비교 횟수가 그만큼 늘어나기 때문에 성능이 저하된다는 단점도 있다. 최선, 최악의 경우 모두 O(n^2)이라는 시간 복잡도를 가진다.
시간 복잡도 참고 자료
https://velog.io/@gayo03/CSW-알고리즘-성능-표현-방법
이미 정렬된 원소들이 주어질 때나 배열의 요소 개수가 적을 때 (최선)
역순으로 정렬되었거나 배열의 요소가 많을 때 (최악)
자바스크립트를 이용하여 구현한 버블 정렬
