[Algorithm] 정렬 알고리즘 (선택 정렬)

1. 정렬 알고리즘?

 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

• 데이터의 개수가 적을 때
• 데이터의 개수가 많으면서 범위가 한정되어 있을 때
• 이미 데이터가 정렬되어 있을 때

---

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

선택 정렬 과정

Step 0 : 정렬할 데이터를 준비한다.

 Step 1 : 처리되지 않은 데이터 중 가장 작은 '1' 을 선택해 가장 앞의 '5' 와 바꾼다.

Step 2: 처리되지 않은 데이터 중 가장 작은 '2' 를 선택해 가장 앞의 '5' 와 바꾼다.

Step 3: 처리되지 않은 데이터 중 가장 작은 '3' 을 선택해 가장 앞의 '4'와 바꾼다.

위와 같이 순서대로 정렬된 것을 볼 수 있다. 이를 python 코드로 좀 더 많은 데이터를 통해서 구현한 내용은 아래와 같다.

python으로 구현한 선택 정렬

출력 결과

선택 정렬의 시간 복잡도

 선택 정렬은 N번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 따라서 전체 연산 횟수는 다음과 같다.