지겨운 퀵소트

안뇽하세요 오늘 코톡에 질문 정말 많이 하네요 ㅠㅠ 정렬 공부중인데,퀵 정렬이 너무 어려운데 정상이겠저…?

백준 알고리즘문제를 푸는데 시간초과가 너무 많이 나네요ㅠ 어디를 어떻게 더 고쳐야 할지 모르겠어서 조언좀 듣고 시퍼요,

문제 링크는 아래와 같습니당

https://www.acmicpc.net/problem/2751

위 문제에서 결국 퀵 정렬을 구현 하라고 하는 것 같아서, 제가 알고 있기론 퀵 정렬이 정렬중 가장 빠르다고 알고있어서 구현까진 했지만, 어느부분에서 느려지는건지… 우선 첫번째로 짜본 코드는 아래와 같습니당

<1>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_LENGTH 9

typedef struct Words Words;
struct Words {

	char str[MAX_LENGTH];
	
};

void Quick_Sort(Words* words, int size);
bool Compare(const char* x, const char* y);
void Swap(Words* x, Words* y);

int main() {

	int Number = 0;

	scanf("%d", &Number);
	Words* words = (Words*)malloc(sizeof(Words) * Number);

	for (int i = 0; i < Number; i++) {

		scanf("%s", words[i].str);
	}

	Quick_Sort(words, Number);

	for (int i = 0; i < Number; i++) {

		printf("%s\n", words[i].str);
	}

	return 0;
}

void Quick_Sort(Words* words, int size) {

	if (size <= 1)return;

	int Target = 0;
	int Left = Target;
	int Right = size;

	while (Left < Right) {

		for (++Left; (Left < size) && (Compare(words[Left].str, words[Target].str) == false); ++Left);
		for (--Right; (Right > Target) && (Compare(words[Target].str, words[Right].str) == false); Right--);

		if (Left < Right)Swap(&words[Left], &words[Right]);
		else Swap(&words[Right], &words[Target]);
	}

	Quick_Sort(words, Right);
	Quick_Sort(words + Left, size - Left);
}

void Swap(Words* x, Words* y) {

	Words temp = *x;
	*x = *y;
	*y = temp;
}

bool Compare(const char* x, const char* y) {

	return (atoi(x) - atoi(y) > 0) ? true : false;
}

비주얼스튜디오 2019프로 사용중인데 테스트 코드는 전부 통과입니다, 근데 itoa or atoi 같은 함수는 애초에 느리다고 들은 기억이 있어서 이거 사용해서 안됬구나 해서 두번째로 짜본 코드는 아래와 같습니당

<2>


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_LENGTH 9

typedef struct Words Words;
struct Words {

	char str[MAX_LENGTH];
	int length;
	
};

void Quick_Sort(Words* words, int size);
int Compare(Words* x, Words* y);
void Swap(Words* x, Words* y);

int main() {

	int Number = 0;

	scanf("%d", &Number);
	Words* words = (Words*)malloc(sizeof(Words) * Number);

	for (int i = 0; i < Number; i++) {

		scanf("%s", words[i].str);
		words[i].length = strlen(words[i].str);
	}

	Quick_Sort(words, Number);

	for (int i = 0; i < Number; i++) {

		printf("%s\n", words[i].str);
	}

	return 0;
}

void Quick_Sort(Words* words, int size) {

	if (size <= 1)return;

	int Target = 0;
	int Left = Target;
	int Right = size;

	while (Left < Right) {

		for (++Left; (Left < size) && (Compare(&words[Left], &words[Target]) < 0); ++Left);
		for (--Right; (Right > Target) && (Compare(&words[Target], &words[Right]) < 0); Right--);

		if (Left < Right)Swap(&words[Left], &words[Right]);
		else Swap(&words[Right], &words[Target]);
	}

	Quick_Sort(words, Right);
	Quick_Sort(words + Left, size - Left);
}

void Swap(Words* x, Words* y) {

	Words temp = *x;
	*x = *y;
	*y = temp;
}

