버블정렬(Bubble Sort)

버블정렬: 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 정렬

 

 

Java code

import java.util.*;

public class BubbleSort {
	public static void main(String[] args) {
		int i,j,temp;
		int []arr= {1,10,5,8,7,6,4,3,2,9};
		for(i=0;i<arr.length;i++) {
			for(j=0;j<(arr.length-1)-i;j++) {
				if(arr[j]>arr[j+1]) {
					temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}

			}
		}
		for(int k=0;k<arr.length;k++)
			System.out.print(arr[k]+" ");
	}
}

 

 

시간복잡도 계산

 

배열 arr에 1,10,5,8,7,6,4,3,2,9가 있다고 가정하면 총 배열의 길이가 10이다 

 

이 배열을 버블정렬로 정렬할때

ㄱ값을 왼쪽으로 보내는 연산을 실행하면

배열의 상태는 1,5,8,7,6,4,3,2,9,10이 된다 ->이때 10개의 데이터를 탐색한다

 

2. 그 다음엔 배열의 첫번째 요소부터 9번째 요소까지 탐색하고 더 작은값을 왼쪽으로 보내는 연산을 실행하면

배열의 상태는 1,5,7,6,4,3,2,8,9,10이 된다 -> 이때 9개의 데이터를 탐색한다

 

....

 

이런식으로 실행하면

 

버블정렬은 10+9+8+ ...+2+1=N(N*1)/2=O(N^2)의 시간복잡도를 갖는다 

 

 

선택정렬같은 경우는 탐색을 다 마친후에 최솟값만 맨앞으로 가져오면 되지만

버블정렬은 배열의 현재 요소와 뒤의 요소를 비교할때마다 뒤의 요소가 더 작으면 현재 요소와 교체해야 된다(매우 비효율적)

->시간복잡도는 선택정렬과 동일하지만 실제로는 선택정렬보다 훨씬 느리다

 

정렬 알고리즘 중에 가장 비효율적인 알고리즘이 버블정렬이다