[알고리즘] 선택정렬

선택정렬이란

• 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 알고리즘이다.

논리

• 0번 인덱스를 최소 값이라고 가정한다.
• 0번 인덱스를 마지막 인덱스까지 비교한다.
• 0번 인덱스 보다 작은 값이 있다면 자리를 교체한다.
• next
• 1번 인덱스를 최소 값이라고 가정한다.
• 1번 인덱스를 마지막 인덱스까지 비교한다.
• 1번 인덱스 보다 작은 값이 있다면 자리를 교체한다.
• next
• ....

이미지로 보기

특징

• 알고리즘이 단순하다.
• 비교 횟수는 많지만, 실제로 교환하는 횟수는 적다.
  • 교환이 많이 일어나는 상황에서 효율적이다.

단점

• 불안정 정렬이다.
  • 중복 값이 있을 경우 위치 보존이 안된다.

예제

• [5,3,1,4,2]가 [1,2,3,4,5]가 되도록 정렬한다.

예제 코드

// 배열 선언
int[] datas = new int[5];

// 값 넣기
datas[0] = 5;
datas[1] = 3;
datas[2] = 1;
datas[3] = 4;
datas[4] = 2;

// 마지막 자리는 자동 정렬 되므로 arr.length - 1
for (int i = 0; i < datas.length - 1; i++) 
{

    // 현재 인덱스 값을 최소값이라 가정
    int minIndex = i;

    // 기준 값을 마지막 인덱스 값까지 비교한다.
    for (int j = i + 1; j < datas.length; j++) 
    {

        // 기준 값이 더 크다면
        if (datas[j] < datas[minIndex]) 
        {

            // 최소값 교체
               minIndex = j;

        }

    }

     // 기준 값을 임시저장
    int temp = datas[i];

    // 기준 값 자리에 최소값을 넣기
    datas[i] = datas[minIndex];

    // 최소값 자리에 기준 값 넣기
    datas[minIndex] = temp;

}

//출력
for(int data : datas) 
{

    System.out.print(data + " ");

}