int Compare(Words* x, Words* y) {

	if (*(x->str) == '-' && !(*(y->str) == '-')) {

		return -1;
	}

	else if (!(*(x->str) == '-') && (*(y->str) == '-')) {

		return 1;
	}

	else if (*(x->str) == '-' && *(y->str) == '-') {

		char* str1 = x->str;
		str1 += 1;
		char* str2 = y->str;
		str2 += 1;

		if (x->length == y->length) {
			return strcmp(str1, str2)>0 ? -1 : 1;
		}
		return y->length - x->length;
	}

	if (x->length == y->length) {
		return strcmp(x->str, y->str);
	}
	return x->length - y->length;
}

사실 위의 백준 문제에서 정수 데이터의 범위는 고작 백만이라 그냥 int형 정수배열 만들어서 풀면 되는거 아닌가 싶으셨을텐데 그냥 고집으로 문자형으로 해봤습니다.ㅋ 3시간째 보고있는데 위의 코드에서 문제는 무엇인지 조언 좀 부탁드립니다ㅠ

quicksort 비슷한 모양이긴 한데 pivot ( Target ) 운영이 제가 아는 quicksort 는 아닌 것 같습니다.
제대로 점검해보세요.

작은 예제를 따로 만들고, 작은 몇가지 배열을 입력으로 넣은 다음,
제대로 동작하는지 left, right, pivot 의 값을 추적해 보세요. 의도대로인지.

2 Likes

귀찮으시면 위키든 로제타 코드든에서 quicksort 코드 몇개 긁어다가 배열구조와 비교부분만 바꿔서 돌려보시든지요.

quick sort 는 특히나 예민한 코드고, 비슷하게 작성한다고 제대로 돌아주는게 아니거든요.
검증 난이도가 조금 있습니다. 꼼꼼하게 보셔야됨.
그게 귀찮으면 그냥 남이 짠거 갖다 쓰시는게 답이고요.

답변 감사드립니다. 우선 운영이 quicksort와 다르다고 하셨는데 사실 처음 공부한 퀵소트와 위에 구현한 퀵소트가 생긴게 다른점은 인지하고 있었습니다(사실 그래서 공부했던거에용).공부하면서 위의 퀵소트 코드도 뜯어보니 결국 같은 코드라고 생각 했었는데, 말씀하신 부분들을 다시 점검하고나서도 다른점을 찾지 못했습니다. 제가 아직 부족한게 많기 때문에 중요한 부분을 놓쳤을 수도 있겠다는 생각이 들어서 조심스럽게 질문드리자면 pivot(저는 연결리스트를 공부하면서 이 Target이라는 단어가 맘에들어서 애용하고 있습니다…ㅎ) 을 기준으로 왼쪽과 오른쪽을 나누어 정렬하는 방식이 두 코드다 동일한 것을 확인 했고 몇개의 예제로 원하는 값들을 추적하면서 확인도 해봤고 제가 의도한데로 출력하는 것도 확인 했습니다. 말씀하신데로 퀵스트가 예민한 코드이고 검증난이도도 꾀 있다는 것도 동의하기에 아직 제가 실력이 많이 부족해서 말씀하신 것들을 미처 확인하지 못한 부분이 있단 생각에 조심스럽게 다시 질문드려봅니다…ㅠㅠ

아래 코드는 기존에 말씀하신 퀵 소트라고 생각드는 코드로 다시 작성한 코드입니다!

< 이상한 퀵소트 >

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_LENGTH 9

typedef struct Words Words;
struct Words {

	char str[MAX_LENGTH];

};

void Quick_Sort(Words* words, int size);
bool Compare(const char* x, const char* y);
void Swap(Words* x, Words* y);

int main() {

	int Number = 0;

	scanf("%d", &Number);
	Words* words = (Words*)malloc(sizeof(Words) * Number);

	for (int i = 0; i < Number; i++) {

		scanf("%s", words[i].str);
	}

	Quick_Sort(words, Number);

	for (int i = 0; i < Number; i++) {

		printf("%s\n", words[i].str);
	}

	return 0;
}

