오랜만에 알고리즘 포스팅을 한다..
알고리즘 중에 기본이라고 할 수 있는 버블 정렬에 대해서 다시 정리하고 싶어져서 포스팅을 하게 되었다.
🎶 버블 정렬이란?
- 서로
인접한두 원소를 검사하여 정렬하는 알고리즘- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
😒 구체적으로!
1회전으로, 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, ...
마지막-1 번째 원소와 마지막 원소를 비교하며 조건에 맞지 않으면 서로 교환한다.
1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 가고 2회전부터는 첫번째 원소부터 마지막 -1번째 원소까지 검사한다.
이렇게 하나씩 줄여가면서 검사한다.
🕹코드
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length; i++) { // 1.
for(int j= 1 ; j < arr.length-i; j++) { // 2.
if(arr[j-1] > arr[j]) { // 3.
// swap(arr[j-1], arr[j])
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}💁♂️버블 정렬의 특징
- 장점
- 매우 간단
- 단점
- 순서에 맞지 않은 요소를 인접한 요소와 교환
- 가장 왼쪽에 있는 요소가 가장 오른쪽으로 이동하려면 다 교환해야함
- 자료의 교환 작업 (SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 줄구하고 거의 쓰이지 않는다.
🤦♀️시간 복잡도
- 비교 횟수
- 최상, 평균, 최악 모두 일정
- n-1, n-2, ... , 2, 1 = n(n-1)/2
- 교환 횟수
- 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP)이 필요하므로 (비교 횟수 3) 번 = 3n*(n-1)/2
- 이미 정렬 -> 이동 없음
=> O(n^2)
🙌출처
https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
야호