선택정렬, 이진탐색, 순열

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 101
#define SWAP(x,y,t) (t=x,x=y,y=t)
void sort(int[], int);
void main() {
	int i, n, list[MAX_SIZE];
	printf("Enter the number of numbers to generate:");
	scanf_s("%d", &n);
	if (n<1 || n>MAX_SIZE) {
		printf("ERROR");
	}
	for (i = 0; i < n; i++) { //n개의 정수를 랜덤으로 생성
		list[i] = rand() % 1000;
		printf("%d ", list[i]);
	}
	sort(list, n);
	printf("\n Sorted array:\n");
	for (i = 0; i < n; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");
}

void sort(int list[], int n) { //선택정렬
	int i, j, min, temp;
	for (i = 0; i < n - 1; i++) {
		min = i;
		for (j = i + 1; j < n; j++)
			if (list[j] < list[min])//더 작은 수를 만난 경우
				min = j;//min 변경
		SWAP(list[i], list[min], temp); //i번째 수와 가장 작은 수의 위치를 변경
	}
}

데이터의 수가 n개일 때

n(n-1)/2 번 연산을 해야 함

 

---

이진 탐색

정렬되어있는 리스트가 있고 key가 주어졌을 때

list[i]=key인 i를 찾아 출력.

 

#include <stdio.h>

int binsearch(int list[], int key, int left, int right) {
	int middle;
	
	while (left <= right) {
		middle = (left + right) / 2;
		if (list[middle] == key) {
			return middle;
		}
		else if (list[middle] > key) {
			right = middle - 1;
		}
		else if (list[middle < key]) {
			left = middle + 1;
		}
	}
	return -1;
	
}
int main() {
	int list[5] = { 10,20,30,40,50 };
	int rs = binsearch(list, 30, 0, 5);
	printf("%d",rs);
}

---

순열

#include <stdio.h>
#define SWAP(x,y,t) (t=x, x=y, y=t)

void perm(char* list, int i, int n) { //list[i]부터 list[n]까지의 원소로 구성된 모든 순열 출력
	int j, temp;
	if (i == n) {//배열의 길이가 1인 경우
		for (j = 0; j <= n; j++) {
			printf("%c", list[j]);
		}
		printf("\n");
	}
	else {
		for (j = i; j <= n; j++) {
			SWAP(list[i], list[j], temp);
			perm(list, i + 1, n);//재귀
			SWAP(list[i], list[j], temp); //원상복구
		}
	}
	

}
int main() {
	char list[4] = { 'a','b','c','d'};
	char temp;
	perm(list, 0, 3);


}