[자바] 정렬 알고리즘 - 버블정렬

버블 정렬(Bubble Sort)

- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘  (효율성이 가장 떨어진다.)

- 서로 비교해서 큰 값을 뒤로 보내는 것이다. (오름차순으로)

- 버블하면 비눗방울이 떠오르는데 비눗방울은 작으니 작은 원으로 감싸져 있는 인접한 두 원소를 검사하여 정렬한다고 생각하자.

버블정렬 사진

이런과정을 데이터 갯수만큼해야되는데 조건이 배열의 마지막인덱스는 정렬된 값이라서 나중에 정렬할때 제외하는게 좋다.

이때 데이터갯수가 n개라고 하면 위의 단계를 n-1번만 하면 된다 왜냐하면 마지막으로 배열의 인덱스 0에 남은 것은 앞의 것이 정해짐에 따라 같이 정해지기 때문이다.

 

public class Bubble_Sort {
	public static void bubble_sort(int []a) {
		for(int i=1; i<a.length;i++) {
			for(int j=0;j<a.length-i;j++) {
				if(a[j]>a[j+1]) 
				{
					swap(a,j,j+1);
				}
			}
		}
	}
	
	public static void swap(int []a, int i, int j) 
	{
		int temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
}

이런식으로 하면 될 것이다.

 

단점

- 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.

 

시간복잡도

O(N2)이다.