swapping last element problem in sorting C array

user_13338945 0
Viewed 196

I am trying to write a sorting algorithm using a function that finds the adress of the minimum element in the array:

#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;
}

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

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");
    
    
}

How can I correct this?

selection-sort pointers sorting c arrays
2 Answers

The expression in this declaration

int size = (end - start);

does not give the exact size of the array. At least you should write

int size = end - start + 1;

However it is not a good idea to pass the pointer to the last element of the array instead of the pointer to the memory after the last element of the array. In this case you can specify an empty range as start is equal to end.

Also if the function accepts two pointers then there is no need to introduce intermediate variables used as indices in loops.

And this code snippet

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

is very inefficient.

Here is a demonstrative program that shows how the functions can be implemented.

#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;
}

The program output is

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

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

No, that's at best a misleading characterization. Your findMin() does not specifically compare array elements to their immediate successors, so the fact that *end has no successor is irrelevant. The problem is (in part) simply that you have an off-by-one error, resulting in never comparing *end with *min. That mistake would be harder to make and easier to recognize if you relied more directly on pointer arithmetic and comparisons:

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;
}
user_24022720
Related