Thread: Selection Sort

Hello i have recently started programming in C and have managed to put together my first selection sort program.

Code:

#include <stdio.h>
#include <conio.h>
int sort(int a[], int x)
{
int i, j, spot;
 for (i = 0; i > x; i++)
 {
  
  for(j=i; j < 0; j--)
  {
   if (a[j] > a[j+1])
   {
   spot = a[j];
      a[j] = a[j+1];
   a[j+1] = spot;
   }
  }
 }
 return 0;
}
  int main()  
  {  
  
      int a[100],x,i;  
  
        
  
      printf(" Spots in array: \n ");  
      scanf("%d",&x);  
  
      for( i=0;i<x;i++)  
  { 
      printf("\n\n Spot %d in array : ",i+1);  
              scanf("%d",&a[i]);  
  }  
  
       sort(a,x);
  
       printf("\n\n\n\n\n iSort \n\n");  
       for( i=0;i<x;i++)
       {
       printf("%d\n",a[i]);  
       }
  
  system("Pause");
  }

Everything seems to work besides the actual sort? Can someone more experienced please show me what I am doing wrong.


Thanks.

The pseudocode Selection sort - Wikipedia, the free encyclopedia

At your code

Code:

for (i = 0; i > x; i++)

This is your initial loop in the function.Will the code flow enter it?

wouldn't using j = i in the second loop allow the data in my sort function to pass through the original for loop after each pass? Is this what you are refering too?

in the first iteration of the loop 'for (i = 0; i > x; i++)' , i == 0. look closely at the 'while' condition in your loop. will i ever be greater than x? and if it is, will the loop terminate?

My mistake on the second expression of the for loop need to be more careful obviously..

Code:

for (i = 0; i < x; i++) //quits when i is larger than x
 {
  
  for(j=i; j < x; i--) // isn't this wrong as well?
  {
   if (a[j] > a[j+1])
   {
   spot = a[j];
      a[j] = a[j+1];
   a[j+1] = spot;
   }
  }
 }

Shouldn't my inner for loop have j++ for the update expression? If i starts out at zero; the loop will continue until j is larger than x; and we minus 1 each pass == terminates the loop.

Code:

for (i = 0; i < x; i++)
 {
  
  for(j=i; j < x; j++)
  {
   if (a[j] > a[j+1])
   {
   spot = a[j];
      a[j] = a[j+1];
   a[j+1] = spot;
   }
  }
 }

Although we are making headway (The numbers jumble and for some reason result with a 0 in the middle of the array out of nowhere), we are still not sorting in the order I intend.

Code:

