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

선택 정렬(選擇整列, 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()의 조건만 반대로 해주면된다. 오름차순으로 정렬된것을 거꾸로 출력하는 방법도 있다.