글 읽기 - 궁금한 점이 있습니다.

smg20 1년 전 0

일단 백준 2751번 문제를 c언어에서 제공하는 qsort함수를 사용해서 해결은 했습니다. 그리고나서 추가적으로 퀵정렬 알고리즘을 통해 직접 함수를 구현해보면서 추가적으로 공부를 하였습니다. 제가 pivot값을 중간값, 랜덤값, 첫번째값, 마지막값으로 설정하면서 제출을 해봤는데 계속 시간초과가 뜹니다. c언어에서 제공하는 qsort함수를 사용하면 맞았다고 뜨고 직접 함수를 구현해서 제출하면 틀리다고 뜨는데 왜 그런지 알려주시면 감사하겠습니다.

#include <stdio.h>
#include <math.h>

int partition(int arr[], int start, int end);
void QuickSort(int arr[], int start, int end);

int main(void)
{
	int N, i;
	int arr[1000000] = { 0 };
	
    scanf("%d", &N);

	for (i = 0; i < N; i++)
		scanf("%d", &arr[i]);
	//퀵 정렬 함수 사용
	QuickSort(arr, 0, N-1);
	//정렬한 후에 배열의 상태를 출력
	for (i = 0; i < N; i++)
		printf("%d\n", arr[i]);

	return 0;
}
//퀵정렬 알고리즘
void QuickSort(int arr[], int start, int end)
{
	int index;

	if (start < end)
	{
		index = partition(arr, start, end); //분할 함수를 통해 pivort의 위치를 받기
    	QuickSort(arr, start, index - 1); //pivort보다 작은 값들을 정렬
		QuickSort(arr, index + 1, end); //pivort보다 큰 값들을 정렬
	}
	else
		return;
}

int partition(int arr[], int start, int end) //분할 함수.
{
	int i, tmp, random, index = start, pivot;

	srand(time(NULL));
	random = start + (rand() % (end - start + 1));
	
    tmp = arr[random];
  	arr[random] = arr[end];
  	arr[end] = tmp;

	pivot = arr[end];

	for (i = start; i < end; i++)
	{//pivort보다 작은 값들은 pivort의 왼쪽에 위치시키는 과정
		if (arr[i] < pivot)
		{
			tmp = arr[index];
			arr[index] = arr[i];
			arr[i] = tmp;
			index++;
		}
	}
  
	tmp = arr[index];
	arr[index] = arr[end];
	arr[end] = tmp;

	return index;
}