[알고리즘] 버블 정렬

버블 정렬이란?

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 인접한 2개의 요소를 비교하여 오름차순이 아니라면 서로 교환
• 시간복잡도 : T(n) = O(n^2)

Example

(출처 : https://www.geeksforgeeks.org/bubble-sort/)

예제

• 배열의 크기와 요소를 임의대로 입력하면 버블 정렬 적용

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int length = sc.nextInt();
		
		int[] num = new int[length];
		
		for(int i=0; i<length; i++) {
			num[i] = sc.nextInt();
		}
		
		int tmp;
		
		for(int i=0; i<num.length; i++) {
			for(int j=i+1; j<num.length; j++) {
				if(num[i] > num[j]) {
					tmp = num[i];
					num[i] = num[j];
					num[j] = tmp;
				}
			}
		}
		
		for(int i=0; i<num.length; i++) {
			System.out.print(num[i]+" ");
		}
	}
}

장점

• 구현이 매우 간단

단점

• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.

• 특정 요소가 최종 정렬 위치에 있는 경우에도 교환이 일어날 수 있다.