선택 정렬

• 가장 먼저 생각이 날 수 있는 자연스러운 정렬 알고리즘
• 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식

수행 방법

• 전체 원소 중에서 가장 작은 원소를 찾아 첫 번째 원소와 자리를 교환
• 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환
• 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환

→ 이 과정을 반복하면서 정렬을 완성

예시 : [4, 2, 7, 1, 9, 3]

• [1, 2, 7, 4, 9, 3]

• [1, 2, 7, 4, 9, 3]

• [1, 2, 3, 4, 9, 7]

• [1, 2, 3, 4, 9, 7]

• [1, 2, 3, 4, 7, 9]

• [1, 2, 3, 4, 7, 9]

• 비교 횟수

  • 1단계 : 첫 번째 원소를 기준으로 n개의 원소 비교
  • 2단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교
  • 3단계 : 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교

• 상황에 영향을 받지 않고 일정한 시간이 소요된다.