거품 정렬 (Bubble Sort)

정의

---

• 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어있지 않으면 자리를 교환하며 정렬

과정

---

• 맨 앞에서부터 맨 뒤에까지 비교하며 정렬, 맨 앞의 숫자는 가장 작은 값이 오게 됨
• 이미 반복되어있는 배열이면 의미없는 순환 멈추게 하는 sorted변수 추가!

코드 ( JAVA )

---

static int[] bubbleSort(int[] A) {
	
    for(int i = A.length - 1; i >= 1; i--) {
    	boolean sorted = true; 
        for (int j = 0; j < i - 1; j++){
        
    		if ( A[j] > A[j + 1] ) {
        		int temp = A[j];
            	A[j] = A[j + 1];
            	A[j + 1] = temp;
            	sorted = false;//false로 바뀌면 정렬이 되지 않았다는 뜻
        	}
    	}
        if ( sorted == true) return a; //중간에 배열이 정렬되었으면 리턴
    }
    return a;
 }

시간 복잡도

---

• 비교 횟수
• sorted변수 쓰지 않았을때 : 정렬되어있더라도 반복비교 (n-1) + (n-2) + ... + 3 + 2 + 1 = n(n-1)/2
• 최선 최악 모두 : O(n^2)
• sorted변수 사용했을때 : 이미 정렬된 데이터는 반복비교 종료 = O(n)
• 교환 횟수
• 최악 : 한번의 교환을 위해 3번의 이동(swap)이 필요하므로 비교횟수 * 3 = 3n(n-1)
• 최선 : 교환이 일어나지 않는다
• sorted변수 사용했을때 : 이미 정렬된 데이터는 반복비교 종료 = O(n)