20 버블(Bubble)정렬

버블 정렬 알고리즘

• 인접한 두 값들을 비교한다.
• 비교한 값들 중 정렬이 되어 있지 않으면 정렬해준다.

버블 정렬 하는 과정

출처 - 알고리즘 도감

 

5,4,3,2가 있다고 가정하자.

첫번째 사이클

• 5와 4를 비교후 정렬 -> 4, 5, 3, 2
• 5와 3를 비교후 정렬 -> 4, 3, 5, 2
• 5와 2를 비교후 정렬 -> 4, 3, 2, 5
• 이렇게 첫번째 사이클이 종료된다 
• 마지막 5는 이미 오름차순으로 보았을때 정렬이 되어 있으므로, 두번째 사이클부터는 비교를 해주지 않아도 된다.

두번째 사이클

• 4와 3 비교 후 정렬 -> 3, 4, 2, 5
• 4와 2 비교 후 정렬 -> 3, 2, 4, 5

세번째 사이클

• 3와 2 비교 후 정렬 -> 2, 3, 4, 5
• 이제 모두 정렬 되었다.
• 한 사이클을 실행할 때마다 검사할 자릿수(인덱스)가 하나씩 줄어든다.

package ex07;

public class BubbleEx04 {

	public static void main(String[] args) {
		int[] arr = { 50, 40, 30, 10, 8, 5 };
		int n = 0;
        	//한번 사이클을 실행마다 -1
			for(int k = arr.length-1; k > 0;k--) {
			for (int i = 0; i < k; i++) {
				if (arr[i] > arr[i + 1]) {
					int temp;
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
				}
			}
			n++;
			for (int i = 0; i < arr.length; i++) {
				System.out.println(arr[i]);
			}
			System.out.println(n + "번째 사이클 종료====");
			

		}
	}
}