버블 정렬 - Bubble Sort

버블 정렬의 개념

---

버블 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 크기를 비교하고

조건에 맞지 않으면 서로 자리를 교환하여 정렬하는 알고리즘이다.

 

 

거품 정렬의 동작 과정

---

n번째와 n+1번째 원소를 비교하여 조건에 맞지 않으면 교환한다.

 

1회전 할 때 가장 큰 원소가 제일 마지막 순서에 정렬되고 이 수는 2회전 정렬에서 제외된다.

 

Code

---

void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length; i++) {       
		for(int j= 1 ; j < arr.length-i; j++) { 
			if(arr[j-1] > arr[j]) {             
                // swap(arr[j-1], arr[j])
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

 

시간 복잡도

---

버블 정렬의 시간 복잡도는 1회 정렬할 때 n-1, 2회 정렬할 때 n-2 ... 2 , 1 이므로

(n-1) + (n-2) + ... 2 + 1 = O(n^2) 시간 복잡도를 갖는다.

 

버블 정렬은 정렬 여부를 고려하지 않고 2개 원소를 비교하기 때문에

최선, 최악, 평균의 경우 모두 O(n^2) 시간 복잡도를 갖는다.

 

장점

---

버블 정렬은 간단하게 구현이 가능하고 소스코드도 직관적인 장점이 있다.

 

정렬하고자 하는 배열 내에서 교환하기 때문에 다른 메모리 공간을 필요로 하지 않는

알고리즘이다. ( In Place Sorting )

 

단점

---

시간 복잡도가 최선, 최악, 평균의 경우 모두 O(n^2) 시간 복잡도를 갖기 때문에

비효율적인 정렬 알고리즘이다.

 

원소의 정렬을 위해 교환 연산이 많이 일어나게된다.

 

 

출처 : https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview