[알고리즘] 버블 정렬(Bubble Sort)

 

 

서로 인접한 두 원소를 비교하고 조건에 맞지 않는다면 자리를 교환하는 정렬 알고리즘 (In-place sort)

 

• 1번째 원소 - 2번째 원소
• 2번째 원소 - 3번째 원소
• 3번째 원소 - 4번째 원소
• 4번째 원소 - 5번째 원소
• ...

 

💭 과정

---

1. 1회전에서 (1번째 원소, 2번째 원소), (2번째 원소, 3번째 원소), (3번째 원소, 4번째 원소),... (마지막-1번째 원소, 마지막 원소)를 비교하고 교환
   
   
2. 1회전이 끝나면 가장 큰 원소가 맨 뒤로 이동
   
   
3. 2회전에서 맨 뒤 원소 제외하고 위의 과정 반복

 

 

💭 코드

void BubbleSort(int arr[]){
	for(int i=0; i<arr.length; i++){     //n회
		for(int j=1; j<arr.length-i; j++){ //두 원소 비교 - 교환
			if(arr[j-1] > arr[j]) swap(arr[j-1], arr[j]);
		}
	}
}

 

 

💭 시간 복잡도

---

정렬 상태와 상관없이, 2개의 원소를 비교하기 때문에 O(n^2)

 

 

💭 공간 복잡도

---

주어진 배열 안에서 교환-정렬하기 때문에 O(n)

 

 

💭 장점

---

• 구현이 간단하고 직관적
• 제자리 정렬(in-place sorting) → 메모리 공간 추가 필요 x
• 안정 정렬
  
  

💭 단점

---

• 시간 복잡도 O(n^2)
• 교환 연산이 많이 일어남

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!

 

 

 

 

 

 

참고: https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html