버블정렬(BubbleSort)

(N-1)+(N-2)……2+1 = n^2    최악, 최선, 평균에 상관없이 항상 n^2  만큼의 시간복잡도를 가진다.     가장 왼쪽수 부터, 바로 옆에 있는 값과 비교하여 정렬을 한다.

예  제

Ex)  4 1 3 2

1) 가장 좌측에 있는 4부터 값을 비교 한다.
   1 4 3 2 <-- 4, 1 값 비교하여 4의 값이 더 크므로 값을 스위치
   1 3 4 2 <-- 4, 3 값 비교하여 4의 값이 더 크므로 값을 스위치
   1 3 2 4 <-- 4, 2 값 비교하여 4의 값이 더 크므로 값을 스위치

  2) 1)에서 가장 큰수인 4를 확정 지었으므로 -1개수만큼만 비교한다.
       1 2 3 <-- 2, 3 값 비교하여 3의 값이 더크므로 값을 스위치

  3) 2)에서 가장큰수인 3을 확정 지었으므로 -1개수만큼만 비교한다.
       1 2 <-- 1, 2 값 비교하여 1이 2보다 작으므로 그대로 둔다.

  결과 : 1 2 3 4

 

 

소스

public class BubbleSort {
 
    public static void main(String[] args) {
        int[] targetArr = {3,9,6,5,2,7,4,1,8}; 
 
        int length = targetArr.length;
        for(int i=length-1; i > 0; i--) {
            for(int j=0; j < i; j++) {
                if(targetArr[j] > targetArr[j+1]) {
                    int temp = targetArr[j];
                    targetArr[j] = targetArr[j+1];
                    targetArr[j+1] = temp;
                }
            }
        }
        
        for(int result : targetArr) {
            System.out.print(result);
        }
    }
}