[자료구조] 선택정렬(Selection Sort)에 대하여

Data_Structure

 

 

 

 

 

 

 

 

 

선택정렬에 대하여

About. Selection Sort

 

 

---

 

 

 

정의: 1개이상의 서로 다른 정수를 가장 작은순서부터 배열하는 정렬

 

 

배열할때 가장 작은 수부터 배열하고싶으면, 가장 작은 숫자를 찾아서 맨 처음, 그다음은 두번째, 세번째...순으로 나열해주면 되겠죠.

 

기본적인 아이디어를 표현하면 다음과 같습니다.

 

 

 

 

 

 

이를 코드로 간단하게 표현하면 다음과 같습니다.

 

for ( i = 0; i < n; i++){
	list[i]에서부터 list[n-1]까지의 정수값을 검사한 결과
   	list[min]이 가장 작은 정수값이라하자;
    
    list[i]와 list[min]을 서로 교환;
}

참고로 이렇게 자연어와 프로그래밍언어가 섞인 코드를 '의사코드'라고 합니다.

 

 

그러면 이를 구현하려면 필요한 것이 무엇이 있을까요?

 

우선 n에 해당하는 리스트의 크기가 필요하고, 리스트 자체가 필요하며

마지막으로 최솟값을 교환하는 함수가 필요하겠네요.

 

 

다음은 선택정렬을 구현한 코드입니다.

 

 

 

 

#include <stdio.h>
#define swap(a, b, tmp){(tmp) = (a); (a) = (b); (b) = (tmp);}

void selec_sort(int *list, int n);

int main() {
	int n, *list;

	printf("배열의 크기는? ");
	scanf(" %d", &n);

	//malloc으로 동적할당을 해준 모습인데, 이는 list를 동적할당해주기 위함이고
	//동적할당을 쓰지 않으시려면 그냥 list를 큰값으로 설정해주시면 됩니다. ex) list[100]
	list = malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) {
		printf("%d번째 숫자를 입력해주세요: ", i + 1);
		scanf("%d", &list[i]);
	}
	/*for (int i = 0; i < n; i++) {
		printf(" %d", list[i]);
	}*/

	selec_sort(list, n);
}

void selec_sort(int *list, int n) {
	int i, j, tmp;
	int min;

	for (i = 0; i < n; i++) {
		min = i;
		for (j = i; j < n; j++) {
			if (list[min] > list[j]) {
				min = j;
			}
		}
		swap(list[min], list[i], tmp);
	}

	printf("정렬된 배열: ");
	for (i = 0; i < n; i++) {
		printf("%d ", list[i]);
	}
}

 

참고로 c언어 자체에 익숙하지 않다면, 함수로 따로 구현하지 말고 main함수에 다같이 구현하는것도 좋을 것 같습니다.

하지만 함수로 구현해서 작성하는데 함수와 포인터에 대한 이해를 돕습니다.

 

 

 

 

아래 링크들은 제가 코딩하다가 만난 에러들입니다. 혹시라도 겹치면 찾아가보시길ㅎ

 

 

https://dokhakdubini.tistory.com/171

[C언어 오류] 에러코드 C2371:: (함수명):재정의. 기본 형식이 다릅니다.

https://dokhakdubini.tistory.com/173

[C언어오류] 예외가 발생함:: 예외가 throw됨: 읽기 액세스 위반입니다.