정렬 알고리즘은 아래와 같이 2가지로 나뉜다.
그 중 버블 정렬을 다뤄보자.
1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세번째 원소를, 세 번째와 네 번째 원소를... 이런 식으로 마지막 -1번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고 2회전을 수행하고 나면 끝에서 두번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
int[] arr = {7, 6, 2, 4, 3, 9, 1};
private static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) { // 1
for (int j = 0; j < arr.length - i - 1; j++) { // 2
if (arr[j] > arr[j + 1]) { // 3
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.print((i + 1) + "단계 : ");
print(arr);
}
}
private static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 단계별 결과.
1단계 : 6 2 4 3 7 1 9
2단계 : 2 4 3 6 1 7 9
3단계 : 2 3 4 1 6 7 9
4단계 : 2 3 1 4 6 7 9
5단계 : 2 1 3 4 6 7 9
6단계 : 1 2 3 4 6 7 9
7단계 : 1 2 3 4 6 7 9
"한 마디로 내 앞의 숫자가 나보다 크면 나랑 자리 바꿔.
나보다 작으면 내 뒤의 숫자부터 다시 검사해."
첫 번째 for문은 제외될 원소의 갯수를 의미한다. 1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기에 하나씩 증가시켜준다. 2회전에 끝나면 배열의 마지막 두 위치에는 큰 원소 2개가 정렬된 상태로 위치할 것이기에 2개를 제외하면 된다. 이 부분은 코드에서 arr.length-i-1
이다.
왜 전체 갯수에서 i를 빼주는지는 위를 이해했다면 이해 될 것이다.
두 번째 for문은 원소를 비교할 index를 뽑는 for문이다. j는 0부터 arr.length-i-1까지 증가한다. 현재 원소와 다음 원소를 가리키기에 0부터 시작한다.
if문을 통해 기준이 되는 숫자와 현재 검사하는 숫자를 비교해서 기준이 되는 숫자가 현재 검사하는 숫자보다 크다면 큰 수가 작은 수보다 앞에 있으니까 자리를 바꿔준다.
(n-1) + (n-2) + (n-3) + ... + 2 +1 -> n/(n-1)/2이기에 O(N^2)이다.
버블 정렬은 정렬이 되어있건, 안 되어있건 2개의 원소를 비교하기에 최악,최선,평균 모두 시간 복잡도가 O(N^2)로 동일하다.
주어진 배열안에서 수행되기에 O(N)이 된다.