[정렬] 버블정렬

안녕하세요. playground입니다~

이번에는 정렬 중 버블정렬에 대해 포스팅하겠습니다.

 

 

 

버블정렬

 

사실 정렬 3대장(삽입, 버블, 선택) 중 <- 내가 생각한 3대장.....

개인적으로 가장 개념적으로 이해하기 쉬우면서 안 헷갈리는 정렬 같습니다.

인접한 두 원소를 차례대로 비교하면서 자리바꾸고 반복시키면서 정렬시키는 방식 으로

비누거품(버블)이 일어나는 듯한 모습과 비슷해 버블정렬이라고 합니다.

 

 

 

 

 

 

버블정렬의 풀이

 

 

1. 위 배열이 있으면 맨 오른쪽 85를 시작점으로 합니다.

 

 

 

 

 

2. 85와 옆에 인접한 1을 비교했을 때 1이 작으므로 정렬된 상태가 맞습니다.

   그러므로 넘어가고 1을 기준으로 잡고

   옆에 인접한 66과 비교 -> 66이 크므로 교환

   옆에 인접한 11과 비교 -> 11이 크므로 교환

..... 이런식으로 해주면 1이 맨 왼쪽에 오고 한 번 정렬이 끝났습니다.

 

 

 

 

 

 

3. 오른쪽부터 다시 비교하기 시작해 11이 99보다 작으므로 교환해줍니다.

   그 다음 인접한 77과 비교 및 교환을 해서 쭉 오다가 7보다 크므로 멈춥니다.

   그리고 7을 기준으로 인접한 원소인 50과 비교해 교환, 교환해주다가 1보다 크므로 멈추고 pass끝.

 

 

이런식으로 인접한 원소와 비교해 정렬하는 것을 버블정렬이라고합니다.

 

 

 

 

 

 

버블정렬의 알고리즘

 

 

BubbleSort(int _iArr[], int _n) {      int iBound = -1;      int iTop = 0;      do      {           iTop = _n;           for(int j = iTop - 1; j > iBound; --j) // 오->왼으로 비교           {                if( _iArr[j] < _iArr[j - 1] ) // 비교                {                     int iTemp = _iArr[j];                     _iArr[j] = _iArr[j-1];                     _iArr[j-1] = iTemp;                     iTop = j;                }            }     // pass정렬완료           iBound = iTop;      }      while( iTop < _n )      }

 

 

 

 

 

 

버블정렬의 성능

 

 

이중 루프로 구성되며 바깥 루프는 조건에 따라 최소로는 상수, 최대로는 n과 비례합니다.

안쪽 루프는 n에 비례해 

최선일 경우는  O(n) , 최악은 O() 이다.

 

평균 O()

 

 

 

 

 

버블정렬에 대해 포스팅을 했는데요~ 도움이 되셨으면 좋겠습니다.

감사합니다~