[알고리즘] 버블정렬(Bubble sort) 정리, JAVA

[알고리즘] 버블정렬 정리

1. 버블정렬이란?(위키백과 참고)
   • 인접한 원소를 검사하여 정렬하는 방법
   • 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용 됨.
   • 원소의 이동이 거품이 수면으로 올라 오는 듯한 모습을 보이기 때문에 지어진 이름
   • 배열의 i, i+1번째를 비교하여 큰수를 오른쪽으로 밀어내는 방식.
2. 버블정렬의 원리

 

 

• 입력으로 int[] arry = {6, 5, 3, 1} 배열을 비교하려고 한다.
• 첫번째 비교 루프를 시작한다.
• arry[0] = 6, arry[1] =5을 비교한다.

[6, 5, 3, 1]
 ^  ^
 
 6 > 5 라면 6과 5를 변경하여 배열에 넣어준다.
 
 [5, 6, 3, 1]
  ^  ^

• arry[1]=6, arry[2]=3을 비교한다.

[5, 6, 3, 1]
    ^  ^
 
 6 > 3 이기 6과 3을 변경하여 배열에 넣어준다.
  
 [5, 3, 6, 1]
     ^  ^

• arry[2]=6, arry[3]=1을 비교한다.

 [5, 3, 6, 1]
     	^  ^
 
 6 > 1 므로 6과 1을 변경하여 배열에 넣어준다.
  
 [5, 3, 1, 6]
        ^  ^​

• 이런 방법으로 계속해서 i, i+1 값의 대소를 비교하여 배열을 교체하여 주면 버블 정렬을 완성 시킬 수 있다.

3.버블정렬 소스화(JAVA)

package com.mansik.algorithm;


public class BubbleSort {

	public static void main(String[] args) {
		int[] array = {6, 5, 3, 1};
		
		sort(array);
		
	}
	
	private static void sort(int[] array) {
		System.out.print("input Array : ");
		arrayPrint(array);
		
		for(int i=0; i<array.length-1; i++) {
			System.out.println("Loop Count["+i+"]");
			if(array[i] > array[i+1]) {
				int temp = array[i];
				array[i] = array[i+1];
				array[i+1] = temp;
			}
		
			arrayPrint(array);
		}
		
	}
	

	public static void arrayPrint(int[] array) {
		for(int i=0; i<array.length; i++) {
			System.out.print(array[i]+",");
		}
		System.out.println("");
	}

}

4. 출력 화면

버블정렬 출력 화면