Searching an array and transporting items fitting criteria into another smaller array

Hello, have a problem.

Basically, I have an large array. I want to take the 10 smallest numbers out of a large list (200 and can vary). Doing so by taking the numbers that fit this criteria and placing it into a smaller, and sorted, array. Using just a bubble sort for the 10 element array.

First though, just hardcoding an array to try and get it to work.

Code:

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

#define N  10
#define X  15

/* This program shows you how to a psuedo insertion sort.
*/

int main(void)
{
   float *array, *data, value, dump;
   int index_of_min;
   int i, j, z;
   int flag;

   array = malloc(N * sizeof(float));
   data = malloc(X * sizeof(float));

/* Fill in data */
   for(i = 0; i < X; i++){
       if(i == 0)
          data[i] = 23.0;
       if(i < 5 && i != 0)
          data[i] = i * 3.5;
       if(i >= 5)
          data[i] = i + 2;
   }

   for(i = 0; i < N; i++){
       array[i] = 99999.0;
   }

/* Print data out first */
   printf("The data set is:\n");
   for(i = 0; i<X; i++){
      printf("data[%d] = %f\n", i, data[i]);
   }

   printf("*** ----------------------------------------------- ***\n");

   printf("The ARRAY of smallest ten is:\n");
   for(i = 0; i<N; i++){
      printf("array[%d] = %f\n", i, array[i]);
   }

   printf("*** ----------------------------------------------- ***\n");


/* Loop through observations. */
   for(z = 0; z < X; z++){
      flag = 0;
      if(data[z] < array[9]){
         array[9] = data[z];
         dump = array[9];
         flag = 1;
      }

/* Sort the limited array of 10 with the new element */ 
      if(flag == 1){

         for(i = 0; i < N; i++){
            for(j = 0; j < N-1; j++){
               if(array[j]>array[j+1]){
                  value = array[j+1];
                  array[j+1] = array[j];
                  array[j] = value;
               }
            }
         }
/*
         for(i = (N - 1); i >= 0; i--){
            for(j = 1; j <= i; j++){
               if(array[j-1] > array[j]){
                  value = array[j-1];
                  array[j-1] = array[j];
                  array[j] = value;
               }
            }
         }
*/
      }
/* End sort */
   }

/* *************************************************************** */

/* Print out the 10 smallest */
   printf("The smallest elements of the data set sorted is:\n");
   for(i = 0; i<N; i++){
      printf("array[%d] = %f\n", i, data[i]);
   }

   free(data);
   free(array);

   return 0;
}

As you can see, I have also done the bubble sort on a smaller list just to see if that algorithm works -- it does... It seems my method is write and I tried doing by hand and to me -- it should work. Any ideas!

Also, I know the bubble sort is not looked upon highly. I will probably change to an insertion method - but first want to get it done with that alogirthm.

I get output like:

Code:

The data set is:
data[0] = 23.000000
data[1] = 3.500000
data[2] = 7.000000
data[3] = 10.500000
data[4] = 14.000000
data[5] = 7.000000
data[6] = 8.000000
data[7] = 9.000000
data[8] = 10.000000
data[9] = 11.000000
data[10] = 12.000000
data[11] = 13.000000
data[12] = 14.000000
data[13] = 15.000000
data[14] = 16.000000
*** ----------------------------------------------- ***
The ARRAY of smallest ten is:
array[0] = 99999.000000
array[1] = 99999.000000
array[2] = 99999.000000
array[3] = 99999.000000
array[4] = 99999.000000
array[5] = 99999.000000
array[6] = 99999.000000
array[7] = 99999.000000
array[8] = 99999.000000
array[9] = 99999.000000
*** ----------------------------------------------- ***
The smallest elements of the data set sorted is:
array[0] = 23.000000
array[1] = 3.500000
array[2] = 7.000000
array[3] = 10.500000
array[4] = 14.000000
array[5] = 7.000000
array[6] = 8.000000
array[7] = 9.000000
array[8] = 10.000000
array[9] = 11.000000

Just a small note - your sort is fine for such a small number of items. It is not a bubble sort, however. Bubble sort compares adjacent values in the array, so your sort is definitely LIKE a bubble sort, but it won't quite "bubble" the same way.

It would be a HUGE help if you would tell us WHAT is the problem you see with the code, right up front. I absolutely do NOT understand this way of asking for help, but not telling us what is the specific problem.

Are you getting a seg fault, a warning from the compiler, values in the wrong places in the array, etc.

