정렬-버블정렬

1. 정렬

자료구조에서 정렬을 얘기하는 이유는 탐색을 설명하기 위한것이다.

탐색은 어떤 기준을 근거로해서 정렬된 데이터들을 어떻게 효율적으로 탐색할것인가?그것을 논의하는게 탐색이다.

탐색에 앞서 선행된 주제가 정렬이다.

2. 버블정렬 이해

- 버블정렬은 구현하기는 쉬우나 성능은 떨어진다.

- 인접한 두개의 데이터를 비교해가면서 바뀌어야 한다면 두 데이터를 바꾸면서 정렬을 진행한다.

1) 첫번째 : 제일 큰 값을 맨 뒤로 보낸다.

2) 두번째: 두번째로 큰 값을 맨뒤에서 한 칸 앞으로 보낸다.

3) 세번째: 나머지를 동일하게 정렬한다.

이와 같이 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 한다.

3. 버블정렬 구현

- for문 중첩으로 구현하였다. 

- 안쪽 for문의 반복조건과 바깥쪽 for문의 반복조건에 대한 이해가 정확히 필요하다.

package Sort;
 
public class BubbleSort {
 
    public static void main(String[] args) {
 
        int[] arr = {3, 2, 4, 1};
 
        BubbleSort(arr, arr.length);
 
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
    static void BubbleSort(int[] arr, int n)
    {
        int i, j;
        int temp;//임시
 
        for(i=0; i<n-1; i++) {
            for(j=0; j<(n-i)-1; j++) {
                if(arr[j] > arr[j+1]) {//앞이 뒤보다 크다면, 앞뒤를 바꿔줌
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}
 
 
 
 
 
 

4. 성능평가

정렬 알고리즘의 성능은 다음 정렬과정의 핵심 2가지 근거로 판단하는것이 일반적이다.

1) 비교의 횟수  - 두 데이터간의 비교연산의 횟수

2) 이동의 횟수  - 위치의 변경을 위한 데이터의 이동 횟수

실제로 시간 복잡도에 대한 빅-오를 결정하는 기준은 비교의 횟수이다. 

비교횟수는 다음 반복문 안에 위치한 if문의 실행 횟수를 기준으로 계산할 수 있다.

if(arr[j] > arr[j+1]) {...} //비교 연산이 발생하는 장소

앞서 본 버블정렬의 과정 [10-1]~[10-3]의 그림을 보면

4개의 데이터를 3단계에 걸쳐서 정렬하였다. 비교의 횟수를 더한 결과는 3+2+1 이었다.

이렇듯 버블 정렬의 데이터의 수가 n개일때 진행되는 비교의 횟수는 다음과 같다.

(n-1) + (n-2) + . . . + 2+ 1

그리고 이는 등차수열의 합에 해당하므로 다음과 같이 정리된다.

따라서 버블 정렬의 비교연산에 대한 빅-오는 최선의 경우와 최악의 경우 구분없이 O(n^2) 이다.

빅오를 구할때 이동의 횟수는 무시했다.