Bubble Sort (거품 정렬)

Bubble Sort (거품 정렬)

• 인접한 두 인덱스를 비교하여 위치를 교환해가며 정렬하는 방식.

• 코드가 단순하다.

• 연산 횟수가 많아 데이터 수가 많아질수록 성능이 저하된다.

• 시간복잡도 : T(n) = n(n-1)/2 = O(n^2)

• 동작 순서 (최소 선택 정렬을 예시로 함.)

  1. 첫번째 인덱스부터 인접한 2개의 인덱스를 비교하여 순서가 맞지 않으면 위치를 교환한다.
  2. 가장 큰 값이 마지막 인덱스에 위치하므로, 배열의 크기 N - 시행순서 n 까지 반복한다.

• Code

  #include <stdio.h>
  #define ARRAY_SIZE 10
  //Logic 부--------------------------------------------
  void bubble_sort (int array[], int n)
  {
      int temp=0;                                       // 자리 교환을 위한 정수형 변수 temp 선언 및 초기화
      for(int i=0;i<n-1;i++)                            // n-1 만큼 반복
      {
          for(int j=0;j<n-i-1;j++)                      // n-i-1 만큼 반복
          {
              if(array[j]>array[j+1])                   // array[j] 값이 array[j+1]보다 큰 경우
              {
                  temp = array[j];
                  array[j] = array[j+1];
                  array[j+1] = temp;                    // 자리 교환
              }
          }
      }
  }
  //Main 부---------------------------------------------
  void main()
  {
      int Arr[ARRAY_SIZE] = {3,8,7,4,0,1,5,2,6,9};      // 임의의 배열 Arr 선언
      bubble_sort(Arr, ARRAY_SIZE);                     // bubble_sort 함수 실행
      for(int i=0;i<ARRAY_SIZE;i++)                     // ARRAY_SIZE 만큼 반복
      {
          printf("%d",Arr[i]);                          // 거품 정렬 된 배열 출력
      }
  }

  Output : 0    1    2    3    4    5    6    7    8    9