버블정렬(거품정렬 : Bubble sort) - C++로 버블정렬 하는 방법을 알아보자.

C/C++기초 2010. 9. 11. 16:06

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다.
시간 복합도가 O(n2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
- 출처 : 위키백과

수열 "10 9 4 8 5 1 7" 을 버블 정렬을 이용하여 오름차순으로 정렬하는 방법은 다음과 같다.
결과)



소스) 
#define SWAP(x, y) {int t=x; x=y; y=t;}

int main()
{
    int a[7]={10, 9, 4, 8, 5, 1, 7};
    int i, j;

    for (i=1; i<7; i++){
        for (j=0; j<7-i; j++){
            if (a[j] > a[j+1])SWAP(a[j], a[j+1]);
        }
    }

    for (i=0; i<7; i++){
        printf ("%d ", a[i]);
    }

    return 0;
}
다음 수열 "10 9 4 5 6 7 8" 은 두번만에 정렬이 끝나게 된다. 이런경우 나머지 5번의 작업은 의미가 없다.
정렬작업 중 정렬이 다 되었으면 작업을 마치는 방법은 다음과 같다.
결과) 


 소스) 

#define SWAP(x, y) {int t=x; x=y; y=t;}

int main()
{
    int a[7]={10, 9, 4, 5, 6, 7, 8};
    int i, j, flag;

    for (i=1; i<7; i++){
        flag=0;
        for (j=0; j<7-i; j++){
            if (a[j] > a[j+1]){
                SWAP(a[j], a[j+1]);
                flag=1;
            }
        }
        if (flag==0) break;
    }

    for (i=0; i<7; i++){
        printf ("%d ", a[i]);
    }

    return 0;
}


저작자표시 비영리 변경금지 (새창열림)

'C/C++기초' 카테고리의 다른 글

비트 연산자, AND OR XOR NOT 쉬프트 연산자를 알아보자  (2) 2010.10.04
하노이의 탑  (0) 2010.09.28
삽입정렬(Insertion sort) - 삽입정렬을 구현해보자  (0) 2010.09.18
선택정렬(Selection sort) - C++로 선택정렬을 구현해보자  (3) 2010.09.10
최대공약수, 최소공배수 구하기  (0) 2010.09.06
Posted by 파이군
,

선택정렬(Selection sort) - C++로 선택정렬을 구현해보자

C/C++기초 2010. 9. 10. 16:00

선택 정렬(選擇整列, selection sort)은 내부정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1.주어진 리스트 중에 최소값을 찾는다.
2.그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3.맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
-출처 : 위키백과

5개의 정수 95, 75, 85, 100, 50 을 오름차순으로 정렬한다.
결과)



소스) 

int main()
{
	int a[5] = {95, 75, 85, 100, 50};
	int i, j, tmp;

	// 정렬
	for (i = 0; i < 4; i++){
		for (j = i + 1; j < 5; j++){
			if (a[i] > a[j]){
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}
	}

	//출력
	for (i = 0; i < 5; i++){
		printf("%d ", a[i]);
	}

	return 0;
}
* #define 사용해서 배열의 값을 바꿀수도 있다.

소스) 
#define SWAP(a, b) { int t = a; a = b; b = t; } 

int main()
{
    int a[5] = {95, 75, 85, 100, 50};
    int i, j, tmp;

    // 정렬
    for (i = 0; i < 4; i++){
        for (j = i + 1; j < 5; j++){
            if (a[i] > a[j]) SWAP(a[i], a[j]);
       }
   }

    //출력
    for (i = 0; i < 5; i++){
        printf("%d ", a[i]); 
    }

    return 0;
}
내림차순을 할때는 if()의 조건만 반대로 해주면된다. 오름차순으로 정렬된것을 거꾸로 출력하는 방법도 있다.
저작자표시 비영리 변경금지 (새창열림)

'C/C++기초' 카테고리의 다른 글

비트 연산자, AND OR XOR NOT 쉬프트 연산자를 알아보자  (2) 2010.10.04
하노이의 탑  (0) 2010.09.28
삽입정렬(Insertion sort) - 삽입정렬을 구현해보자  (0) 2010.09.18
버블정렬(거품정렬 : Bubble sort) - C++로 버블정렬 하는 방법을 알아보자.  (2) 2010.09.11
최대공약수, 최소공배수 구하기  (0) 2010.09.06
Posted by 파이군
,

티스토리툴바