QuickSort 알고리즘에 NaN을 포함시키는 방법은 무엇입니까? 다음

Question

이

내 코드입니다 : 배열에 NaN 추가

#include <stdlib.h> 
#include <stdio.h> 
#include <limits> 

#define INFINITY std::numeric_limits<float>::infinity() 
#define NEGINFINITY -std::numeric_limits<float>::infinity() 

int floatcomp(const void* elem1, const void* elem2) 
{ 
    if (*(const float*)elem1 < *(const float*)elem2) 
     return -1; 
    return *(const float*)elem1 > *(const float*)elem2; 
} 

int main() 
{ 
    float array[10] = {INFINITY, 3.5f, 144.4f, NAN, 12.4f, NEGINFINITY,  1.4f, -0.0f, 5.9f}; 
int i; 

for (i = 0; i < 10; i++) 
printf("%f\n", array[i]); 
printf("\n"); 

qsort(array, 10, sizeof(float), floatcomp); 

for (i = 0; i < 10; i++) 
    printf("%f\n", array[i]); 

return 0; 
} 

의 NaN은 그것이 있어야로 제대로 분류되어지고되지 않고, 나는 제대로 두 개의 서로 다른 가수의에 추가 할 수 (신호 조용) 아니에요 NaN을 맨 위의 문자열로 내 코드에 삽입하십시오.

Answer 1

아마도 가장 쉬운 방법은 목록을 전달하고, NaN을 모두 제거하고, 발견 한 수를 기록하는 것입니다. 그런 다음 목록이 정렬 된 후 NaN을 배치하기로 선택하면 정렬 된 목록의 앞이나 뒤에 많은 NaN을 추가합니다.

Answer 2

일반적으로 NaN (문자 적으로 "숫자가 아님")은 다른 수량과 비교할 수 없습니다. 모든 비교는 거짓입니다. NaN < 5가 거짓입니다. NaN> 5는 거짓입니다. NaN == NaN는 false입니다. NaN! = NaN은 거짓입니다.

비교 기능은 서면 설명과 반대되는 접근 방식을 취합니다. 그것은 NaN이 무엇이든 모든 것과 같다고 말합니다 (NaN이 관련되어 있으면 0을 반환 함). 빠른 정렬은 안정적인 정렬 알고리즘이 아닙니다. qsort에 대한 맨 페이지는 다음과 같이 말합니다. "두 멤버가 동등한 것으로 비교되는 경우 정렬 된 배열의 순서는 정의되지 않습니다."

1. 동등한 비교 항목은 원래 순서대로 유지 보장되는 안정적인 정렬 알고리즘을 사용하여

   당신은 두 가지 중 하나를 수행해야합니다.

2. 비교 함수에 isnan 함수를 사용하여 NaN을 식별하고 NaN을 어떻게 처리할지 결정하십시오.

"올바른 경로"를 선택하는 경로는 다음과 같습니다.