Bubble Sort : 거품 정렬

 

 

   Bubble Sort : 버블 정렬

       소개

       정렬과정

       구현

 

소개

Bubble Sort는 인접한 두 수를 비교하여 올바른 순서(오름차순 또는 내림차순)를 뒤로 보내는 간단한 정렬
알고리즘으로 각 회전(Pass)과정이 끝날 때마다 정렬은 뒤에서 하나씩 완료된다.

 

정렬과정

아래와 같은 배열이 있을 때, Bubble sort로 정렬하는 과정이다.

순서대로 인덱스 0부터 시작하며, 오름차순이 되도록 두 수를 비교하고 더 큰 수를 오른쪽으로 바꾼다.

 

임의의 배열을 표로 표현하였다.

 

인덱스	0	1	2	3
값	3	7	5	1

 

1, 2번째 교체 후 

 

인덱스	0	1	2	3
값	3	7	5	1

 

2, 3번째 교체 후 

 

인덱스	0	1	2	3
값	3	5	7	1

 

3,4번째 교체 후 

 

인덱스	0	1	2	3
값	3	5	1	7

 

한바퀴를 돌고 나면 위와 같은 결과를 가지게 되는데 가장 큰 수가 가장 오른쪽으로 위치하게 된다.

위와 같은 과정이 한차례 진행될 때마다, 뒤에서부터 원소들이 하나씩 정렬된다.

따라서 다음 회전부턴 이미 정렬된 원소를 제외한 원소들만 정렬해주면 된다.

 

구현

한 회전을 할 때마다 확인해야 할 원소의 개수가 하나씩 줄어든다는 걸 기억해두면 된다.

package javajungsuk;

import java.util.*;

public class bj_2562_Array {

	public static void main(String[] args) {
		
		int[] arr = { 3, 7 , 5, 1};
		int tmp;
		
		for(int i=0;i<arr.length-1;i++) {
			for(int j=0;j<arr.length-(i+1);j++) {
				if(arr[j]>arr[j+1]) {
					tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		
		System.out.println(Arrays.toString(arr));
		
	}
}

 

arr 배열이 오름차순으로 정렬된 것을 볼 수 있다