[알고리즘] 버블 정렬 bubble sort / flag

버블 정렬

• 주요 특징
  • 여러 명칭 : sinking/ripple/exchange/shifting 등
  • 인접한 두 원소들을 서로 비교, 필요시 교환
  • 각 단계에서 대상 원소 중 최대값이 제일 뒤로 이동
    (cf) 적용방법에 따라, 최소값이 처음으로 이동 가능
    • K단계 적용 후, 뒤쪽 k개는 이미 정렬됨
• 복잡도 분석
  • K번째 단계의 비교 회수 : (n-k)회
  • 전체 비교 회수 : (n-1)+(n-2)+…+2+1 = O(n^2)
    (cf) 자료 교환 회수는 기본적으로 비교 회수와 동일
• 문제점 및 개선
  • 한자료가여러번교환될수있음 (cf) 선택정렬
  • 이미 정렬된 경우에도 계속 수행 -> flag 이용 

 

#include <iostream>
using namespace std;

const int SIZE = 15;
int L[SIZE] = {10,4, 7, 1, -2, 12, 28, 66, 9, 3, 5, 7, 6, 21, 11 };


void print_data()
{
	for (int i = 1; i <= SIZE; i++)
		cout << " " << L[i] << " ";
	cout << endl;
}

void bubble_sort()
{
	int i, j,flag;
	int temp;

	for (i = SIZE; i>1; i--)
	{
		flag = 0;
		for(j=2; j<=i; j++)
			if (L[j - 1] > L[j])
			{
				temp = L[j - 1];
				L[j - 1] = L[j];
				L[j] = temp;
				flag++;
			}
		if (flag == 0) break;
	}
}

void main()
{
	cout << "Input Data : ";
	print_data();

	bubble_sort();

	cout << "\n\nSorted Data : ";
	print_data();
}

 

Flag가 있는 버블  정렬

void bubble_sort(data A[], int n) {
	int i, j, flag; 
    data temp;

	for(i = n; i > 1; I--) { /* i >= 1 */
		flag = 0;
		for(j = 2; j <= i; j++) 
        	if(A[j-1] > A[j])
			{ // swap A[j] and A[j-1] 
            	temp = A[j-1];
				A[j-1] = A[j]; 
                A[j] = temp; 
                flag++;
			}
		if(flag == 0) break; 
	}
}

 

• 개선 : 이미 정렬된 경우, 진행 중단, 결과 출력
• 비교회수
  • 최상의 경우(입력이 이미 정렬된 경우) : n-1
  • 최악의 경우(마지막 원소가 최소값인 경우) : n(n-1)/2