java

[JAVA] 버블정렬 버블소트 (Bubble Sort)

희구 2021. 8. 24. 13:30

버블정렬(Bubble Sort)이란?

  • 인접한 두 숫자의 크기를 비교하여 위치를 교환하는 정렬 (작은 값을 앞으로 보냄)
  • 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째, .... 이런식으로 (마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
  • 1회전을 수행하고 나면 가장 큰 값이 맨 뒤로 이동하므로 2회전 부터는 맨 뒤의 값을 제외하고 정렬한다.
    2회전이 끝나면 두번째로 큰 값이 맨뒤에서 2번째로 이동하기 때문에 끝에서 두번째 값까지는 정렬에서 제외한다.
    이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

예제

  • 배열에 8 , 4 , 1 , 7 , 3이 저장되어있다고 가정한다.
  • 자료는 오름차순으로 정렬한다.

 

1회전

4 8 1 7 3

 

2회전

4 1 8 7 3

 

3회전

4 1 7 8 3

 

4회전

4 1 7 3 8

 

오름차순 완성상태

1 3 4 7 8

 

 

Java 버블정렬 예제

package bitarray;

public class Array01_BubbleSort {

	public static void main(String[] args) {
		int[]ar = {8,4,1,7,3};
		
		//정렬 전
		System.out.print("정렬 전 : ");
		for(int x : ar) {
			System.out.print(x + " ");
		}
		System.out.println();
		
		//정렬
		int temp;
		for(int i=0; i<ar.length-1; i++) { //회차 
			for(int j=0; j<ar.length-i-1; j++) { //인접한 숫자 비교
				if(ar[j]>ar[j+1]) {
					temp=ar[j];
					ar[j] = ar[j+1];
					ar[j+1] = temp;
				}//if
			}//for j
		}//for i
		
		//정렬 후
		System.out.print("정렬 후 : ");
		for(int x : ar) {
			System.out.print(x + " ");
		}
		System.out.println();
	}
}
  • 정렬 할때 바깥 쪽 for문(i)정렬 회차를 나타낸다.
    ar.length-1을 한 이유는 두개의 숫자를 비교하는 것이다보니
    4번까지만 정렬해도 5번째 숫자까지 포함되기 때문이다.
  • 안쪽 for문(j)인접한 두 수를 비교한다. 실제 정렬이 일어나는 곳이라고 생각하면 쉽다. 
    ar.length-i-1을 한 이유는 첫 회차가 끝나면 뒷자리는 sort가 완료되기 때문에 비교할 필요가 없기 때문이다.
  • if문을 사용하여 정렬하려는 두 수의 왼쪽과 오른쪽값을 비교한다.
댓글수0