버블정렬 (bubble sort) 을 간단하게 알아보자.

 

버블 정렬을 간단하게 설명하면?

정렬하는 모습이 마치 거품이 올라오는 모습 같아 버블 정렬!

 

1. 두 숫자 (인접한 배열) 를 비교해 스왑하면서 정렬하는 방식입니다.
2. 한 번의 스캔마다 최댓값이 제일 오른쪽에 위치하게 됩니다.

 

구현 과정

import java.util.*;
public class Main {
	
	public static void main(String[] args) {
		int[] A= {70, 20, 10, 80, 60, 90, 30, 40, 100, 50};
		
		for(int i=0; i<A.length; i++) {            //정렬 전 배열 출력 
			System.out.print(A[i]+" ");
		}
		System.out.println();
		
		for(int i=0; i<A.length-1; i++) {    //n-1번째 배열은 n번째와 비교하기 때문에 n까지 갈 필요없음. 
			for(int j=0; j<A.length-1-i; j++) {  //-i: 뒤쪽은 이미 정렬된 상태이기 때문에 굳이 끝까지 비교할 필요 x.
				if(A[j]>A[j+1]) {               //A[j]>A[j+1]이면 스왑.
					int temp=A[j+1];                
					A[j+1]=A[j];
					A[j]=temp;
				}
			}
		}
		
		for(int i=0; i<A.length; i++) {
			System.out.print(A[i]+" ");
		}
}
}

 

구현 과정 - 2

import java.util.*;
public class Main {
	
	public static void main(String[] args) {
		int[] A= {70, 20, 10, 80, 60, 90, 30, 40, 100, 50};
		
		for(int i=0; i<A.length; i++) {            //정렬 전 배열 출력 
			System.out.print(A[i]+" ");
		}
		System.out.println();
		
		for(int i=A.length-1; i>0; i--) {    //n-1번째 배열은 n번째와 비교하기 때문에 n까지 갈 필요없음. 
			for(int j=0; j<i; j++) {  //뒤쪽은 이미 정렬된 상태이기 때문에 굳이 끝까지 비교할 필요 x.
				if(A[j]>A[j+1]) {               //A[j]>A[j+1]이면 스왑.
					int temp=A[j+1];                
					A[j+1]=A[j];
					A[j]=temp;
				}
			}
		}
		
		for(int i=0; i<A.length; i++) {
			System.out.print(A[i]+" ");
		}
}
}

 

 

 

시간 복잡도 

• Worst : O(n^2)
• Average : O(n^2)
• Best : O(n^2)