Search code examples
algorithmiterationselection-sort

What is wrong with my selection sort?


My implementation of selection sort does not work in case of j < n-2 or n-1 or n. What am I doing wrong?

Is there an online IDE that lets us put a watch for the control loops?

#include <stdio.h>
#define n 4
int main(void) {
    int a[n]={4,3,2,1};
    int j,min;
    for(int i=0;i<n;i++){
        min=i;
        for(j=i+1;j<n-3;j++)
            if(a[j]>a[j+1])
                min=j+1;
        if(min!=i){
            int t=a[min];
            a[min]=a[i];
            a[i]=a[t];
        }
    }

    for(int i=0;i<n;i++)
        printf("%d",a[i]);
    return 0;
}

I tried it here


Solution

  • Your code has indeed a strange limit on n-3, but it has also some other flaws:

    • To find a minimum you should compare with the current minimum (a[min]), not the next/previous element in the array
    • The code to swap is not correct: the last assignment should not be from a[t], but t itself.

    Here is the corrected code:

    int main(void) {
        int a[n]={4,3,2,1};
        int j,min;
        for(int i=0;i<n;i++){
            min=i;
            for(j=i+1;j<n;j++)
                if(a[min]>a[j])
                    min=j;
            if(min!=i){
                int t=a[min];
                a[min]=a[i];
                a[i]=t;
            }
        }
    
        for(int i=0;i<n;i++)
            printf("%d",a[i]);
        return 0;
    }
    

    https://ideone.com/AGJDPS

    NB: To see intermediate results in an online IDE, why not add printf calls inside the loop? Of course, for larger code projects you'd better use a locally installed IDE with all the debugging features, and step through the code.