[완료] 흠.. 꽤나 어려운듯한 오름,내림차순 정렬 문제가 발생했습니다.

mauri의 이미지

안녕하세요.

파일 리스트에서 리스트를 주욱~ 읽어들여서 리스트 컨트롤(흔히 사용하는 윈도우 탐색기의 오른쪽 부분)에 뿌려주고 있습니다.

리스트 컨트롤에서 헤더(탐색기로 치자면 파일명 종류 사이즈를 나타내는 부분)를 클릭하면 자동으로 정렬을 하게 만들었습니다.

정렬을 하는 컬백 함수를 만들어야 하는데 이 함수의 리턴값으로 자동 정렬이 됩니다.

그래서 흔히 하는대로 이렇게 만들었죠.

if( b_asc ){
return strcmp(str1, str2);
}
else {
return strcmp(str2, str1);
}

허헐.. 이렇게 만들고 보니.. 글쎄.. XP부터 정렬 스타일이 바뀌었지요?

예로

a1
a11
a2
a3
a21

이렇게 있다면 구 버전에서는 정렬이 이렇게 됩니다(제가 작성한 방식)
a1
a11
a2
a21
a3

하지만 새로운 XP스타일에서는 다음과 같이 정렬이 됩니다.
a1
a2
a3
a11
a21

이야.. 이거 간단하겠지? 라고 생각을 했는데.. 보통 어려운게 아니네요..;;

문자 길이로만 보고 하자니 abc1 abc11 bc2 이런경우 황당한 결과가 나오게 되고..

문자는 문자대로 숫자는 숫자대로 비교를 하니.. 항목 만건이 넘어서면 느려지는게 눈에 보일정도 입니다.

<< 요점만 간단히 간추리자면 >> a, ab, abc, b 가 있을 경우 a > ab > abc > b 순으로.. 1, 12, 123, 2 가 있을 경우 1 > 2 > 12 > 123 순으로..

정렬되는 함수가 존재할려는지요?

혹시 같은 문제로 고민하셨거나, 해결법을 알고 계시는 분이 계시다면 조언 부탁드립니다.

그럼... 즐프되십시요. __);

neogeo의 이미지

더 궁금한건 a123a 와 a12a 는 어떻게 정렬이 되야 하는 겁니까? aaa154b aaa16b 가 있다면 ?

aaa016 과 aaa16 은 어떻게 되나요?

일단 위의 내용을 다 비교하시면 대략 어떻게 짜야하나 감이 오시지 않을까 합니다만.. 상당히 골때린 일이 되겠군요 :(

Neogeo - Future is Now.

Neogeo - Future is Now.

brucewang의 이미지

주어진 string의 hash값으로 비교를 하시면 될 것 같습니다.

a1 < a2 < a11

이런식으로 스트링을 어떤 long 형 값으로 치환하시면 되겠네요.

아까전에 코드를 올렸는데(간단히 몇라인이면 되었습니다), 성능이나 hash collision 문제등이 있는 등 챙피해서 그냥 지웠습니다. ^^

-------------------------------------------------
$yes 4 8 15 16 23 42

-------------------------------------------------
$yes 4 8 15 16 23 42

winner의 이미지

PHP의 strnatcmp source를 보시는 것이 좋겠네요.

mauri의 이미지

neogeo님//

a12a
a123a
aaa016
aaa16
aaa16b
aaa154b

이러한 순서가 되게 됩니다.

brucewang님//
저도 그생각은 해봤는데.. 1만건이 넘어가는데다가, 정렬까지 하게되면 거의 걷잡을 수 없는 시간이 걸리게 됩니다.
현재 단순 정렬에도 약 5초정도 걸리게 되거든요.

winner님, ditto님//
감사드립니다. 링크가 많은 도움이 되었습니다.

링크를 참조해가며 만들다보니..
문득.. "이미 파일 탐색기에서 사용하는 기능이니 API가 제공될 것이다"라는 생각이 들었습니다.

이미 OS에 탑재되어 있는것은 100% API가 있다는 소리가 되니까요.
(공개냐 비공개냐의 차이일 뿐이지요?)

그래서 검색을 해보니 StrCmpLogicalW 라는 함수를 제공하고 있어서 간단히 해결했습니다.

도움주신 모든 분들께 정말 감사드립니다.. __);

brucewang의 이미지

우선 축하드립니다. ^^

저도 글을 써 놓고, 경솔한 답변을 했다 싶었습니다. 이미 시도 해 보셨을 거라는것...
hash를 사용하지 않는 간단한 코드도 올리려 했는데, 글을 자세히 읽어보니 그것도 이미 시도하셨고 단지 속도가 문제라고 하셨더군요... XO

