[정렬] 버블 정렬

개념

 

인접한 두 원소를 비교하여 큰 수를 뒤로 보내는 알고리즘

시간 복잡도는 O(n^2) 의 시간 복잡도를 가지며 정렬 알고리즘 처리속도가 제일 느리다.

장점은 코드가 단순해서 구현하기가 편하고 자주 사용된다.

단점은 처리속도가 느리다. 처리속도가 느리기 때문에 용량이 큰 리스트를 정렬할 때는 적합하지 않다.

 

처리과정

위와 같이 길이가 10인 정수형 배열이 존재하고 이 배열을 버블 정렬로 정렬을 하고자 하면 0번째 인덱스에서 배열의 길이만큼 반복문을 돌면서 (i) 와 (i+1) 인덱스의 값을 비교하고 (i) 인덱스의 값이 (i+1) 인덱스의 값 보다 크다면 (i) 와 (i+1) 인덱스의 값을 교체한다.

 

반복문을 돌 때마다 배열의 끝 부터 차례대로 큰수부터 작은수로 정렬이 되고 마침내 0번 인덱스까지 도달하면 버블정렬이 완료된다.

이미 정렬이 된 인덱스는 다음 조회에서는 접근하지 않아도 된다.

package S_20210126;

public class bubbleSort{
	public static void main(String[] args) {
		int[] arr = {2,8,1,4,6,5};
		
		// 오름차순
		for(int i=arr.length-1;i>=0;i--) {
			for(int j=0;j<i;j++) {
				if(arr[j]>arr[j+1]) {
					swap(j,j+1,arr);
				}
			}
		}
		
		print(arr);
	}
	public static void swap(int orgIdx, int changeIdx, int[] arr) {
		int temp = arr[orgIdx];
		arr[orgIdx] = arr[changeIdx];
		arr[changeIdx] = temp;
	}
	
	public static void print(int arr[]) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
}