정렬, 버블정렬 알고리즘

알고리즘 설명

<img alt="" src="https://static.podo-dev.com/blogs/images/2019/07/10/origin/VEOWAW181224235510.PNG" style="width:240px">

인접 배열의 숫자와 비교하여 정렬하는 알고리즘이다

0번째 배열과 1번째 배열을 비교하여 0번재 배열의 값이 크다면 1번째 배열과 바꾼다.

1번째 배열과 2번째 배열을 비교하여 1번재 배열의 값이 크다면 2번째 배열과 바꾼다.

이 과정을 N-1 번째 배열까지 진행하면 N번째 값은 가장 큰값이 된다. 이 과정을 하나의 사이클로 보자.

가장 큰값을 찾았으니 위 과정을 이번엔 N-2번째 까지 진행한다, N-1번째 값은 두번째로 큰 값이된다. 두번째 사이클이다.

이 사이클을 N-1번 반복하여, 배열을 정렬한다.

<br/>

복잡도

버블 정렬의 최선의 경우는 이미 정렬이 되어있는 경우이다.

이럴경우 N-1번 사이클을 하며 한사이클은 N-i만큼 순회한다.

결국 N + N-1 + N-2 + N-3 .... + N-(N-1) 순회하며 비교하므로, N(N-1)/2의 복잡도를 가진다.

최악의 경우는 역순으로 정렬되어 있는 것이다. N(N-1)/2번의 비교와 N(N-1)/2의 교환 횟수를 가진다.

따라서 버블 정렬의 시간 복잡도는 O(N^2) 이다.

<br/>

장단점

버블정렬은 가장 단순한 코드이다.

그러다 하나의 값이 맨 왼쪽부터 맨 오른쪽으로 이동하기 위해서는 모든 다른 배열값과 교환이 이루어져야한다.

일반적으로 자료의 교환(SWAP) 작업이 자료의 이동(MOVE) 작업보다 더 복잡하기 때문에, 버블정렬은 단숨함에도 불구하고 잘 사용하지 않는다.

<br/>

소스코드

public class BubbleSort {
	public void sort(int[] arr) {
		int n = arr.length;

		int temp;
		for (int i = 0; i <= n - 2; i++) {
			for (int j = 0; j <= n - 2 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}

	}

	public static void main(String[] args) {
		int arr[] = { 10, 8, 7, 3, 2, 15, 9, 5 };
		new BubbleSort().sort(arr);
		System.out.print(Arrays.toString(arr));
	}
	
}
<br/>

<br/>