버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

'인접'한 두개의 원소를 비교하여 자리를 교환하는 방식으로 정렬.

처음부터 마지막 원소까지 반복하면서 가장 큰 원소가 마지막으로 정렬된다.

​

평균 비교 횟수와 평균 자리 교환 횟수는 n(n-1)/2 이다.

따라서 시간 복잡도는 O(n^2)가 된다.

​

예시)

{57, 16, 41, 2, 50, 6}

​

1. 인접한 두 원소를 비교하여 자리를 교환하는 작업을 마지막 원소까지 반복하여 가장 큰 원소를 마지막 자리로 옮긴다.

{57, 16, 41, 2, 50, 6}

===>

{16, 57, 41, 2, 50, 6}

===>

{16, 41, 57, 2, 50, 6}

===>

{16, 41, 2, 57, 50, 6}

===>

{16, 41, 2, 50, 57, 6}

===>

{16, 41, 2, 50, 6, 57}

​

2. 위와 같은 작업을 마지막에서 두번째 원소까지 반복하여 다음으로 큰 원소를 옮긴다.

{16, 41, 2, 50, 6, 57}

===>

{16, 41, 2, 50, 6, 57}

===>

{16, 2, 41, 50, 6, 57}

===>

{16, 2, 41, 50, 6, 57}

===>

{16, 2, 41, 6, 50, 57}

​

3. 위와 같은 작업을 마지막에서 세번째 원소까지 반복하여 그 다음으로 큰 원소를 옮긴다.

{16, 2, 41, 6, 50, 57}

===>

{2, 16, 41, 6, 50, 57}

===>

{2, 16, 41, 6, 50, 57}

===>

{2, 16, 6, 41, 50, 57}

​

4. 위와 같은 작업을 마지막에서 네번째 원소까지 반복하여 그 다음으로 큰 원소를 옮긴다.

{2, 16, 6, 41, 50, 57}

===>

{2, 16, 6, 41, 50, 57}

===>

{2, 6, 16, 41, 50, 57}

​

5. 위와 같은 작업을 마지막에서 다섯번쨰 원소까지 반복하여 그 다음으로 큰 원소를 옮긴다.

{2, 6, 16, 41, 50, 57}

===>

{2, 6, 16, 41, 50, 57}

​

6. 마지막으로 남은 첫번째 원소는 가장 작은 원소이므로 종료한다.

{2, 6, 16, 41, 50, 57}

​

프로그램 작성)

package test;

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

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50, 6};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.bubleSort(a);

		System.out.println("정렬 후 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
	}
}

실행 결과)