Bubble Sort - 버블 정렬

소개

인접한 두 수를 비교하면서 대소 비교에 적합한 수를 뒤로 보내는 알고리즘이다. 평균적으로 시간 복잡도는  $O(n^2)$를 나타낸다. 

설명

• 현재 인덱스의 바로 다음번 인덱스와의 크기를 비교해서 조건에 맞다면 위치를 옮겨준다. 여기서 조건은 대소 비교의 조건이다.
• 비교하면서 한 번 순회를 끝내면 순회 시 제일 마지막 인덱스는 자연스럽게 제일 크거나 작은 값이다. 
• 다음번 순회에서는 최종 인덱스 까지 순회할 필요 없다. 즉 순회마다 -1만큼 순회할 크기가 줄어 드는 것이다. 
  
  

시간 복잡도 계산 

전체 원소의 수가 $n$ 개라면 $(n-1) + (n-2) + ... + 2 + 1 = (n - 1) * n / 2 = (n^2-n)/2$의 값을 연산을 하게 될 것이다. 그래서 평균적인 시간 복잡도는 $O(n^2)$ 이 되는 것이다. 

소스코드 - JAVA

public class BubbleSort {
	public static void main(String[] args) {
		int[] beforeSortingValues = ;
		// 버블정렬은 순회 할 때마다 순회 하는 크기가 줄어 든다. 
		// 그래서 데이터 전체 길이로 시작해서 하나 씩 줄어 드는 가장 바깥쪽 for루프.
		for(int i=beforeSortingValues.length-1; i>=0; i--) {
			//원소들 끼리 비교하는 for루프
			for(int j=0; j<i; j++) {
				int afterJIndex = j + 1;
				int value1 = beforeSortingValues[j];
				int value2 = beforeSortingValues[afterJIndex];
				
				//대소 비교 부등호 방향에 따라 정렬이 바뀐다. 
				if(value1 > value2) {
					int temp = value1;
					beforeSortingValues[j] = value2;
					beforeSortingValues[afterJIndex] = temp;
				}
			}
		}
		
		for(int value : beforeSortingValues) {
			System.out.println(value);
		}
	}
}

참고 블로그 

http://bowbowbow.tistory.com/10