[sorting] Bubble sort

BUBBLE SORT

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
  •  => 인접한 두 개의 원소를 비교하여 순서대로 되어있지 않을 경우 서로 교환한다.
  •  => array[3] < array[4] 일 경우 두 원소의 위치 변경
• 1회전 시 가장 큰 값이 맨 뒤로 이동한다.
  •  ==> 제외되는 데이터가 하나씩 늘어난다.

 

#include <stdio.h>
#include <iostream>
using namespace std;

int main(void) {
	int arr[10] = { 4,5,6,2,3,10,8,1,9,7 };
	int temp;

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 9 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
}

진행 결과

 

장점

• 구현이 간단하다.

말고 없나보다. 

 

단점

• 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서 다른 모든 요소들과 교환되어야 한다.
• 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
• 일반적으로 자료의 교환이(SWAP)이 자료의 이동작업(MOVE)보다 더 복잡하기에 버블정렬은 단순하지만 거의 쓰지 않는다.

 

시간복잡도

 

비교 횟수

• n-1번 진행 -> n-2번 진행 -> n-3번 진행 -> ... ->3번 진행 ->2번 진행 ->1번 진행

 => n(n-1)/2

 

교환 횟수

 

•  최악의 경우 : 입력자료가 역순으로 정렬되어 있는 경우. 1번의 교환을 위해 3번의 교환 필요.
  •  3*n(n-1)/2
• 최상의 경우 : 입력 자료가 이미 정렬되어있는 경우. 교환 X

 

T(n) = O(n^2)

최상, 평균, 최악 모두 동일

 

 

한 줄 요약 ==> 구현이 간단하고 단순하지만 비 효율적이다.

 

 

참고 url:

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

https://hongku.tistory.com/147