[알고리즘] 버블정렬

버블정렬?

https://riptutorial.com/ko/algorithm/topic/1478/%EB%B2%84%EB%B8%94-%EC%A0%95%EB%A0%AC

버블정렬은 이웃한 두 요소의 대소관계를 비교하여 교환을 반복하는 알고리즘이다.

다음과 같은 배열이 있다.
6 4 3 7 1 9 8

버블정렬에선 끝에 있는 두 요소부터 시작한다. (9와 8)
오름차순으로 정렬한다고 가정하면 두 요소를 비교하였을 때 작은 값이 왼쪽, 큰 값이 오른쪽에 위치해야 한다.

9와 8을 비교하였을 때 8이 더 작으므로 두 수의 위치가 바뀌어야 한다.
6 4 3 7 1 8 9

그리고 뒤에서부터 그 다음 요소인 1과 8을 비교한다. 이때 1은 이미 8보다 작고, 왼쪽에 위치하므로 교환을 할 필요가 없다.

이런식으로 뒤에서부터 이웃한 요소를 비교, 교환하는 작업을 첫번째 요소까지 계속 한다면 그 결과는 가장 작은 요소가 앞쪽에 위치하게 된다.

이러한 일련의 과정(비교, 교환)을 하나의 pass라고 부른다.

첫번째 pass가 끝난 결과
1 6 4 3 7 8 9

2번째 pass 또한 다시 동일하게 맨 뒤 요소 2개부터 비교,교환작업을 시작한다. 단 1번째 pass의 결과로 맨 앞의 1번째 요소는 가장 작은 값을 가지게 되므로 비교,교환작업은 두번째 요소까지만 진행이 된다.

• 하나의 pass에서 일어나는 비교,교환작업
  >> 남은 요소의 개수가 n개 일때 n-1회 시행
• 배열의 요소 개수가 n일때 일어나는 pass 시행 수
  >> n-1개. n개가 아닌 이유는 어짜피 마지막에 남는 요소는 자동으로 가장 큰 요소이기 때문이다.

참고로 서로 이웃한 요소에 대해서만 교환을 하기때문에 버블 정렬은 안정적인 정렬 알고리즘이라 불린다.

버블정렬 구현 (버전1)

import java.util.Scanner;

public class BubbleSort {
	
	//배열의 두 요소 자리를 바꿔주는 메서드
	public static void swap(int[] a, int index1, int index2) {
		int temp = a[index1];
		a[index1] = a[index2];
		a[index2] = temp;
	}
	
	/*
	 * 배열 전체의 길이가 n일때, 실행되는 pass의 횟수는 n-1이다.
	 * i는 현재 pass가 몇번째 pass인지 알려준다.
	 * i = 0일땐 pass = i +1, 즉 1번째 pass 진행중인것.
	 * i =0이라면 맨 앞에서부터 0번째 요소까지는 정렬이 완료되어있음.
	 */
	public static void bubbleSort(int[] a, int n) {
		for(int i = 0; i<n-1; i++) {
			for(int j = n-1; j>i; j--) {
				//오름차순 기준
				if(a[j-1] >  a[j]) {
					swap(a, j-1, j);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner ss = new Scanner(System.in);
		System.out.println("버블 정렬(버전1)");
		System.out.println("요소 개수 입력 : ");
		
		int nx = ss.nextInt();
		int[] x = new int[nx];
		
		for(int i=0; i<nx; i++) {
			System.out.print("x[" + i + "] : " );
			x[i] = ss.nextInt();
		}
		
		bubbleSort(x, nx);
		
		System.out.println("버블정렬 오름차순 완료");
		
		for(int i = 0; i<nx; i++) {
			System.out.println("x[" + i + "] : " + x[i]);
		}
	}
	
}