Sorry, problem is that it doesn't sort the "mini" array. IT just places the values and shuffles them to the front, one after the other - doesn't sort... (note, i replaced the sorting algorithm with the bubble sort from this website).

I get output like:

Code:

The data set is:
data[0] = 23.000000
data[1] = 3.500000
data[2] = 7.000000
data[3] = 10.500000
data[4] = 14.000000
data[5] = 7.000000
data[6] = 8.000000
data[7] = 9.000000
data[8] = 10.000000
data[9] = 11.000000
data[10] = 12.000000
data[11] = 13.000000
data[12] = 14.000000
data[13] = 15.000000
data[14] = 16.000000
*** ----------------------------------------------- ***
The ARRAY of smallest ten is:
array[0] = 99999.000000
array[1] = 99999.000000
array[2] = 99999.000000
array[3] = 99999.000000
array[4] = 99999.000000
array[5] = 99999.000000
array[6] = 99999.000000
array[7] = 99999.000000
array[8] = 99999.000000
array[9] = 99999.000000
*** ----------------------------------------------- ***
The smallest elements of the data set sorted is:
array[0] = 23.000000
array[1] = 3.500000
array[2] = 7.000000
array[3] = 10.500000
array[4] = 14.000000
array[5] = 7.000000
array[6] = 8.000000
array[7] = 9.000000
array[8] = 10.000000
array[9] = 11.000000

Well, use this one:

Code:

for(i=0;i<N-1;i++)  {
  for(j=i+1;j<N;j++)  {
    if(a[i] > a[j])  {   // <--if you want descending order? change > to < 
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }     
  }
}

This is Selection sort - also very close to a Bubble sort (just a tad faster).

There are a LOT of different ways to make a simple sort like Bubble sort - and sometimes they are referred to as "Bubble" sorts - I've done it, myself. The thing to remember about them, is that a Bubble sort ALWAYS compares adjacent elements or values.

Alright, I replaced it with the new algorithm but I am still getting the same incorrect output. Really don't know why it isn't working. It seems to be shuffling just the first 10 elements in to the smaller array and that is it, and not looking at to see if it is smaller or larger and if it should sort the smaller array..

Initialize smaller array to really large numbers.
It loops through obs.
If an obs is less than the last element, it takes its place in the smaller 10 element array.
It then sorts that array.
Goes on to next obs/value

CODE:

Code:

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

#define N  10
#define X  15

/* This program shows you how to a psuedo insertion sort.
*/

int main(void)
{
   float *array, *data, value, dump;
   int i, j, z;
   int flag;

   array = malloc(N * sizeof(float));
   data = malloc(X * sizeof(float));

/* Fill in data */
   for(i = 0; i < X; i++){
       if(i == 0)
          data[i] = 23.0;
       if(i < 5 && i != 0)
          data[i] = i * 3.5;
       if(i >= 5)
          data[i] = i + 2;
   }

   for(i = 0; i < N; i++){
       array[i] = 99999.0;
   }

/* Print data out first */
   printf("The data set is:\n");
   for(i = 0; i<X; i++){
      printf("data[%d] = %f\n", i, data[i]);
   }

   printf("*** ----------------------------------------------- ***\n");

   printf("The ARRAY of smallest ten is:\n");
   for(i = 0; i<N; i++){
      printf("array[%d] = %f\n", i, array[i]);
   }

   printf("*** ----------------------------------------------- ***\n");


/* Loop through observations. */
   for(z = 0; z < X; z++){
      flag = 0;
      if(data[z] < array[9]){
         array[9] = data[z];
         dump = array[9];
         flag = 1;
      }

/* Sort the limited array of 10 with the new element */ 
      if(flag == 1){

         for(i = 0; i < N-1 ; i++){
            for(j = i+1; j < N; j++){
               if(array[i] > array[j]){ /* > for ascending order */
                  value = array[i];
                  array[i] = array[j];
                  array[j] = value;
               }
            }
         }
/*
         for(i = 0; i < N; i++){
            for(j = 0; j < N-1; j++){
               if(array[j]>array[j+1]){
                  value = array[j+1];
                  array[j+1] = array[j];
                  array[j] = value;
               }
            }
         }
*/
/*
         for(i = (N - 1); i >= 0; i--){
            for(j = 1; j <= i; j++){
               if(array[j-1] > array[j]){
                  value = array[j-1];
                  array[j-1] = array[j];
                  array[j] = value;
               }
            }
         }
*/

      }
/* End sort */
   }

/* *************************************************************** */

/* Print out the 10 smallest */
   printf("The smallest elements of the data set sorted is:\n");
   for(i = 0; i<N; i++){
      printf("array[%d] = %f\n", i, data[i]);
   }

/* *************************************************************** */

   free(data);
   free(array);

   return 0;
}

