글 읽기 - Random Pivot Quicksort로 짰는데 시간초과 뜨네요.

mkleeboy3 5년 전 0

Mergesort로는 됐는데

Random Pivot으로 골라서 Quicksort를 구현했는데 시간초과가 뜨네요.

간편함을 위해서 인덱스만 정렬했습니다.

퀵소트로는 정녕 해결이 안되는건가요?

퀵소트도 구현방법에 따라서 조금씩 차이가 나던데 혹시 두 인덱스 i, j를 양끝에서부터 시작해서 중간값을 pivot으로 정해서 구현한 퀵소트로는 해결이 될까요? 성능차이가 있을까요?

/*
2018-09-08
Lee Min Keon
Baekjoon Online Judge #1181
mkleeboy3@naver.com
*/

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

#define MAX_WORD_LENGTH 51

void swap(int* arr, int i, int j)
{
	if (i == j) return;

	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

int partition(char** word, char* len, int* index, int i, int j)
{
	int p_index = rand() % (j - i + 1) + i;

	swap(index, p_index, j);

	for (int k = p_index = i; k < j; k++)
		if (len[index[k]] < len[index[j]]) { swap(index, k, p_index); p_index++; }
		else if (len[index[k]] == len[index[j]])
			if (strcmp(word[index[k]], word[index[j]]) < 0) { swap(index, k, p_index); p_index++; }

	swap(index, p_index, j);

	return p_index;
}

void quick_sort(char** word, char* len, int* index, int i, int j)
{
	if (i >= j) return;

	int p_index = partition(word, len, index, i, j);
	quick_sort(word, len, index, i, p_index - 1);
	quick_sort(word, len, index, p_index + 1, j);
}

int main()
{
	srand((unsigned)time(NULL));

	int n;
	scanf("%d", &n);

	int* index = (int*)calloc(n, sizeof(int));//index arrays for array 'word'
	for (int i = 0; i < n; i++)
		index[i] = i;

	char** word = (char**)calloc(n, sizeof(char*)); //2-dimensional array which takes strings as input
	for (int i = 0; i < n; i++)
		word[i] = (char*)calloc(MAX_WORD_LENGTH, sizeof(char));

	char* word_len = (char*)calloc(n, sizeof(char)); //array which takes word length per index

	for (int i = 0; i < n; i++)
	{
		scanf("%s", word[i]);

		char count = 0;
		while (word[i][count]) count++;
		word_len[i] = count;
	}

	quick_sort(word, word_len, index, 0, n - 1);

	char prev[MAX_WORD_LENGTH] = "";
	for (int i = 0; i < n; i++)
	{
		if (!strcmp(word[index[i]], prev)) continue;
		printf("%s\n", word[index[i]]);
		strcpy(prev, word[index[i]]);
	}

	free(index);

	for (int i = 0; i < n; i++)
		free(word[i]);
	free(word);

	free(word_len);

	return 0;
}

djm03178 5년 전 1

피벗을 랜덤으로 잡아도, 여전히 O(N^2)입니다. 모든 원소가 다 같을 때에 문제가 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Random Pivot Quicksort로 짰는데 시간초과 뜨네요.

mkleeboy3 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말