Bubble Sort   버블 정렬

(2022-10-05)

Exchange Sort, 교환 정렬


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

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

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

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


2. 연산의 구성 및 계산 효율성연산 및 구성
     - 연산 : 비교(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

     * 버블 정렬은, 항상 O(n2)인, 가장 느린 정렬 알고리즘3. 알고리즘 설명 및 특징

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

  ㅇ 구현이 매우 단순하나, 
     - 알려진 정렬 알고리즘 중 가장 비효율적인 성능을 보임

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


4. 알고리즘 표현 (오름차순 기준)

  ㅇ 개선전 버블 정렬  
      
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. 퀵 정렬  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"