Select Sort (version2)

1. 설명

정렬의 기준은 오름차순이다.

정렬을 할 배열을 A[n]이라 한다.

배열 A[1...n]에서 가장 큰 원소를 찾아, 이 원소와 배열의 맨 끝자리에 있는

A[n]과 자리를 바꾼다.

그러면 방금 맨 뒷자리로 옮긴 원소, 즉, 가장 큰 원소는 자기 자리를 찾았으므로, 더 이상

신경 안써도 된다. 이 원소는 정렬이 끝났다고 볼 수있으므로,

이제 이 원소를 제외한 나머지 원소들도 같은 작업을 반복하면 된다. 

 

아래는 선택 정렬 알고리즘 의사코드

위의 알고리즘을 풀어서 쓴 의사코드

알고리즘의 입력은 정렬해야할 배열 A[1...n]이다.

위의 알고리즘 식 알파에서 변수last는 정렬할 배열의 맨 마지막 인덱스,

즉, 배열의 크기를 나타낸다.

처음에는 배열의 크기가 n으로 시작하므로, A[1...n]을 정렬 대상으로 삼는다.

가장 큰 수를 찾아 제자리에 놓을 때마다 last는 1씩 줄어든다.

알파의 for루프는 정렬할 배열의 크기를 한 번에 하나씩 줄여 나가는 역할을 한다.

즉, 맨 처음에는 배열의 크기가 n으로 시작하여, 그 다음 루프에서는 n-1이 되며

정렬할 배열은 A[1...(n-1)]이 된다. 이와 같은 방식으로 줄어든다.

마지막에는 크기가 2인 배열 A[1...2]의 두 원소 중 큰 원소를 A[2]에 놓고 나면

A[1]에는 가장 작은 원소가 자리잡게 된다. 이로써 정렬이 끝난다. 

 

2. 구현

프로그램 실행결과

3. 소스 파일

main.c

0.00MB