Prosto

선택 정렬(Selection Sort) - C언어/자료구조 본문

Programing/C Programing

선택 정렬(Selection Sort) - C언어/자료구조

Prosto 2016. 10. 17. 23:42

'선택하여 차례대로 정렬하는 선택정렬'

 

선택 정렬은 데이터를 정렬하는 방법 중 가장 기본적인 방법으로

첫 번째 자료부터 마지막 자료까지 하나씩 순서대로 정렬해가는 방식입니다.

 

오름차순이라면 가장 낮은 숫자가 첫 번째, 가장 높은 숫자가 마지막이 되겠죠?

(내림차순이라면 그 반대의 결과가 나오겠죠?)

 

 

그렇다면 이 선택 정렬은 어떻게 이루어지는 걸까요?

 

 

오름차순을 기준으로 이야기하자면 이렇습니다.

 

첫 번째 위치인 가장 낮은 값을 찾기 위해서

 두 번째부터 마지막까지 낮은 값을 확인하여 첫 번째 값을 결정합니다.

 그 과정에서 현재 위치의 값보다 작은 값을 만나면 서로의 값을 교환해줍니다.

 

그 후 두 번째로 낮은 수를 찾기 위해서

 세 번째부터 마지막까지 현재 두 번째 자리의 수보다 낮은 값이 있는지 확인하죠.

 마찬가지로 작은 값을 만나서 서로 값을 교환해줍니다.

 

그렇게 세 번째, 네 번째... 마지막 위치까지 교환을 거쳐서

최종적으로 오름차순으로 정렬된 결과를 받는 정렬 방법입니다.

 

 

실제로 5개의 숫자 배열 자료가 어떻게 정렬되는지 확인해볼까요?

 

 

7, 4, 10, 3, 5 숫자를

오름차순으로 정렬하는 과정을 보도록 하겠습니다.

 

 

가장 먼저 첫 번째 위치를 기준으로 시작됩니다.

현재 첫 번째 위치의 숫자가 7이고,

두 번째 위치의 숫자가 4입니다.

비교 결과 4가 더 작은 숫자이기 때문에 숫자 7과 4를 바꿔줍니다.

 

 

첫 번쨰 위치의 숫자가 4가 되었습니다.

다음으로 세 번째 자리인 10과 비교합니다.

비교 결과 기존의 숫자인 4가 더 작기 때문에 바꾸지 않습니다.

 

 

다음 자리인 네 번째 숫자 3과 비교합니다.

비교 결과 기존의 숫자인 4보다 3이 작기 때문에 바꿔줍니다.

 

 

다음 자리인 다섯 번째 숫자 5와 비교합니다.

비교 결과 기존의 숫자인 3보다 크기 때문에 바꿔지 않습니다.

 

 

이렇게 첫 번째 자리의 가장 낮은 숫자는 3으로 결정됐습니다.

 

그 후 두 번째 바퀴를 돕니다.

두 번째 자리의 7과 세 번째 자리의 10을 비교합니다.

비교 결과 기존의 숫자인 7이 더 작기 때문에 바꾸지 않습니다.

 

 

다음으로 네 번째 자리의 4와 비교합니다.

비교 결과 기존의 숫자인 7보다 4가 더 작기 때문에 바꿔줍니다.

 

 

다음으로 다섯 번째 자리의 5와 비교합니다.

비교 결과 기존의 숫자인 4가 더 작기 때문에 바꾸지 않습니다.

 

 

이렇게 두 번째로 작은 숫자인 4도 결정되었습니다.

 

그리고 세 번째 바퀴를 돕니다.

세 번째 자리의 10과 네 번째 자리의 7을 비교합니다.

비교 결과 기존의 숫자(10)보다 7이 더 작기 때문에 바꿔줍니다.

 

 

기존의 숫자 7과 다섯 번째 자리의 5를 비교합니다.

비교 결과 기존의 숫자(7)보다 5가 더 작기 때문에 바꿔줍니다.

 

 

이렇게 세 번째로 작은 숫자인 5도 결정되었습니다.

 

그리고 네 번째 바퀴를 돕니다.

네 번째 자리의 10과 다섯 번째 자리의 7을 비교합니다.

비교 결과 기존의 숫자(10)보다 7이 더 작기 때문에 바꿔줍니다.

 

 

이렇게 네 번째 작은 숫자와 마지막 숫자가 나왔습니다.

 

다섯 번째 자리는 비교 대상이 없기 떄문에

정렬이 완료됩니다.

 

 

 

 

 

 

 

그러면 이번에는 C 프로그램으로 확인해볼까요?

 

원하는 출력 결과를 보고

프로그램 소스를 작성해보세요.

(출력 결과 예)

 


 

제가 완성한 소스입니다.

 

보고 참고하세요.

 

(복사할 수 있는 소스는 아래 전체복사용보기를 누르시면 됩니다.)

 

 

 

 

 

 

궁금한 점 있으시면 댓글이나 따로 메일로 질문하시면 시간되는 대로 답변드리겠습니다. ( 연락 )

 

Comments