I am trying to print iterations of the sorting function, it seems to work but there are some extra numbers

Viewed 47
void SelectionSort(int arr[], int n)
{
    int i, j, min_idx;
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        PrintArray(&arr[i], n);
        for (j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
            // Swap the found minimum element with the first element
                Swap(&arr[min_idx], &arr[i]);
    }
}
void PrintArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

this is the output I'm getting

I'm trying to print out every iteration of the sorting process, I already tested the sorting function and the print function separately and they both work, I tried to place the print function at different places in the loop but that did not work either. I am new to c and programming in general so if you could also explain the steps to me I would appreciate it. thanks

2 Answers

Notice that you are passing the array starting from the i'th element to your print function, but your print function expects the array to have n elements by initializing i to be 0 in the for loop. As a result you are actually printing elements outside the array. This also explains why you always print n elements, and the amount of additional numbers grows each time.

I suggest you use valgrind on your programs. It shows various memory bugs that may happen in your program. This is an example of accessing memory outside what was allocated to you, which it would have caught. It also tells you about memory leaks (i.e. memory you didn't deallocate) at the end of your run.

Also, never omit curly braces in your code even if the block is 1 command long. It makes your code much less readable and may cause bugs as a result.

void PrintArray(int arr[], int n) { 
    int i; 
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]); 
    }
    printf("\n"); 
} 

This call

PrintArray(&arr[i], n);

always uses as the number of outputted elements of the array the value stored in the variable n. So independent of the starting index i the function will try to output exactly n elements that results in accessing memory beyond the array.

You have to write

PrintArray( &arr[i], n - i );

or

PrintArray( arr + i, n - i );

However it seems you want to output the whole array in each iteration. If so then you should just write

PrintArray( arr, n );

Also pay attention to that you should use the type size_t instead of the type int for the parameter that specifies the number of elements in the array because an object of the type int in general can be not large enough to store the possible number of elements in an array.

That is your function should be declared like

void SelectionSort(int arr[], size_t n);

Correspondingly the function PrintArray should be declared like

void PrintArray( const int arr[], size_t n );

Pay attention to that the first parameter has the qualifier const because elements of the array are not being changed within the function.

Also you should swap two elements of the array only in case when they are not the same one element.

Here is a demonstrative program.

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

void PrintArray( const int [], size_t );
void Swap( int *, int * );

void SelectionSort( int arr[], size_t n )
{
    for ( size_t i = 1; i < n; i++ )
    {
        PrintArray( arr + i - 1, n - i - 1 );
        
        size_t min_idx = i - 1;

        for ( size_t j = i; j < n; j++ )
        {
            if ( arr[j] < arr[min_idx] ) min_idx = j;
        }           

        if ( min_idx != i - 1 ) Swap( &arr[min_idx], &arr[i-1] );
    }
}

void PrintArray( const int arr[], size_t n )
{
    for ( size_t i = 0; i < n; i++ )
    {
        printf( "%d ", arr[i] );
    }       
    putchar( '\n' );
}

void Swap( int *a, int *b )
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(void) 
{
    enum { N = 10 };
    int a[N];
    
    srand( ( unsigned int )time( NULL ) );
    
    for ( size_t i = 0; i < N; i++ )
    {
        a[i] = rand() % N;
    }
    
    SelectionSort( a, N );
    
    PrintArray( a, N );
    
    return 0;
}

The program output is

2 2 9 2 3 9 3 2 
2 9 2 3 9 3 2 
9 2 3 9 3 2 
9 3 9 3 2 
3 9 3 9 
9 3 9 
9 9 
9 

2 2 2 2 2 3 3 5 9 9 
Related