[알고리즘] 선택정렬

안녕하세요. 오늘은 가장 간단하고 직관적인 정렬 알고리즘인 선택정렬에 대한 개념과 코드에 대해 설명하겠습니다. 그럼 집중!! 

 

 

선택 정렬 개념

---

선택 정렬은 주어진 배열에서 가장 작은 값을 찾아서 해당 값이 위치해 있는 인덱스와 첫 번째 원소를 서로 교환하고, 그 다음으로 작은 값을 찾아서 해당 값이 위치해 있는 인덱스와 두 번째 원소를 교환하는 과정을 반복하여 정렬을 수행하는 알고리즘입니다.

 

 

선택 정렬이 작동되는 방법

---

1. 정렬되지 않은 리스트에서 가장 작은 원소를 찾습니다.

2. 그 원소를 리스트의 맨 앞에 위치한 리스트와 교환합니다.

3. 맨 처음 위치를 제외한 나머지 리스트를 정렬되지 않은 리스트로 간주하고 위 과정을 반복합니다.

 

 

선택 정렬 코드

---

#include <stdio.h>
int main() {
	int n, arr[100]={0};
	
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%d", &arr[i]);
	}
	
	for (int i = 0; i < n - 1; i++)
    {
        int indexMin = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[indexMin])
            {
                indexMin = j;
            }
        }
        int temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }
	
	for(int i=0; i<n; i++) {
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

코드 설명

---

배열에 들어갈 숫자의 수를 n에 넣고, n만큼 반복문을 실행하며 숫자를 입력 받으며 배열에 넣습니다.

 

int n, arr[100]={0};
	
scanf("%d", &n);
for(int i=0; i<n; i++) {
	scanf("%d", &arr[i]);
}

 

indexMin이라는 변수에 i를 넣습니다. i는 반복문에 따라 0에서 n-1보다 작을때 까지 계속 바뀝니다..! 그리고 반복문을 한 개 더 실행하는데 i+1부터 n보다 작을때 가지 실행 되는 반복문입니다. 그런데 만약 배열의 j번째 숫자가 indexMin번째 숫자보다 작다면 indexMin 변수에 j를 넣습니다. 그리고 안에 있는 반복문 전체가 끝났다면..? 배열의 indexMin번째 숫자와 배열의 i번째 숫자를 교환합니다. 

 

for (int i = 0; i < n - 1; i++)
{
    int indexMin = i;
    for (int j = i + 1; j < n; j++)
    {
         if (arr[j] < arr[indexMin])
         {
              indexMin = j;
         }
    }
    int temp = arr[indexMin];
    arr[indexMin] = arr[i];
    arr[i] = temp;
}

 

배열 전체를 출력합니다.

 

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

 

 

 

 

 

다음 글은 삽입정렬에 대한 글을 가지고 오겠습니다! 모두 즐거운 하루 보내세요 🤗