void Quick_Sort(Words* words, int size) {

	if (size <= 1)return;

	int Target = 0;
	int Left = Target;
	int Right = size;

	while (Left < Right) {

		for (++Left; (Left < size) && (Compare(words[Left].str, words[Target].str) == false); ++Left);
		for (--Right; (Right > Target) && (Compare(words[Target].str, words[Right].str) == false); Right--);

		if (Left < Right)Swap(&words[Left], &words[Right]);
		else Swap(&words[Right], &words[Target]);
	}

	{
		printf("\t<TEST> : Pivot : %s\n", words[Right].str);
		for (int i = 0; i < size-1; i++) {
			printf("%s ", words[i].str);
		}printf("\n");
	}

	Quick_Sort(words, Right);
	Quick_Sort(words + Left, size - Left);
}

void Swap(Words* x, Words* y) {

	Words temp = *x;
	*x = *y;
	*y = temp;
}

bool Compare(const char* x, const char* y) {

	return (atoi(x) - atoi(y) > 0) ? true : false;
}

<아마도 말씀하신 퀵 소트? >

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_LENGTH 9

typedef struct Words Words;
struct Words {

	char str[MAX_LENGTH];
	int length;

};

void Quick_Sort(Words* words,int start, int end);
bool Compare(const char* x, const char* y);
void Swap(Words* x, Words* y);

int main() {

	int Number = 0;

	scanf("%d", &Number);
	Words* words = (Words*)malloc(sizeof(Words) * Number);

	for (int i = 0; i < Number; i++) {

		scanf("%s", words[i].str);
		words[i].length = strlen(words[i].str);
	}

	Quick_Sort(words, 0, Number - 1);

	for (int i = 0; i < Number; i++) {

		printf("%s\n", words[i].str);
	}

	return 0;
}

void Quick_Sort(Words* words, int start, int end) {

	if (start >= end)return;
	/*
		Target = Pivot;
	*/
	int Target = start;
	int Left = Target + 1;
	int Right = end;

	//char* temp = words[Target].str;

	while (Left <= Right) {

		while ((Left <= end) && (Compare(words[Left].str, words[Target].str) == false))Left++;

		while ((Right > Target) && (Compare(words[Target].str, words[Right].str) == false))Right--;

		if (Left <= Right)Swap(&words[Left], &words[Right]);
		else Swap(&words[Right], &words[Target]);
	}

	{
		printf("\t<TEST> : Pivot : %s\n", words[Right].str);
		for (int i = start; i < end; i++) {
			printf("%s ", words[i].str);
		}printf("\n"); 
	}

	Quick_Sort(words, start, Right - 1);
	Quick_Sort(words, Right + 1, end);
}

void Print_Array(Words* words, int size) {

	for (int i = 0; i < size; i++) {

		printf("%s ", words[i].str);
	}
}

void Swap(Words* x, Words* y) {

	Words temp = *x;
	*x = *y;
	*y = temp;
}

bool Compare(const char* x, const char* y) {

	return (atoi(x) - atoi(y) > 0) ? true : false;
}


<테스트>
10
5
7
4
6
2
9
8
1
3
10
        <TEST> : Pivot : 5
2 3 4 1 5 9 8 6 7
        <TEST> : Pivot : 2
1 2 4
        <TEST> : Pivot : 4
3
        <TEST> : Pivot : 9
7 8 6 9
        <TEST> : Pivot : 7
6 7
1
2
3
4
5
6
7
8
9
10

아 추가적으로 위의 퀵 소트 소스코드는 아래의 링크에서 공부한 코드에용 좋은 자료들이 많아서 자주 이용하는 사이트인데 시간나시면 확인 부탁드리겠습니다!

일단 개인 블로그 류 보다는 이런곳이 여러 사람들이 쳐다보기에 검증되어 있을 가능성이 큽니다.

