정렬(2). 버블 소트(bubble sort)

버블 소트란?

버블 소트는 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

Bubble sort 원리 (출처: https://www.programiz.com/algorithm)

위에서와 같이 인접한 원소와 하나하나 비교하며 정렬을 수행한다. 배열의 끝까지 정렬을 완료하면 다시 처음으로 돌아가 같은 작업을 반복하여 수행한다. 다음은 JAVA로 작성된 버블 소트의 코드이다.

 

public class bubbleSort {

	public static void main(String[] args) {
		int arr[] = {1,3,6,2,8,2,5,9};
		//정렬중 임시 저장 
		int temp;
		
		//출력(정렬전)
		System.out.print("정렬전: ");
		for(int i = 0; i< arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println();
		
        //정렬
		for(int i = 0; i<arr.length;i++) {
			for(int j=0;j<arr.length-1;j++) {
				if(arr[j]>arr[j+1]) {
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		
        //출력(정렬후)
		System.out.print("정렬후: ");
		for(int i = 0; i< arr.length; i++) {
			System.out.print(" " +arr[i]);
		}
	}

}

다음은 출력 결과이다.

 

 

                                 
                                    [출처]: https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

거품 정렬 - 위키백과, 우리 모두의 백과사전