Bubble Sort   버블 정렬

(2019-12-22)

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. 퀵 정렬
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 순서도
            3. 재귀 호출
        1.   알고리즘 효율성
        2.   알고리즘 종류
              1. 알고리즘 분류
              2. 그래프 알고리즘
          1.   기초 알고리즘
          2.   정렬 알고리즘
            1.   1. 정렬 알고리즘
                2. 버블 정렬
                3. 선택 정렬
                4. 삽입 정렬
                5. 병합 정렬
                6. 퀵 정렬
          3.   검색 알고리즘
        3.   알고리즘 전략
        4.   (기타 알고리즘)
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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