https://rosettacode.org/wiki/Sorting_algorithms/Quicksort

그리고 quick sort 가 아무리 O ( n log n ) 알고리즘 중에서 빠른편에 속한다 하지만,
저런 코드챌린지 사이트들은 문제에 따라 제각각의 시간 기준을 갖고 있고,
때로는 굉장히 타이트하기도 하니까,
문자열 베이스로 정렬한다는건 한번의 비교를 여러번의 메모리 접근과 비교로 바꿔버립니다.

속도가 중요한 문제에서 문자열을 고집하는건 이상한 컨셉 같습니다.

pivot 을 시작 위치로 잡냐 ( left + right ) / 2 인 mid 로 잡냐는 크게 중요한 문제는 아닌데요,
아래 질문에서의 stack overflow 는 swap 으로 해결된 모양이군요?

이런건 words + Left 로 그냥 쓰시면 됩니다.

어라 거기다 atoi 까지 쓰고 계시군요…;;
2 랑 10 이랑 비교하자면 당연한거겠지만,
비교할때마다 문자열 숫자 변환을 한다는건 swap 횟수인 n * log n 번 이상 한다는건데 정상이 아닙니다…

정수 비교 한 번이면 끝날 문제를,
자릿수만큼의 비교를 돌리는 문자열 처리와, 또한 그만큼의 정수 변환, 그걸 또 함수로 싸서 돌리고 있으니 느릴밖에요.

같은 수를 왜 매번 atoi 하나요. ㅡㅡ 그냥 정수로 돌리셔야죠.

stack overflow 질문 했던걸 말씀하시는게 맞나용? 재귀함수로 구현해놓고 탈출 조건을 적지 않아서 오버플로우가 발생했던 거더라구요…ㅠ 계속 답변해주셔서 감사합니다!

아아 그건 그렇게 해결된거군요 ( 사실 코드 제대로 안봄 )

확장성을 두고 싶으면 big integer 같은걸 구현하셔야 됩니다.
저 컨셉은 그냥 문자열 노가다시키기 예요.

제가 문자열로 구현하는걸 고집해서 생긴 문제 같네요 ㅠㅠ 개인적으로 문자열에대해 연구를 좀더 하고 싶기도 하고, 뭔가 '문자열’이 c언어에서는 포인터 배열 널포인터 메모리 등등 어려운 내용들이 많이 있다보니 실력이 없는 저는 뭔가 더 공부하면서 실력이 느는 느낌이 들더라구요… 그래서 괜히 고집을 부렸네요…ㅋ

뭐 경험이 되시겠죠.

최적화의 가장 기본은, 제거할 수 있는 같은 연산은 제거 한다는겁니다.
바뀌지 않는 수를 비교시마다 변환하는건 엉뚱한거죠.

변환을 하더라도 한 번만 해야 하는것이구요.

찬찬히 코드를 읽어드리고 돌려드리고 하면 좋겠지만…

뭐 제 평생 그것만 해주고 살 순 없는 노릇이라서 양해바랍니다.

일일이 신경써주는 젊은 친구들한텐 감사해야 하구요. ( 저도 몇 년 전까진 그랬쥬 )

그리고 문제에 ‘수는 중복되지 않는다’ 는게 있네요.

아아 아닙니다! 오히려 시간내서 답변해주시는게 제 입장에선 더 감사드리는 거죠… 코톡은 뭔가 이렇게 답변으로 교류하는게 많아서(특히 탱커분들이…) 질문을 올리면 항상 얻어가는게 많고 저는 질문충이라 이렇 질문만 올리고 답변은 못해드리는데 탱커분들이 답변해주시는 내용들은 항상 도웁이 많이 되더라구요 늦은 시간에도 계속 답변 해주셔서 감사드립니다!!

크기가 1000000 개에 중복되지 않는 수라면, 1000000 비트 배열을 사용하면 정렬 을 O( n ) 으로 가능합니다.