[Algorithm] 정렬 - Bubble Sort (거품 정렬)

[Algorithm] 정렬 - Bubble Sort (거품 정렬)

Bubble Sort

첫번째와 두번째 원소를 비교하여 정렬, 두번째와 세번째 , ... , n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 첫번째와 두번째, ... , n-2번째와 n-1번째 ... 이를 반복하는 방식이다.

Selection Sort와 마찬가지로 O(n^2)이다.

동작

Step1

Step2 부터 j가 이동하면서 swap하지않고 그냥 지나가는 것은 생략한다.

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort { public void swap(arr, index1, index2) { int temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = arr[index1]; } public void bubbleSort(arr) { for(int i = arr.length - 1; i >= 0; i--) { for(int j = 0; j < i; j++) { if(arr[j] > arr[j+1]) { swap(arr, j, j+1); } } } } }

from http://jino-dev-diary.tistory.com/32 by ccl(A) rewrite - 2021-09-13 22:01:05