Selection sort on array in C

Question

I'm trying to create a simple(?) selection sort program in C that selects the largest integer of an integer array and places it in the location a[n-1], places the second largest number in a[n-2], etc until the smallest number is placed in a[0]. I've run through the below code on paper and it seems like it should work, but when I compile it I'm getting faulty results. Am I missing something obvious?

/* The program implements selection sort*/

#include <stdio.h>
#include "simpio.h"

#define n 5

void GetArray(int a[]);
void SelectionSort(int a[]);
int FindMax(int a[], int high);
void swap(int a[], int p1, int p2);
void PrintArray(int a[]);

main()
{
      int a[n];
      GetArray(a);
      SelectionSort(a);
      PrintArray(a);
      getchar();
}

void GetArray(int a[])
{
     int i;
     for(i=0;i<n;i++)
     {
       printf("Enter integer# %d", i+1);
       a[i]=GetInteger();
     }
}

void SelectionSort(int a[])
{
     int i, max;
     for(i=0;i<n;i++)
     {
           max=FindMax(a,i);
           swap(a,max,(n-1-i));
     }     
}

int FindMax(int a[], int high)
{
    int i, index;
    index=high;
    for(i=high;i<n;i++)
    {
       if(a[i]>a[index])
          index=i;
    }
    return index;
}

void swap(int a[], int p1, int p2)
{
     int temp;
     temp=a[p2];
     a[p2]=a[p1];
     a[p1]=temp;
}

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

Don't try it on paper, run it through the debugger until you find the point where its behaviour diverges from what you expect. — Oliver Charlesworth
– Oliver Charlesworth, Commented Feb 22, 2012 at 1:37
I agree with Oli - also, you'll generally get a better response from questions here if you can narrow down where the problem is. A debugger or print statements will help you do this - and you may even find the problem without needing to ask :) — Timothy Jones
– Timothy Jones, Commented Feb 22, 2012 at 1:43
"I'm getting faulty results." What input creates what result? Give sample input, and show what you actually get. — abelenky
– abelenky, Commented Feb 22, 2012 at 1:46
This is why you should just bite the bullet and learn how to use qsort :-) — paxdiablo
– paxdiablo, Commented Feb 22, 2012 at 1:52
@TimothyJones Could you clarify what you mean by print statements? I haven't really debugged with that method and I'm not quite sure if I see how it could be applied here... (Sorry if this has an obvious answer, I'm a little new to programming). — Joshpho
– Joshpho, Commented Feb 22, 2012 at 2:04

Vijayakumar · Accepted Answer · 2020-07-11 13:12:44Z

2

Selection sort is process of comparing minimum element from the list and placing from the least index. Now consider below code snippet.

public void selectionSort(int[] elements) {
    
    for(int i=0;i<elements.length;i++) {
        int minPosition = i;
        for(int j=i+1;j<elements.length;j++) {              
            if(elements[minPosition]>elements[j])
                minPosition = j;                
        }

        int temp = elements[i];
        elements[i] = elements[minPosition];
        elements[minPosition] = temp;       
    }
}

Thanks for reading, let me know feedback to improve from myside

answered Jul 11, 2020 at 13:12

Vijayakumar

293 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Steve · Accepted Answer · 2012-02-22 01:47:34Z

1

Change these method to:

void SelectionSort(int a[])
{
     int i, max;
     for(i=0;i<n;i++)
     {
           max=FindMax(a,n-i-1);
           swap(a,max,n-i-1);
     }     
}

int FindMax(int a[], int high)
{
    int i, index;
    index=high;
    for(i=0;i<high;i++)
    {
       if(a[i]>a[index])
          index=i;
    }
    return index;
}

I actually tested my answer and it works.

answered Feb 22, 2012 at 1:47

Steve

31.7k19 gold badges101 silver badges123 bronze badges

2 Comments

Joshpho Over a year ago

Off topic, but are you from the PhpBB support forum? I think I recognize you :-) But that seems to be working for me, I'll have to look at my previous code and see where I went wrong.

Steve Over a year ago

Nope - never even done any real PHP. But glad I could help : )

Timothy Jones · Accepted Answer · 2012-02-22 01:39:23Z

0

Shouldn't:

       max=FindMax(a,i);
       swap(a,max,(n-1-i));

Be:

       max=FindMax(a,i);
       swap(a,max,i);

otherwise, next time through the loop, you'll find the same max value in the top position in the array.

answered Feb 22, 2012 at 1:39

Timothy Jones

22.3k6 gold badges65 silver badges95 bronze badges

2 Comments

Joshpho Over a year ago

But then wouldn't the highest number would be put in a[0], etc?

Timothy Jones Over a year ago

That's true. Your current version has the SelectionSort for decending sort, but the FindMax for ascending sort. Daniel's answer fixes the FindMax for you.

lokesh5790 · Accepted Answer · 2014-05-09 01:11:51Z

0

A very basic implementation of selection sort

#include<stdio.h>
main()
{
       int i,j,n=7,a[]={1,2,5,3,8,9,5},key;
       for(j=1;j<n;j++)
       {
                       key=a[j];    //a[j] is the new element to be added to the sorted
                                    //sequence
                       i=j-1;       
                       while(i>=0 && key<a[i]) //traverse through the sorted sequence
                       {a[i+1]=a[i];i--;}      //until the place of key is found
                       a[i+1]=key;             
       }
       for (j=0;j<n;j++)
       printf("%d",a[j]);
}

edited May 9, 2014 at 1:11

answered May 9, 2014 at 1:06

lokesh5790

624 bronze badges

Comments

Sachin Darde · Accepted Answer · 2016-12-03 21:33:22Z

-1

#include<stdio.h>
#include<conio.h>
int removex(int arr[],int small,int n)
{
    int i=0;
    for(;i<n;i++)
        if(arr[i]==small)  //searching that no to delete
            break;
    for(;i<n-1;i++)
        arr[i]=arr[i+1]; //delete by overloading no
    return n-1;
}
void selectSort(int arr[],int sort[],int n)
{
    int j=0,k=0,small;
    while(n!=0)
    {
        small=arr[0];
        for(j=0;j<n;j++)
            if(arr[j]<small)
                small=arr[j]; //finding smallest no
        sort[k++]=small;
        n=removex(arr,small,n);  //removing that from list as we included that no into sorted list
    }
}
void main()
{
    int arr[10],arr2[10],i,n;
    clrscr();
    printf("Enter how many elements");
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&arr[i]);
    selectSort(arr,arr2,n);
    printf("sorted list is\n");
    for(i=0;i<n;i++)
        printf("%d\n",arr2[i]);

    getch();
}

answered Dec 3, 2016 at 21:33

Sachin Darde

1451 silver badge4 bronze badges

4 Comments

Nissa Over a year ago

Explanation please.

melpomene Over a year ago

Why add another answer to a 4 year old question that already has an accepted answer? Especially if your new answer is just a dump of code with no explanation.

melpomene Over a year ago

<conio.h> is not a standard header; void main should be int main; clrscr and getch aren't standard functions; you should never ignore scanf's return value (actually, you should never use scanf for user input in the first place); that's also a potential buffer overflow.

Sachin Darde Over a year ago

@melpomene Thank You Sir for feedback

Collectives™ on Stack Overflow

Selection sort on array in C

5 Answers 5

Comments

2 Comments

2 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

2 Comments

2 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related