[알고리즘] 버블 정렬

목차

버블정렬의 개념

1. 버블정렬의 방식
2. 버블정렬의 장단점
3. 버블정렬의 코드구현(JAVA)

버블정렬의 개념

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘을 말한다.

버블정렬의 방식

초기배열에 7,4,5,1,3이 있다고 가정을 해보자.

 

• 1회전
  
  • 첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.
• 2회전
  • 첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
• 3회전
  • 첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
• 4회전
  • 첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.

버블정렬의 장단점

장점

•       구현이 쉽다.

단점

• 최선이든 최악이든 시간복잡도 O(n2) 로 인하여 정렬 시간이 오래 걸린다. 따라서, 효율적인 정렬방법으로 사용되지 않는다.
• 하나의 요소가 끝에서 끝으로 이동하기 위해서 배열의 모든 다른 요소들과 교환되어야 한다.
• 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 발생한다.

버블정렬의 구현(JAVA)

public class BubbleSort {
	
	static void swap(int[]arr,int num1,int num2) {
		int tmp = arr[num1];
		arr[num1] = arr[num2];
		arr[num2] = tmp;
	}
	
	static void bubleSort(int[]arr, int size) {
		
		for(int i=0;i<size-1;i++) {
			for(int j =0 ;j<size-i-1;j++) {
				if(arr[j]>arr[j+1]) {
					swap(arr, j, j+1);
				}
			}
		}
	}
	
	static void Sort(int[]arr) {
		bubleSort(arr, arr.length);
	}
	
	public static void main(String[] args) {
		//버블정렬
		int[]numbers = {7,10,2,9,4,6};
		System.out.println(Arrays.toString(numbers));
		System.out.println();
		Sort(numbers);
		System.out.println();
		System.out.println(Arrays.toString(numbers));
	}
}