버블정렬

---

• 버블 정렬은 이웃한 데이터들의 크고 작음을 비교한 뒤, 정렬 조건에 맞추어 이동 시키며 정렬하는 알고리즘입니다.
• 최대 값이 서서히 뒤로 옮겨지는 모습이 마치 사이다의 거품이 올라가는 모습과 비슷하다는 뜻에서 버블 정렬이라고 불립니다.
  
  
  오름차순으로 예시를 들겠습니다.

정렬하려는 배열은 정렬되지 않은 부분(앞부분)과 정렬된 부분(뒷부분)으로 나뉩니다.

정렬을 시작할 때는 정렬된 부분이 비어있는 상태이며, 정렬되지 않은 부분이 배열 전체를 차지합니다.

최대 값을 정렬되지 않은 부분의 끝으로 옮기는 순서를 떠올려봅시다.

순서

1단계 : 정렬되지 않은 부분의 1번째 데이터와 2번째 데이터를 비교한다 [ 이웃한 데이터 비교 ]

2단계 : 1번째 데이터 > 2번째 데이터라면, 두 값의 순서를 바꾼다. [ 큰 값을 뒤로 옮기는 중 ]

3단계 : 데이터를 비교하기 시작할 위치를 뒤로 1칸 옮긴다. [ i ++ ]

정렬되지 않은 부분의 데이터가 2개만 남을 때까지 위의 순서를 반복하면,

정렬되지 않은 부분의 마지막 요소에는 정렬되지 않은 부분의 ‘최대 값’이 저장됩니다.

이 다음 ‘정렬되지 않은 부분’의 크기가 ‘최대 값’이 들어있는 마지막 요소를 뺀 나머지 부분을 다시 정렬합니다.

점점 작아지는 정렬되지 않은 부분’에서의 ‘최대 값’이 차례대로 저장되어 갑니다.

따라서 전체적으로 ‘정렬된 부분’은 데이터 열의 끝 부분부터 커지고,

‘정렬되지 않은 부분’은 데이터 열의 시작 부분부터 줄어듭니다.

마지막에 ‘정렬된 부분’이 데이터 열 전체를 차지하게 되면 정렬이 완료됩니다.

실습

import java.util.Arrays;
import java.util.Scanner;

public class BubbleSort {

	// a[index1]과 a[index2]의 값을 바꾸는 함수
	static void swap(int[] arr, int index1, int index2) {

		int t = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = t;

	}

	**// 버블 정렬**
	static void bubbleSort(int[] arr, int n) {
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - 1; j++)
				if (arr[j] > arr[j + 1])
					swap(arr, j, j + 1);
			System.out.println(Arrays.toString(arr));
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.println("버블 정렬");
		System.out.print("요소 개수 : ");
		int n = sc.nextInt();
		int[] x = new int[n];

		for (int i = 0; i < n; i++) {
			System.out.print("X[" + i + "] : ");
			x[i] = sc.nextInt();
		}
		System.out.println("정렬 과정");
		bubbleSort(x, n);

		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < n; i++) {
			System.out.println("X[" + i + "] :" + x[i]);
		}
	}
}

---

1. 배열 요소의 값을 모두 입력하면 버블 정렬과정을 순서대로 출력합니다.
2. 실제 버블 정렬이 이루어지는 코드는 //버블정렬 주석 위치입니다.