How to sort array as to get all the numbers that are the same to the beginning of the array-CodePudding

I am working on a program from a yahtzee and I am trying to get all the cases where different points are given to for example 3 of a kind, 4 or a kind etc.

For that purpose I thought of arranging the values of the player dice and verifying if the first x where equal and going from there. I tried doing a selection sort and bubble sort but couldnt get them to work as they cant decide what to do when the numbers are the same. Any ideas for me to get this working?

This is the code I have tried for that purpose:

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

#define n 5

void
switches(float *v, float *m)
{
    int temp;

    temp = *v;
    *v = *m;
    *m = temp;

}

void
selection(int size, int *v)
{

    int min, i, j;

    for (i = 0; i < n - 1; i  ) {
        for (j = i   1; j < n; j  ) {
            if (v[j] <= v[min])
                min = j;
        }

        if (min != i)
            switches(v[i], v[min]);
    }
}

int
main(void)
{
    int size = n;
    int v[n] = { 2, 1, 3, 3, 3 };
    int m[n] = { 1, 3, 4, 3, 3 };

    selection(n, v);

    for (int i = 0; i < 6; i  )
        printf("The values for the array are:%d\n", v[i]);

    return 0;
}

This is a test code on another file as I havent tried it in the actual program.

CodePudding user response：

