글 읽기 - [quick sort] 퀵정렬을 구현했는데 시간초과가 납니다... 도와주세요ㅠㅠ

otter66 3년 전 0

퀵정렬 너무 어렵습니다.... 도와주세요 고수님들...

퀵정렬은 빠른게 아니었나요..??

최악의 경우가 있기 때문인걸까요... 최악의 경우라고 해도 선택정렬정도일텐데...

제가 알고리즘을 구현하면서 실수가 있던건가요ㅠㅠ?

#include <stdio.h>

void QuickSort(int* arr, int start, int end) {
	if (start >= end) return;	//원소가 하나인 경우

	int key = start;
	int i = start + 1;
	int j = end, tmp;

	while (i <= j) {
		while (i <= end && arr[i] <= arr[key]) {
			i++;	//키값보가 큰 값을 찾는다
		}
		while (j > start&& arr[j] >= arr[key]) {
			j--;	//키값보다 작은 값을 찾는다
		}

		if (i > j) {	//현재 엇갈린 상태면 키값 교환
			tmp = arr[j];
			arr[j] = arr[key];
			arr[key] = tmp;
		}
		else {			//현재 엇갈리지 않은 상태면 i와 j 교환 
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}

		QuickSort(arr, start, j - 1);	//왼쪽부분을 정렬 
		QuickSort(arr, j + 1, end);		//오른쪽 부분을 정렬
	}
}

int main() {
	int n;
	int arr[1001];

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	QuickSort(arr, 0, n-1);
	for (int i = 0; i < n; i++) {
		printf("%d\n", arr[i]);
	}
}

seawon0808 3년 전 0

그냥 sort함수를 쓰세요.

otter66 3년 전 0

퀵소트를 공부하고싶을뿐인데욥....

sort함수는 이미 충분히 쓰고있습니다..

seawon0808 3년 전 0

그런데 이 문제는 sort함수만 써야지 시간초과가 안나는 것일 수도 있습니다.

그러므로 완벽한 퀵소트를 사용한 코드가 있어도 시간초과가 날 수도 있습니다.

otter66 3년 전 0

이 문제가 선택정렬로도 통과가 되는 문제라...

그렇다면 최악의 경우 퀵정렬이 선택정렬보다도 많이 느릴 수가 있는건가요..?

seawon0808 3년 전 0

퀵정렬은 최악의 경우 n^2의 시간복잡도를 가집니다.

otter66 3년 전 0

유명한 알고리즘 기법 중 가장 느리다는 선택, 버블도 O(n^2)인걸로 알고있습니다.
가장 느린 선택, 버블도 통과가 되니까 퀵정렬도 통과가 되어야하는게 아닐까요?

seawon0808 3년 전 0

버블정렬로 이 문제를 풀어서 백준에 제출시켜보신적이 있습니까?

otter66 3년 전 0

https://www.acmicpc.net/source...

seawon0808 3년 전 0

저는 퀵정렬을 잘 모르므로 퀵정렬을 사용한 코드로 이 문제를 맞춘사람의 코드를 보세요.

convert7342 3년 전 1

QuickSort를 재귀로 보내는 부분은

while문 밖에있어야합니다~

convert7342 3년 전 1

while(i <= j) 를 통해 키 값을 기준으로 좌 우가 나뉜뒤에 재귀로 보내야겠지요?

otter66 3년 전 0

아.. 그런 이상한 실수를 했군요..
정말 감사합니다~~~! :)

jh05013 3년 전 1

@seawon0808 N이 최대 1,000이므로 O(N^2)에 풀어도 됩니다.

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