나동빈 실전 알고리즘 3강 - 버블 정렬(Bubble Sort)

<문제> 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요
1 10 5 8 7 6 4 3 2 9

---

이번에는 버블 정렬(Bubble Sort)로 다음 숫자들을 오름차순으로 정리해보려고한다.

버블 정렬이란 이웃한 두 숫자를 비교하여 큰 수를 뒤로 보내는 정렬인데

확실히 듣기만해도 비효율적으로 보인다.

 

그럼 버블 정렬 프로그램을 작성해보자.

 

package excercise;

public class algorithm {
	public static void main(String[] args) {
		int temp = 0;
		int arr[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
		
		for(int i = 0; i < arr.length; i++) {
			for(int j = 0; j < (arr.length - 1) - i; j++) { // j는 배열의 index를 나타낸다. index는 0부터 시작하므로 크기를 조정해준다.
				if(arr[j] > arr[j+1]) {
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}	
}

 

방법은 간단하다. 배열 앞에서부터 차례대로 이웃한 두 수를 비교하여 앞 숫자가 크다면 뒤의 숫자와 자리를 바꿔주는 형식으로 진행한다.

 

 

해당 프로그램을 실행하게되면 복잡도는 n^2으로 선택정렬과 비슷하다.

 

blog.naver.com/ndb796/221226803544

3. 버블 정렬(Bubble Sort)