algorithmsort

알고리즘 | 버블정렬

sort

버블정렬(Bubble Sort)

  • 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행
  • 제일 큰 원소를 오른쪽으로 옮기는 방법
  • 버블 정렬의 비교 횟수
    = (n-1)+(n-2)+…+(n-(n-2))+(n-(n-1))
    = (n-1)+(n-2)+…+3+2+1 = (n-1)(n/2)
    비교횟수 T(n)= (n    (n-1))/2
  • 시간복잡도
    • 평균, 최악, 최고: O(n^2)
    • 기존의 레코드들이 정렬이 되어 있던, 되어 있지 않던 상관 없이 레코드들의 가장 처음부터 끝까지 비교하는 과정이 모두 같기 때문
    • 개선 방안 -> 정렬되어있는 경우 루프를 취소하고 빠져나오도록 하는 방법
  • 공간복잡도: O(1)

동작원리

  1. 이웃 하는 두 레코드를 비교하여 큰 레코드는 우측으로 밀어낸다.
  2. 더 이상 이웃 하는 레코드가 없을 때까지 반복한다.
  3. 리스트의 가장 우측부터 큰 레코드로 정렬이 된다.
  4. 모든 레코드가 정렬이 될 때까지 반복한다.

예제코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BubbleSort()
{
  int DataSet[]={6,4,2,3,1,5};
  int Length =sizeof(DataSet)/sizeof(DataSet[0]);
  for(int i=0; i<Length-1; i++){
    for(int j=0; j<Length-(i+1); j++){
      if(DataSet[j]> DataSet[j+1]){ //인접한 두 값을 비교
      //정렬되지 않은 두 값
      temp = DataSet[j+1];
      DataSet[j+1]=DataSet[j];
      DataSet[j]=temp;
      }
    }
  }
}
Share