[Algorithm] 거품 정렬(Bubble Sort) 이란?

📖 거품 정렬(버블 정렬)이란?

거품 정렬은 인접한 두 원소를 검사하면서 정렬하는 알고리즘입니다.

시간 복잡도가 O(n²)으로 다른 알고리즘에 비해 속도가 상당히 느리지만 구현이 어렵지 않아 자주 사용됩니다.

아래의 영상을 보시면 쉽게 이해하실 수 있습니다.

 

📕 알고리즘

• 앞에서부터 현재 원소와 다음 원소의 크기를 비교
• 현재 원소가 다음 원소보다 클 시 교환
• 다음 원소로 이동하여 1번부터 다시 진행

arr[1]과arr[2], arr[2]과arr[3] , ...... , arr[n-1]과arr[n]을 비교하고 그다음엔
arr[1]과arr[2], arr[2]과arr[3] , ...... , arr[n-2]과arr[n-1] 비교,
arr[1]과arr[2], arr[2]과arr[3] , ...... , arr[n-3]과arr[n-2] 비교,

...

arr[1]과arr[2] 비교 후 종료되는 방식입니다.

 

 

👨🏻‍💻 JAVA로 구현

import java.util.*;
public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		System.out.print("배열의 길이 입력 : ");
		int N = sc.nextInt();
		
		
		int arr[] = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		
		// Bubble Sort
		
		for (int i = N-1; i >= 0; i--) {
			for (int j = 0; j < i; j++) {
				if(arr[j] > arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		
		// 출력
		System.out.println("오름차순으로 정렬됨");
		for (int i = 0; i < N; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
			
	}
}