버블 정렬

제일 간단하고, 구현이 쉬운 정렬입니다. 

정렬을 단순하게 생각한다면 제일 먼저 떠오를만한 정렬로, 하나하나씩 정렬이 되는 게

거품이 올라오는 모습과 비슷하기에 버블 정렬이라는 이름이 생겼습니다.

그래서인지 대체로 효율적이지 않습니다.. (거품 정렬..)

 

특징

• 제자리 정렬 (다른 메모리 공간 필요하지 않음)
• 안정 정렬
• 첫 번째 항목부터 마지막까지 입력 배열을 반복
• 각 항목 쌍을 비교하면서, 필요하면 교환하는 동작 방식
• 비교 특성상 맨 마지막부터 역차적으로 정렬이 된다
• n-1, n-2, ,,, 2, 1 = n(n-1)/2

시간 복잡도

• 최악: O (n^2)
• 최선: O (n^2)
• 평균: O (n^2)

시간 복잡도는 굉장히 비 효율적인 편입니다.

예시 그림

이렇게 반복

구현 코드 ( java )

void bubbleSort(int A [], int n) {
	for(int pass = n - 1; pass >= 0; pass--) {
		for (int i = 0; i < pass - 1; i++) {
			if (A[i] > A[i+1]) {
				int temp = A[min];
				A[i] = A[i + 1];
				A[i + 1] = temp;
			}
		}
	}
}