C 数组排序中交换最后一个元素的问题

Question

我正在尝试使用查找数组中最小元素地址的函数编写排序算法：

#include <stdio.h>


int * findMin(int * start,int * end) ///function to return the adress of the smallest array element
{
    int *min = start;
    int x;
    int size = (end - start);
    
    for(x=0; x<size; x++)
    {
    
        if (*(start+x)<*min)
            min = (start+x);
        
    }
    
    return min;
}

但在我的排序算法中，由于最后一个元素没有更多可与之比较的元素，因此被错误地保留原样

void sort(int * start, int  * end)  ///funtion to sort the array in ascending order
{
    int x,temp;
    int size = (end - start);
    
    for (x = 0; x <size; x++) 
    { 
        if ( *(start+x) > *findMin(start,end))
        {
            temp = *findMin(start+x,end);
            *findMin(start+x,end) = *(start+x);
            *(start+x) = temp;
        }
    }
}


int main()
{

    int arr[10]={5,11,3,12,17,25,1,9,14,2};
    
    sort(arr,&arr[9]);
    
    for(int i=0;i<10;i++)
        printf("%d ",arr[i]);
    printf("\n");
    
    
}

我该如何纠正？

Answer 1

这个声明中的表达式

int size = (end - start);

没有给出数组的确切大小。至少你应该写

int size = end - start + 1;

然而，传递指向数组最后一个元素的指针而不是传递指向数组最后一个元素之后的内存的指针并不是一个好主意。在这种情况下，您可以指定一个空范围，因为开始等于结束。

此外，如果函数接受两个指针，则无需引入用作循环索引的中间变量。

还有这个代码片段

        temp = *findMin(start+x,end);
        *findMin(start+x,end) = *(start+x);
        *(start+x) = temp;

效率很低。

这是一个演示程序，展示了如何实现这些功能。

#include <stdio.h>

int * findMin( const int * start, const int * end ) ///function to return the adress of the smallest array element
{
    const int *min = start;

    if ( start != end )
    {
        while ( ++start != end )
        {
            if ( *start < *min ) min = start;
        }
    }
    
    return ( int * )min;
}

void selection_sort( int *start, int  *end )  ///funtion to sort the array in ascending order
{
    for ( ; start != end; ++start )
    {
        int *min = findMin( start, end );

        if ( min != start )
        {
            int tmp = *start;
            *start = *min;
            *min = tmp;
        }
    }
}

int main(void) 
{
    int arr[] = { 5, 11, 3, 12, 17, 25, 1, 9, 14, 2 };
    const size_t N = sizeof( arr ) / sizeof( *arr );
    
    for ( const int *p = arr; p != arr + N; ++p )
    {
        printf( "%d ", *p );
    }

    putchar( '\n' );
    
    selection_sort( arr, arr + N );
    
    for ( const int *p = arr; p != arr + N; ++p )
    {
        printf( "%d ", *p );
    }

    putchar( '\n' );

    return 0;
}

程序输出为

5 11 3 12 17 25 1 9 14 2 
1 2 3 5 9 11 12 14 17 25

Answer 2

But here in my sort algorithm, since the last element has nothing more to compare itself with, is mistakenly left as it is

不，这充其量只是一种误导性的描述。您的 findMin() 没有专门将数组元素与其直接后继进行比较，因此 *end 没有后继这一事实是无关紧要的。问题（部分）只是你有一个差一错误，导致永远不会比较 *end 和 *min。如果您更直接地依赖指针运算和比较，那么这个错误将更难犯也更容易识别：

int *findMin(int *start, int *end) {
    int *min = start;

    // The original code is equivalent to this variant:
    // for (int *x = start; x < end; x++) {
    
    // but this is what you need for an inclusive upper bound:
    // for (int *x = start; x <= end; x++) {

    // or, since initially min == start, this would be even better:
    for (int *x = start + 1; x <= end; x++) {
        if (*x < *min) {
            min = x;
        }
    }
    
    return min;
}

C 数组排序中交换最后一个元素的问题

swapping last element problem in sorting C array

arrays

c

sorting

pointers

selection-sort