버블 정렬

버블 정렬은 배열에서 차례대로 두 개의 붙어있는 인덱스를 비교하여 더 큰 값을 뒤로 보내는 정렬 방법이다.
가장 큰 값이 먼저 맨 뒤로 보내지고 그 다음 뒤에서부터 순차적으로 정렬이 완성된다.

n = array length
처음엔 인덱스 0부터 n-2까지 그다음 인덱스와 비교하면서 다음 인덱스가 크면 서로 교환
위 절차를 0~n-3, 0~n-4, 0~n-5, ... 0~0으로 총 n-1번 순회
i : 0~n-2
j : 0~n-2-i

	public class BubbleSort {
	public int[] sort(int[] arr) {
	int temp;
	for (int i = 0; i < arr.length-1; i++) {
	for (int 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;
	}
	}
	}
	return arr;
	}
	public static void main(String[] args) {
	BubbleSort bubbleSort = new BubbleSort();
	int[] sort = bubbleSort.sort(new int[]{7, 3, 78, 3, 4, 8, 10, 34});
	System.out.println(Arrays.toString(sort));
	}
	}

view raw BubbleSort.java hosted with ❤ by GitHub

 

최선의 경우, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 성능이 좋지 못하여 구현이 쉽다는 장점 말고는 다른 정렬 방법과 비교했을 때 좋은 정렬 방법이 아님.