Bubble Sort   버블 정렬

(2020-05-02)

Exchange Sort, 교환 정렬

1. 버블 정렬 (Bubble Sort) 또는 교환 정렬 (Exchange Sort)

  ㅇ 정렬 방법
     - 이웃 요소 간에 대소 비교하고, 필요시 교환을 수행하며,
     - 이 과정을 전체 자료에 걸쳐 반복 수행

  ㅇ 버블 의미
     - 매 반복/패스/라운드 마다 가장 큰 수가 버블(거품)되어 맨 끝으로 이동됨

  ㅇ 연산 및 구성
     - 연산 : 비교(compare), 교환(swap)
     - 구성 : 이중 루프(반복문)

  ㅇ 계산 효율성 : O(n2)
     - 키 비교 횟수 : 총 n(n-1)/2 회
        . i=0일 때, (n-1)번 비교, i=1일 때, (n-2)번 비교, ... , i=(n-2)일 때, 1번 비교 등
        . 즉, (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

  ㅇ 한편, 교환 정렬 (Exchange Sort)은, 버블 정렬과 거의 같으나, 
     - 두 이웃 수 간에 비교 및 교환이 아니라,
     - 두 수의 위치 중 하나를 고정하고 다른 위치를 이동하며 비교/교환을 수행


2. 정렬 방법

  ㅇ 2개의 중첩 루프를 사용
     - 외부 루프는, 루프를 돌 때 마다, 
        . 제일 큰 원소를 맨 우측에 보내고, 정렬 대상 크기를 하나씩 줄임
     - 내부 루프는,
        . 가장 큰 원소를 맨 우측에 보냄
        . 좌측부터 두 이웃 원소를 비교하며, 순서가 맞지 않으면, 하나하나 교환하고 나감

  ㅇ 기 정렬 여부의 확인
     - 만일, 어떤 교환도 발생 않고 끝나면, 
     - 이미 자료가 정렬된 상태 임 ☞ 3.항 개선 버블 정렬 참조


3. 알고리즘 표현

  ㅇ 개선전 버블 정렬 (오름차순) 
     
Input  : (정렬 전 데이터 배열) Data[], (배열 데이터 수) int n
Output : (정렬 후 데이터 배열) Data[]

BubbleSort(int Data[], int n) {
    for (i = 0; i < n-1; i++)             // (입력 개수 - 1)까지 반복
        for (j = 0; j < n - (i+1); j++)   // (대상 개수 - 1)까지 반복
            if (Data[j] > Data[j+1])      // 순서 맞지 않으면
                Data[j] ↔ Data[j+1];     // 자리바꿈
}
ㅇ 개선후 버블 정렬 (오름차순)
Input  : (정렬 전 데이터 배열) Data[], (배열 데이터 수) int n
Output : (정렬 후 데이터 배열) Data[]

BubbleSort(int Data[], int n) {
    for (i = 0; i < n-1; i++)             // (입력 개수 - 1)까지 반복
        sorted = TRUE;
        for (j = 0; j < n - (i+1); j++)   // (대상 개수 - 1)까지 반복 
            if (Data[j] > Data[j+1])      // 순서 맞지 않으면
                Data[j] ↔ Data[j+1];     // 자리바꿈
                sorted = FALSE;           // 교환 발생했으므로, 플래그 설정
        if (sorted == TRUE) return;       // 입력이 이미 정렬 상태이면, 바로 종료
}


[정렬 알고리즘] 1. 정렬 알고리즘 2. 버블 정렬 3. 선택 정렬 4. 삽입 정렬 5. 병합 정렬 6. 퀵 정렬

 
        최근수정     요약목록     참고문헌