선택정렬 Selection sort

정렬 알고리즘은 크게 크기에 의한 분할 후 정렬과, 특정 값에 의한 분할 후 정렬로 나눌 수 있다.
크기에 의한 분할에는 삽입 정렬(insertion), 병합 정렬(merge)이 있다.
특정 값에 의한 정렬에는 선택 정렬(selection), 힙 정렬(heap), 퀵 소트 등이 있다.

---

선택정렬 Selection sort *최솟값의 인덱스!!

선택정렬은 최소값을 기준으로 배열을 나눈다.
기초 원리는 arr[0]과 나머지 중 최소값 스왑.
arr[1]과 나머지 중 최소값 스왑. ... arr[n-2]와 나머지 중 최소값 스왑.
즉 n-1번 반복.
반복 한번 할때마다 앞부분은 정렬 됨.

---

public class Main
{
	public static void main(String[] args) 
	{
              int[] arr = {1,5,2,4,6,9,8};

              for (int k=0; k<7; k++)
              {
                  System.out.print(arr[k]+ " ");
              }
              System.out.println();

              int min, temp; // min은 최솟값의 인덱스
              int n=7;
              for (int i=0; i<n-1; i++)
              {
                  min = i;
                  for (int j=i+1; j<n; j++)
                  {
                      if (arr[j] < arr[min])
                      {
                          min = j; // 최솟값 인덱스를 계속 갱신
                      }
                  }
		// 두번째 반복문이 다 돌고 스왑
                  temp = arr[min];
                  arr[min] = arr[i];
                  arr[i] = temp;

              }

              for (int k=0; k<7; k++)
              {
                  System.out.print(arr[k]+ " ");
              }
     	 }
  }

---

시간복잡도

첫번째는 6번, 두번째는 5번 ... 7번째는 1번 비교를 한다.
즉 (n-1) + (n-2) + ... 1번 = n(n-1)/2 비교하므로 시간 복잡도는 O(n²)이다.

---

선택 정렬은 빠른 알고리즘은 아니지만 배열 요소들 간 교환은 n-1번 이뤄진다. 요소들 간의 교환이 적기 때문에 (입력 크기 작고) 배열 요소들 간 교환 비용이 큰 경우 적절하다.