[C] 퀵정렬을 이용한 몇 번째 작은수

10개의 난수(100보다 작은)를 발생시키고 몇 번째 작은 수를 찾을 것인가를 입력받은 후 그 수를 출력하는 프로그램을 작성하라.

 

입력 :

Enter the number of numbers : 10

몇번째로 작은 수 : 4

출력 :

894 250 65 688 99 966 296 649 455 305

4번째로 작은 수는 296

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void init_array(int list[], int n) {
	srand(time(NULL));
	for (int i = 0; i < n; i++)
		*(list + i) = rand() % 100;
}

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

void swap(int A[], int i, int j) {
	int temp = A[j];
	A[j] = A[i];
	A[i] = temp;
}

int partition(int A[], int p, int r) { //퀵 정렬의 partition
	int i = p - 1;
	int j = p;
	int pivot = A[r];

	while (j < r) {
		if (A[j] < pivot) {
			swap(A, ++i, j);
		}
		j++;
	}
	swap(A, ++i, j);

	r = i;
	return r;
}

int find(int A[], int p, int r, int orderIndex) {
	int q;

	if (p <= r) {
		q = partition(A, p, r);

		if (orderIndex == q)
			return A[orderIndex]; //찾으면 그 수 반환
		else if (orderIndex < q) //찾고자 하는 수의 인덱스가 partition보다 작으면 왼쪽에서 찾기
			find(A, p, q - 1, orderIndex);
		else
			find(A, q + 1, r, orderIndex); //크면 오른쪽에서 찾기
	}
}

int main(void) {
	int num, order;
	int *list;

	printf("Enter the number of numbers: ");
	scanf("%d", &num);

	printf("몇번째로 작은 수: ");
	scanf("%d", &order);

	list = (int*)malloc(sizeof(int) * num);

	init_array(list, num);
	print_array(list, num);

	int order_num = find(list, 0, num - 1, order-1);
	printf("\n%d번째 작은 수는 : %d\n", order, order_num);

	free(list);
}