아, 근데 StrCmpLogicalW 이 Shlwapi.dll version 5.5 이상에서 지원되는 API라던데 다양한 9x, 2k 혹은 old Shlwapi.dll 에 대한 고려는 안하셔도 되는지요?

-------------------------------------------------
$yes 4 8 15 16 23 42

-------------------------------------------------
$yes 4 8 15 16 23 42

mauri의 이미지

장치제어하는 특수한 환경이기 때문에요. XP고정이 됩니다.

많은 관심과 첨부해주신 예제코드도 정말 감사드립니다.. ^^*

neogeo의 이미지

aaa22aaa33
aaa3aa55
aaa21bbb44
21aab44aaa55
21aab3bbb56

이런녀석들이 반복해서 있으면 어찌되는가도 상당히 궁금하군요 -_-;;;

그나저나 도대체 무슨 센스로 저렇게 소팅을 하는걸까요.... (=ㅅ= )

도저히 규칙이 이해가 가지 않네요...

Neogeo - Future is Now.

Neogeo - Future is Now.

brucewang의 이미지

아, 그것은 neogeo님께서 잘 집어 주신것인데
정하기 나름 아닐까요..

제가 여러가지를 고려하지 않은 부분이 많아 챙피해서 코드를 안올리려 했는데,
아마 제 코드를 보시면 실소를 금치 못하실겁니다.. comp() 함수인데,
보시면 어떻게 정렬시키겠다는 제 생각이 보이실겁니다. 이거야 정하기 나름인 것 같습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/*
unsigned long hash(char *str)
    {
	unsigned long hash = 0;
	// ... hash collision occurred. abolishing the code
        return hash;
    }
*/
 
static int comp(const void *va, const void *vb)
{
	char* a=(char*)va;
	char* b=(char*)vb;
	int la = strlen(a);
	int lb = strlen(b);
	int len = la>lb?la:lb;
	int diff=0;
	int inumbera=0;
	int inumberb=0;
	int tempa;
	int tempb;
	//bool bfirstnumber=false;
 
	for(int i=0; i<len && diff==0; i++)
	{
		diff = a[i] - b[i];
		if( 0!=diff )
		{
			tempa = (int)(a[i] - '0') ;
			tempb = (int)(b[i] - '0') ;
			bool bai = tempa >= 0 && tempa <= 9 ? true : false;
			bool bbi = tempb >= 0 && tempb <= 9 ? true : false;
 
			if(bai && bbi)
			{
				if(la==len)inumbera = inumbera*10 + tempa;
				if(lb==len)inumberb = inumberb*10 + tempb;
 
				diff=inumbera-inumberb;
 
				//bfirstnumber=true;
			}
			else
			{
				//bfirstnumber=false;
			}
		}
	}
 
	return diff;
}
 
int main(int argc, char* argv[])
{
	int j;
 
	char input[12][10] = {"a1", "a11", "a07", "a21", "au2", "a2", 
				"a111", "a3b", "a3a", "a3a1", "a3a11", "aaa", };
	const int istrings = 12; // number of strings to sort
 
	qsort(&input[0], istrings, 10, comp);
 
	for (j = 0; j < istrings; j++)
		puts(input[j]);
 
	exit(EXIT_SUCCESS);
}

코드보고 너무 뭐라 하진 말아주세요.. 저도 챙피합니다.

-------------------------------------------------
$yes 4 8 15 16 23 42

-------------------------------------------------
$yes 4 8 15 16 23 42

winner의 이미지

http://www.naturalordersort.org/

Windows XP부터 Windows에서도 적용되는지는 몰랐네요.

사람이 이름을 적을 때 안에 숫자가 들어갈 때
일반적인 문자열의 사전식 순서를 적용할 수 없다는 것이
이 방식이 나온 것입니다.

Programmer들이야 source를 보면 이해하겠지만
알고리즘을 일반화시켜 이렇게 정형화를 해낸 것은 정말 놀랍습니다.

검색해보니 이제는 대단히 다양한 곳에서 이미 적용되어 있더군요.
ls나 Perl의 정렬함수에도 이미 적용되어 있나 보네요.

이 방식이 가장 대중적으로 효과를 보는 것은 아마도 연속물 동영상 볼 때가 아닌가 싶네요.
예전에는 다들 01, 02, ..., 10, 11, ... 으로 하고 100편 이상이면 001, 002 였는데
이제는 앞의 채움용 숫자는 제거해도 되지요.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.