[알고리즘] 선택 정렬

선택 정렬

정렬을 위한 알고리즘 중 하나이며, 

배열 안의 자료 중 가장 작은 수 (혹은 가장 큰 수)를 찾아서 첫 번째 위치(혹은 가장 마지막 위치)의

수 와 교환해주는 방식의 정렬

 

 

예를 들어,

 

6 3 8 5 2 7 4 1  

 

이렇게 정렬되지 않은 숫자들을 오름차순으로 정렬하려고 한다면

 

6 3 8 5 2 7 4 1

 

비교기준이 되는 6을 제외한 나머지 숫자들중 가장 작은 수를 찾아낸다 (가장 작은 수: 1)

찾아낸 가장 작은수를  비교기준으로 설정한 6 과 자리를 바꿔준다.

 

1 3 8 5 2 7 4 6

 

그럼이제 정렬되어있는 1을 제외하고, 두번째 숫자부터 시작해서 가장 작은 값을 찾는다.(가장 작은 수: 2)

찾아낸 가장 작은수를 2 와 바꿔준다.

 

1 2 8 5 3 7 4 6 

 

이 과정을 오름차순 정렬 완료 될때까지 반복한다.

 

#include <stdio.h>
#define SIZE 8
int main()
{
    int arr[SIZE] = {6,3,8,5,2,7,4,1};
    int min;
    int temp;


    //올바른 예시
    for(int i = 0; i < SIZE-1; i++) // 마지막 인덱스는 비교 대상이 없으니 SIZE - 1 (i = 7 일때 앞에 인덱스들의 정렬이 완료 되어 정렬할 필요 x)
    {   
        min = i; //인덱스의 위치를 변경해야 하니 값을 저장하는 것이 아니라 위치에 관한 인덱스를 저장해야 한다.

       for(int j = i+1;  j < SIZE; j++) //예를들어 arr[0] 이라면 우리는 arr[1] 부터 arr[7]까지 모든 인덱스를 비교해야하기 때문
       {
           if(arr[min] > arr[j])
            {
               min = j;
            }
        }

            //모든 원소들을 거쳐 최소값인 인덱스의 번호를 찾았다면 비교기준으로 설정했던 인덱스의 위치와 바꾼다.
       
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
    }

    for(int i = 0; i < SIZE; i++)
       {
           printf("%d", arr[i]);
       }
       
    return 0;
}


    //틀린(?) 예시
    //위의 코드는 모든 탐색을 마친후 위치를 변경하는 반면, 이 코드는 인덱스를 탐색할때 마다 위치를 변경한다.
    /*
    for(int i = 0; i < SIZE-1; i++)
    {
       for(int j = i+1;  j < SIZE; j++)
       {
           if(arr[i] > arr[j])
            {
                min = arr[j];
                arr[j] = arr[i];
                arr[i] = min;
            }
       }

       for(int k = 0; k < SIZE; k++)
       {
           printf("%d", arr[k]);
       }
       printf("\n");
    }
    return 0;
}
*/

 

소스 코드 실습중 아래 코드와 헷갈려서  실수했던 코드까지 작성해 봤다