[Algorithm] 버블정렬

두 인접한 원소를 검사하여 정렬하는 방법
시간복잡도가 느린편이지만 코드가 단순해서 자주 사용된다.

(구현하기는 간단하지만 비효율적인 알고리즘)

 

버블정렬 (java)

public class BubbleTest {
	public static void main(String[] args) {
		int[] a = {254,3,213,64,75,56,4,324,65,78,9,5,76,3410,8,342,76};
		int b;
		for(int i = 0 ; i < a.length ; i ++) {
			for(int j = 0 ; j < a.length -i -1 ; j ++) {
				if(a[j]>a[j+1]) {
					b = a[j];
					a[j] = a[j+1];
					a[j+1] = b;
				}
			}
		}
		
		for(int i = 0 ; i < a.length ; i ++) {
			System.out.println(a[i]);
		}
	}
}

출처 : [Algorithm]버블정렬 예제(bubble sort)

 

버블 정렬은 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에, 
(->  why? 한 회전이 끝나면 배열안에서 가장 큰 값이 맨 뒤로 가기 때문.)

전체 원소의 개수가 n개 라고 할 때, 총 n-1 번 순회하면 정렬이 끝난다.

 

총 원소 개수가 5개라면 4 + 3 + 2 + 1 = 10번 비교하게 된다.

(-> 총 (n-1) + (n-2) + ... + 2 + 1 번의 비교연산 발생. for문을 각각 n번과 n-1번 돌림)

 

 

시간복잡도는 (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2, 즉 O(n2)

등차수열의 합

(참고) O(n2)정렬 알고리즘엔 선택정렬, 삽입정렬, 버블정렬이 있다

 

 

최악의 경우 O(n^2)

최선의 경우 O(n) 의 시간복잡도를 갖게된다.

 

빅오 표기법

알고리즘 시간 복잡도 표기법 3가지 표기법최상의 경우 : 오메가 표기법 (Big-Ω Notation)최악의 경우 : 빅오 표기법 (Big-O Notation)평균의 경우 : 세타 표기법 (Big-θ Notation)
가장 보편적으로 사용되는 것은 Big-O 표기법입니다. Big-O 표기법은 계수와 낮은 차수의 항을 제외시키는 방법입니다(ex: 2n²-2n+2 > O(n2)로 표기). 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다.
(출처 : [Algorithm] 알고리즘을 위한 시간복잡도 계산 방법 - Big-O 표기)

 

 

참고한 블로그

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

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

 

버블정렬 버블소트 BubleSort 자바구현

버블정렬 버블소트 BubleSort 자바구현

 

정렬 알고리즘 정리1 ( 개념 / 시간복잡도 - O(n^2) )

정렬 알고리즘 정리1 ( 개념 / 시간복잡도 - O(n^2) )