for(j=i; j < x; j++)
  {
   if (a[j] > a[j+1])
   .....

What will happen in the if condition when j gets the value of x-1?

I'm sorry std10093 I'm lost with that statement. I have no idea how to iterate what you are asking me. Why would j have a value of x-1?

Do not be sorry.You are honest.You try.I appreciate that
See post number 8 from this thread Simple c programming
When j gets the value of x-1 then in the if statement you will have this

Code:

if(a[x-1] > a[x])

Arrays start indexing at zero and finish at sizeOfArray-1, so a[x] is out of borders.That i think explains the zero.You were just lucky not to get a segmentation fault.
Maybe what you written here is not selection sort.Look the link i provided in post number two of this post for the pseudocode of it

I don't know what that is, but it's certainly not selection sort. In selection sort, you repeatedly scan over the values of the array, and find the smallest value. Then you place that one value, and repeat until the array is all sorted.

A slow sorter to be sure.

Code:

int min;
int temp;

for (i = 0; i < x-1; i++)  //x-1, same as Substitution sort on outer loop
 {
  
   min = a[i]; //  
  for(j=i+1; j < x; j++)  //i+1, also same as Substitution sort
  {
     //if (a[j] > a[j+1]) this is bubble sort!
     if(a[j] < a[min] 
     {  
        min = j;
     } 
  }
  if(min != i) {
     temp = a[i];
     a[i] = a[min];
     a[min] = temp;
  }
}

I don't use Selection sort but once in a blue moon, so this might not be right, but it's close.


What will happen in the if condition when j gets the value of x-1?[/QUOTE]

Code:

#include <stdio.h>
#include <conio.h>
 

void swap (int *a, int *b) 
{
int temp;

temp = *a;
*a = *b;
*b = temp;
}
int sort(int a[], int x)
{
int i, j;
 for (i = 0; i < x-1; i++)
 {
  
 
  for(j=i; j < x-1; j++)
 
  { 
        printf(" if %d > %d \n",a[j], a[j+1]);
   if (a[j] > a[j+1])
   {
        printf("then swap them");
   swap(&a[j], &a[j+1]);
   }
  }
 }
 
}
  int main()  
  {  
  
      int a[100],x,i;  
  
        
  
      printf(" Spots in array: \n ");  
      scanf("%d",&x);  
  
      for( i=0;i<x;i++)  
  { 
      printf("\n\n Spot %d in array : ",i+1);  
              scanf("%d",&a[i]);  
  }  
  
       sort(&a[0],x);
  
       printf("\n\n\n\n\n iSort \n\n");  
       for( i=0;i<x;i++)
       {
       printf("%d\n",a[i]);  
       }
  
  system("Pause");
  }

Success!

A big problem in this coding was using pointers for the sorting function and calling it in main().
another problem was not having the exact logic behind a selection sort. Adding print statements in loops can help a lot. Thanks to everyone for their help here.

std10093 You had mentioned earlier about trusting a user. I'm guessing your talking about a flaw I have in this. Although this is simple I would like to start implementing security features early on. Any advice on improvement is appreciated.

Originally Posted by Andersonsacanno

[code]
std10093 You had mentioned earlier about trusting a user. I'm guessing your talking about a flaw I have in this. Although this is simple I would like to start implementing security features early on. Any advice on improvement is appreciated.

You let the user input the size of spots.If the user inputs a negative or zero number,then you will set the number of spots to a negative or zero number , which does not make any sense. Remember that he may by accident input that number.It would be nice to inform him.In addition inform him that no sorting is going to take place.
You do not have a security issue here, but in general you should always check if the input is satisfying some requirements.Consider this example.We have an array of ten elements and we want the user to input a number, so that we access the element in this specific index.

Code:

#include <stdio.h>

int main(void)
{
     int a[5];
     int i;
     int request;
  
     for( i = 0 ; i < 5 ; i++)
     {
             a[i] = 7;
      }
  
      printf("Please type the number of element you want to access.Indexing starts from zero\n"); 
      scanf("%d",&request);

      printf("Element in index %d is %d \n",request,a[request]);

      return 0;
}

What will happen if by accident or for other reason i type -1?You are going to access the -1-th element of array a, in other words a[-1], which of course is an error.
So, modify the code to this :

Code:

#include <stdio.h>

int main(void)
{
     int a[5];
     int i;
     int request;
  
     for( i = 0 ; i < 5 ; i++)
     {
             a[i] = 7;
      }
  
      do{
          printf("Please type the number of element you want to access.Indexing starts from zero\nNotice that input must be a positive, non-zero number\n"); 
          scanf("%d",&request);
      }while(request<=0);

      printf("Element in index %d is %d \n",request,a[request]);

      return 0;
}

But what if the user inputs an index greater than the index of last element(in this case 4) ?Again, an error is likely to occur .
Again modify the code to this

Code:

#include <stdio.h>

int main(void)
{
     int a[5];
     int i;
     int request;

     for( i = 0 ; i < 5 ; i++)
     {
             a[i] = 7;
      }

      do{
          printf("Please type the number of element you want to access.\n");
          printf("Input must be in range of 0 to 4.\n");
          scanf("%d",&request);
      }while(request<=0 || request>4);

      printf("Element in index %d is %d \n",request,a[request]);

      return 0;
}

PS - i am telling you from the start that this is not selection sort.Adak also states that.

The do while loop will force the user to input again, if "wrong" input is given.

Wow guys thanks for all the help!

Our pleasure!I also guess that this is your first thread,so welcome to the forum