How to use selection sort algorithm correctly to sort a list?

Question

I cannot get this to work, seems like whatever I do it never sorts correctly.

I am trying to sort in a descending order based on number of points.

Bryan_Bickell         2    5    +2

Brandon_Bolig         0    3     0

Dave_Bolland          4    2    -1

Sheldon_Brookbank     0    4   -1

Daniel_Carcillo       0    1    +3

The middle column is the amount of points.

I am using 4 arrays to store all of those values, how would I correctly utilize the array selection sort to get it to order in the right way?

I had tried all the answers below but none of them seemed to work, this is what i have so far

void sortArrays( string playerNames[], int goals[], int assists[], int rating[], int numPlayers )
{
int temp, imin;
int points[numPlayers];

 for(int j = 0; j < numPlayers; j++)
    {
        points[j] = goals[j] + assists[j];
    }

    imin = points[0];

for(int i = 0; i < numPlayers; i++)
{
  if (points[i] < imin)
  {
        imin = points[i];
   }
}

 for(int j = 1; j < numPlayers; j++)
{
    if (points[j] > imin)
    {
        temp = points[j];
          points[j] = points[j-1];
               points[j-1] = temp;
    }
}
}

i guess you need to revise your thinking...selection sort deals with finding the minimum value in each iteration...your are not setting any minimum...pls refer stackoverflow.com/questions/8362640/… — karan
– karan, Commented Mar 29, 2013 at 19:36
Your "swap" is buggy; note that the variable temp is never set. Also, your code looks like it's part of a bubble sort, not a selection sort. — comingstorm
– comingstorm, Commented Mar 29, 2013 at 19:39
There is std::swap for this ;) -> using std::swap; ... swap(points[i], points[i+1]); — leemes
– leemes, Commented Mar 29, 2013 at 19:45
If you've got 4 parallel arrays, your swapping code needs to work on all 4 arrays in parallel. You'd do better with one array of structures; presumably, you haven't covered that yet. — Jonathan Leffler
– Jonathan Leffler, Commented Mar 29, 2013 at 19:47
I want to first get the sort to sort out the points, then handling all 4 arrays would be a breeze after function is down. — Scholar
– Scholar, Commented Mar 29, 2013 at 20:53

taocp · Accepted Answer · 2013-03-29 19:50:59Z

3

it should go like this...

void selsort(int *a,int size)
{
   int i,j,imin,temp;
   //cnt++;
   for(j=0;j<size;j++)
   {
       //cnt+=2;
       imin=j;
       for(i=j+1;i<size;i++)
       {
           //cnt+=2;
          if(a[i]<a[imin])
          {
             //cnt++;
             imin=i;
          }
        }

        if(imin!=j)
        {
            //cnt+=3;
            temp=a[j];
            a[j]=a[imin];
            a[imin]=temp;
         }
    }
}

edited Mar 29, 2013 at 19:50

taocp

23.7k10 gold badges52 silver badges62 bronze badges

answered Mar 29, 2013 at 19:39

karan

8,8734 gold badges45 silver badges81 bronze badges

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

3 Comments

karan Over a year ago

a will be your required array

Valentin Over a year ago

shouldn't i be j<size-1? otherwise the last i=j+1 will exceed array bounds

karan Over a year ago

call is something like this...for(i=0;i<ip;i++) a[i]=i; selsort(a,ip);

taocp · Accepted Answer · 2013-03-29 19:49:07Z

1

You don't need 4 arrays to store those records if only the middle column is used for sorting, i.e, keys used for sorting the records. From my understanding, you are trying to sort those records of people based on the number of points with selection sort. Code should look like the following: assuming records is your array of records

void selectionSort(RECORD records[], int n) {
  int i, j, minIndex, tmp;    
  for (i = 0; i < n - 1; i++) {
        maxIndex = i;
        for (j = i + 1; j < n; j++)  //find the current max
        {
              if (records[j].point > records[minIndex].point)
              {
                    //assume point is the number of point, middle column
                    minIndex = j;
              }
        }

        //put current max point record at correct position
        if (minIndex != i) {
              tmp = records[i];
              records[i] = records[minIndex];
              records[minIndex] = tmp;
        }
  }
}

It will sort all your records in "descending order" as you want

edited Mar 29, 2013 at 19:49

answered Mar 29, 2013 at 19:41

taocp

23.7k10 gold badges52 silver badges62 bronze badges

2 Comments

Useless Over a year ago

NB. the .point bit isn't correct if using int records[] ... I assume that was from another draft using a struct?

taocp Over a year ago

@Useless yeah, I was careless, I meant an array of structs. Thanks!

LemonCool · Accepted Answer · 2013-03-29 20:26:50Z

0

how about store the data into a std::vector then sort it

int compare(int a, int b){
 return (a>b);
}

void sort(std::vector<int> &data){
 std::sort(data.begin(), data.end(), compare);
}

try to use vector as much possible, they have been heavy optimized for performance and better memory usage

answered Mar 29, 2013 at 20:26

LemonCool

1,27010 silver badges20 bronze badges

Collectives™ on Stack Overflow

How to use selection sort algorithm correctly to sort a list?

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related