정렬알고리즘_선택정렬

정렬알고리즘

정렬이란 임의의 순서대로 배열되어 있는 자료의 집합을 일정한 순서대로 재배열하는 것을 의미

 

정렬의 방법론

= > 판단과 교환을 어떻게 적절히 조합하는가에 대한 방법론.

 

정렬을 하는 대상을 파일이라고 하며, 이 파일은 정보의 단위인 레코드의 나열이다.

아래 정보를 가지고 있는 인사기록 카드를 정렬하려고 했을 경우 카드 각 한장은 레코드, 레코드의 정보를 가지고 있는 사번, 성별,나이 등은 필드라고 한다.

정렬을 하려면 키가 있어야한다. ‘비교’의 대상이 되는 것은 레코드 중에서 키값이며, ‘교환’의 대상이 되는 것은 레코드 자체가 된다. 사원번호 정도가 ‘키’가 될 수 있겠다.

 

 

선택 정렬(Selection Sort)

 

순서대로 정렬하는 가장 간단한 정렬 알고리즘.

선택 정렬 알고리즘

선택정렬 특징:

첫 번째  배열의 앞 부분부터 정렬을 차례로 해나간다.

두 번째 정렬을 아직 하지 않은 부분은 n의 변함이 없다.

선택 정렬의 비교 횟수는 최소값을 찾기 위해서 N2/ 2 정도로 많지만 교환 횟수는 많아야 N번이다.

 

안정성 문제

안정성이란 같은 키의 상대적 순서가 정렬 후에도 변함이 없음을 뜻한다.

하지만 선택 정렬은 안정성이 없다.

인접한 배열 요소를 교환하는 것이 아닌 뚝 떨어진 요소와도 교환이 되기 때문이다.