A good rule of thumb in C is: When you hear "sort/sorting" and "array" in the same sentence, your first thought should be qsort. (That's probably also why qsort has been mentioned in a number of comments)

An essential part of qsort is the compare-function. The compare-function gets the value of 2 array elements (well, really a pointer to two array element) and solely from those values the compare-function needs to return 1 of the following 3 results:

A before B
B before A
Doesn't matter

In most cases it's possible to write such a compare-function and therefore possible to do the array sorting using qsort.

However... The sorting requested in the question is not solely based on the values of two elements. The requested sorting involves the frequency (aka number of occurences) of each dice value in the whole array.

Since we can't know the frequency of a specific value solely from the value itself, we can't write the compare-function. We would need some extra information that isn't available. So...

The conclusion is: We can't use qsort

Unless... we are willing to "cheat"/"do nasty stuff"/"..."

If we are willing to do that, we can get the extra information into the compare-function by using a (dreaded) global variable (oh dear...).

It could look like the code below. The idea is to count the frequency of each dice value and store it in a global variable before calling qsort. Then the compare-function can access the global variable to retrieve frequency information.

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


// Global variable :-(
int cnt[7];  // 7 elements but element at index zero won't be used
             // as dice values are 1, 2, ..., 6

#define CNT_ARRAY_SIZE (sizeof cnt / sizeof cnt[0])

#define DICES 5

void roll_dices(int n, int roll[])
{
  for (int i=0; i < n;   i) roll[i] = rand() % (CNT_ARRAY_SIZE-1)   1;
}

void print_dices(int n, int roll[])
{
  for (int i=0; i < n;   i) printf("%d ", roll[i]);
}

int cmp(const void *pa, const void *pb)
{
  int a = *(int*)pa;
  int b = *(int*)pb;

  // if A more frequent than B, return -1
  if (cnt[a] > cnt[b]) return -1;

  // if B more frequent than A, return 1
  if (cnt[a] < cnt[b]) return 1;

  // if A greater than B, return -1
  if (a > b) return -1;

  // if B greater than A, return 1
  if (a < b) return 1;

  // Same frequency, same value, retun 0
  return 0;
}

void sort_dices(int n, int roll[])
{
  // Calculate frequency
  for (size_t i=0; i < CNT_ARRAY_SIZE;   i) cnt[i] = 0;
  for (int i=0; i < n;   i)   cnt[roll[i]];

  // Call qsort
  qsort(roll, n, sizeof roll[0], cmp);
}

int main(void) {
  srand(time(NULL));

  int roll[DICES];

  for (int i=0; i < 20;   i)
  {
    roll_dices(DICES, roll);
    print_dices(DICES, roll);
    printf("-> ");
    sort_dices(DICES, roll);
    print_dices(DICES, roll);
    puts("");
  }

  return 0;
}

Example output:

4 5 2 2 4 -> 4 4 2 2 5 
5 5 6 1 4 -> 5 5 6 4 1 
4 6 1 6 6 -> 6 6 6 4 1 
5 2 6 1 3 -> 6 5 3 2 1 
2 5 4 1 2 -> 2 2 5 4 1 
3 2 4 3 4 -> 4 4 3 3 2 
3 6 2 5 6 -> 6 6 5 3 2 
3 3 2 3 1 -> 3 3 3 2 1 
3 4 4 3 2 -> 4 4 3 3 2 
4 6 1 1 4 -> 4 4 1 1 6 
3 2 6 4 2 -> 2 2 6 4 3 
1 4 1 3 1 -> 1 1 1 4 3 
5 5 4 4 1 -> 5 5 4 4 1 
1 1 1 6 1 -> 1 1 1 1 6 
5 2 4 3 3 -> 3 3 5 4 2 
3 4 2 3 4 -> 4 4 3 3 2 
3 4 4 2 1 -> 4 4 3 2 1 
3 1 5 4 3 -> 3 3 5 4 1 
3 2 5 4 5 -> 5 5 4 3 2 
6 5 3 4 4 -> 4 4 6 5 3

note: The main problem with the global variable is that it wont work as is in a multi-thread application. For multi-thread apps some extra code will be required to make sure that two threads doesn't interfere by updating the same global variable at the same time.

CodePudding user response：

BTW, a basic Selection Sort:

void selection_sort_int( int * array, size_t n )
{
  // Each time through this loop the array is one element more sorted
  for (size_t sorted_index = 0;  sorted_index < n-1;  sorted_index  )
  {
    // SUV == “smallest unsorted value”’s index
    size_t suv_index = sorted_index;

    // Find the suv in the remaining (unsorted) array
    for (size_t index = suv_index;  index < n;  index  )
      if (array[index] < array[suv_index])
        suv_index = index;

    swap_int( array sorted_index, array suv_index );
  }
}

We can rewrite that to a much more concise:

void selection_sort_int( int * array, size_t n )
{
  while (n --> 1)
  {
    int * min_value = array;
    for (size_t i = 0;  i < n 1;  i  )
      if (array[i] < *min_value)
        min_value = array   i;
    swap_int( array  , min_value )
  }
}

If you want that to have the same kind of generic interface as qsort() we can do that too. (We’ll just need a generic helper function to swap elements.)

void memswap( void * a, void * b, size_t nbytes )
{
  if (a == b) return;
  unsigned char * x = a;
  unsigned char * y = b;
  while (nbytes--)
  {
    unsigned char c = *x;
    *x   = *y;
    *y   =  c;
  }
}

void selection_sort(
    void * array, size_t n, size_t element_size, 
    int (* compare)( const void *, const void * ) )
{
  char * bytes = array;
  while (n --> 1)
  {
    char * min_value = bytes;
    for (size_t i = 0;  i < n 1;  i  )
      if (compare( bytes   i * element_size, min_value ) < 0)
        min_value = bytes   i * element_size;
    memswap( bytes, min_value, element_size );
    bytes  = element_size;
  }
}

We can use that on an integer array the usual way:

#include <stdio.h>

int compare_ints( const void * a, const void * b )
{
  if (*(const int *)a < *(const int *)b) return -1;
  if (*(const int *)a > *(const int *)b) return  1;
  return 0;
}

#define sizeof_array(xs) (sizeof(xs)/sizeof(xs[0]))

int main(void)
{
  int xs[] = { 3, 4, 2, 7, 3, 6, 7, 1, 5 };

  selection_sort( xs, sizeof_array(xs), sizeof(xs[0]), &compare_ints );

  printf( "%d", xs[0] );
  for (size_t n = 1;  n < sizeof_array(xs);  n  )
    printf( " %d", xs[n] );
  printf( "\n" );

  return 0;
}

Some important points:

Selection Sort is not a stable sort. (That “swap” function in there throws a wrench in that. If you need stable, use Insertion Sort or Merge Sort.)
Selection Sort is rather slow compared to other sorts. You should be using qsort() anyway.

_{PS. I just typed this in off the top of my head. If I’ve made any mistakes, be sure to comment.}

^{PPS. Okay, I think I fixed all the typos.}