선택 정렬

-설명

정렬 방법 중 하나로써 갖고 있는 값들 중 최솟값을 선택해서(찾아서) 가장 왼쪽에 있는 값과 바꾸고, 그 다음으로 작은 수를 선택해서 그 다음 왼쪽에 있는 값과 하나하나씩 바꾸어가며 정렬하는 방법.

 

-선택 정렬이 갖는 특징

구현이 간단하다.

알고리즘의 시간 복잡도가 O(N^2) 이다.

-> 데이터의 수가 N이라면 그중 최솟값을 찾는 작업에 드는 시간 N. 이를 값들 중 왼쪽에 있는 값과 교환

     모든 데이터 정렬을 위해 해당 작업을 N번 반복

 

-예

데이터 : 1 2 5 8 11 51 3 7

1번 반복 : 1 2 5 8 11 51 3 7  (1이 최솟값이라 변화 없음)

2번 반복 : 1 2 5 8 11 51 3 7  (2가 최솟값이라 변화 없음)

3번 반복 : 1 2 3 8 11 51 5 7  (3번째 최솟값과 왼쪽에서 3번째 인덱스에 있는 값과 교환)

4번 반복 : 1 2 3 5 11 51 8 7

5번 반복 : 1 2 3 5 7 51 8 11

6번 반복 : 1 2 3 5 7 8 51 11

7번 반복 : 1 2 3 5 7 8 11 51

 

-코드(C++)