[JAVA/알고리즘] 버블정렬(Bubble sort)

버블정렬

- 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째, .... 이런식으로

(마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
• 인접한 두 개의 레코드를 비교하여 순서가 맞지 않으면 서로 교환 하는 방식이다
• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는맨 끝에 있는 자료는 정렬에서 제외, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 증가한다.

- 배열에 1, 6, 4, 5, 3 이 저장되어있다고 가정 -> 오름차순 정렬

 

1회전 :

2회전 :

3회전 :

4회전 :

결과 :

- 소스코드

package sort;

public class BubbleSort
{

	public static void bubbleSort(int[] num)
	{
		int ch = 0;
		for (int i = 0; i < num.length; i++)
		{
			for (int j = 0; j < num.length - 1 - i; j++)
			{
				if (num[j] > num[j + 1])
				{
					ch = num[j];
					num[j] = num[j + 1];
					num[j + 1] = ch;
				}
			}
			for (int k = 0; k < num.length; k++)
			{
				System.out.print(num[k] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args)
	{
		int num[] = { 1, 6, 4, 5, 3 };

		bubbleSort(num);


	}
}

- 시간복잡도

 데이터의 개수를 n개라고 가정한다면,

 (n -1) + (n - 2) + ... + 2 + 1 => n(n - 1)/2이 되므로, O(n^2)만큼의 시간이 걸린다.