Output:
The data set is:
data[0] = 23.000000
data[1] = 3.500000
data[2] = 7.000000
data[3] = 10.500000
data[4] = 14.000000
data[5] = 7.000000
data[6] = 8.000000
data[7] = 9.000000
data[8] = 10.000000
data[9] = 11.000000
data[10] = 12.000000
data[11] = 13.000000
data[12] = 14.000000
data[13] = 15.000000
data[14] = 16.000000
*** ----------------------------------------------- ***
The ARRAY of smallest ten is initially:
array[0] = 99999.000000
array[1] = 99999.000000
array[2] = 99999.000000
array[3] = 99999.000000
array[4] = 99999.000000
array[5] = 99999.000000
array[6] = 99999.000000
array[7] = 99999.000000
array[8] = 99999.000000
array[9] = 99999.000000
*** ----------------------------------------------- ***
The smallest elements of the data set sorted is:
array[0] = 23.000000
array[1] = 3.500000
array[2] = 7.000000
array[3] = 10.500000
array[4] = 14.000000
array[5] = 7.000000
array[6] = 8.000000
array[7] = 9.000000
array[8] = 10.000000
array[9] = 11.000000

Code:

   /* Loop through observations. */
   for(z = 0; z < X; z++){
      flag = 0;
      if(data[z] < array[9]){
         array[9] = data[z];
         dump = array[9];
         flag = 1;
      }

Is the Little Array from Smallest to biggest or Biggest to Smallest?
In other words; when sorted is array[9] the biggest or the smallest value?



Tim S.

Code:

printf("array[%d] = %f\n", i, data[i]);

Fixed below

Code:

printf("array[%d] = %f\n", i, array[i]);

Wow, so it worked the whole time - just have not been printing the right thing out.. I feel dumb!
Ugh

Originally Posted by Adak

Well, use this one:

Code:

for(i=0;i<N-1;i++)  {
  for(j=i+1;j<N;j++)  {
    if(a[i] > a[j])  {   // <--if you want descending order? change > to < 
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }     
  }
}

This is Selection sort - also very close to a Bubble sort (just a tad faster).

There are a LOT of different ways to make a simple sort like Bubble sort - and sometimes they are referred to as "Bubble" sorts - I've done it, myself. The thing to remember about them, is that a Bubble sort ALWAYS compares adjacent elements or values.

Adak, is that really selection sort? Upon looking at Cprogramming.com - Algorithms - Insertion Sort and Selection Sort, it doesn't look like selection sort... It never establishes what the minimum value is. So... is it like a insertion?

Well, ... no. It has a history, actually. When I took my class in programming, they didn't have "laptops", or a computer lab that would hold even 1/4th of the class - so we were told it would be a "Le Mans start", for the final; meaning a dash to your car, drive home, do the test, and return within 3 hours.

So obviously, time was of the essence here, and you just knew that something with sorting was going to be on that final test.

So I picked out selection sort and memorized it. But then I noticed that I could simplify it, and it still worked fine - and made it easier/quicker, for me. What I posted up there, was the result.

I used to call it "Bubble sort", but iMalc corrected me on that, since it doesn't compare adjacent values. So I called it "Selection sort, because it still is close to it, and the performance is better than bubble sort, but worse than insertion sort, so it fits right into this "family" - but there is no scanning for a minimum value.

So maybe it's best to call it "EZ" sort. Except for Gnome sort, it's the easiest sort I know of, and it's easy for me, at least, because I already have it memorized.

Seriously, it's EZ because it has two increments, i and j, and one other variable other than the array, of temp. Both i and j only increment, none of this "one goes up and the other goes down", stuff, and there is no "transfer this value over here, then back over there", logic, like a true Selection sort. This one is from Wikibooks, and selects the largest array members, but it's still obviously, selection sort.

Code:

void selection(int *array, int length)
{
    int max, i, temp;
    while(length > 0)
    {
        max = 0;
        for(i = 1; i < length; i++)
            if(array[i] > array[max])
                max = i;
        temp = array[length-1];
        array[length-1] = array[max];
        array[max] = temp;
        length--;
    }
}

It's definitely not Insertion sort - too slow for that.

One BIG difference with Selection sort is that Selection has the fewest number of swaps, possible. Less than any other sorting algorithm. EZ doesn't select and hold a value, so it doesn't share that low number of swaps, property. It has fewer than Bubble sort however, since it swaps across a greater distance, which is a big advantage generally.