Sort numbers according to n-th term

Question

I know how to sort an array(i.e. bubble sort) but I don't have any idea how I can sort an array according to n-th term. Could you give me idea or example if there is? Thank you for all appreciated answer. @edit: how can be the program sensed a number with zeros I mean for 1 program sense 0001 or 00001 .... ?

Example:
2 --> nth digit
4 45 62 1 900 105 --> inputs

Output: 001 004 105 900 045 065

---

void bubble_sort(int iarr[], int num) {
   int i, j, k, temp;

   printf("\nUnsorted Data:");
   for (k = 0; k < num; k++) {
      printf("%5d", iarr[k]);
   }

   for (i = 1; i < num; i++) {
      for (j = 0; j < num - 1; j++) {
         if (iarr[j] > iarr[j + 1]) {
            temp = iarr[j];
            iarr[j] = iarr[j + 1];
            iarr[j + 1] = temp;
         }
      }

      printf("\nAfter pass %d : ", i);
      for (k = 0; k < num; k++) {
         printf("%5d", iarr[k]);
      }
   }
}

Answer 1

The quick answer is that your comparison function needs to look at the n-th digit instead of the whole number.

So if your original comparison was something like:

if (a < b)     // handle a before b case
elseif (b < a) // handle b before a case

you'll want to change it to be:

aDigit = getNthDigit(a, n);
bDigit = getNthDigit(b, n);

if (aDigit < bDigit)     // handle a before b case
elseif (bDigit < aDigit) // handle b before a case

You'll also have to implement getNthDigit, which would involve integer division and modulus operators.

Answer 2

Take a look at qsort for what a generic sort function requires. For your specific question, look at the sort algorithm you want to implement (i.e. bubble sort), and replace comparisons of elements with a function call to an order function. Your compare function should then extract the second digit and compare those digits.

Based on your code, you should change if (iarr[j] > iarr[j + 1]) with if(comp_gt(iarr[j], iarr[j + 1])). And, I would implement comp_gt by

int comp_gt(int a, int b)
{
    int a_second_digit = (a / 10) % 10;
    int b_second_digit = (b / 10) % 10;

    return (a_second_digit < b_second_digit);
}

Answer 3

It means that you sort the numbers based on their n-th digit.

In the example you have, you see that the bolded digits (the second digit in every number) are the ones who define the order of the output.

Here is an example on how you can solve it (I am tuning it right now, because the method it uses to find a digit is wrong):

#include <stdio.h>
#include <math.h>

void quickSort(int a[], int first, int last, int n_th);
int pivot(int a[], int first, int last, int n_th);
void swap(int* a, int* b);
int n_th_digit(int number, int n);
void print(int array[], const int N);

int main() {
  int test[] = { 7, 9, 1, 3, 6, 5, 2, 4 };
  int N = sizeof(test) / sizeof(int);
  int n_th = 0;  // digit(from the end) to sort by

  printf("Size of test array : %d\n", N);

  printf("Before sorting : \n");
  print(test, N);

  quickSort(test, 0, N - 1, n_th);

  printf("After sorting : \n");
  print(test, N);

  return 0;
}

/**
 * Quicksort.
 * @param a The array to be sorted.
 * @param first The start of the sequence to be sorted.
 * @param last The end of the sequence to be sorted.
 * @param n_th The digit to sort by
 */
void quickSort(int a[], int first, int last, int n_th) {
  int pivotElement;

  if (first < last) {
    pivotElement = pivot(a, first, last, n_th);
    quickSort(a, first, pivotElement - 1, n_th);
    quickSort(a, pivotElement + 1, last, n_th);
  }
}

/**
 * Find and return the index of pivot element.
 * @param a The array.
 * @param first The start of the sequence.
 * @param last The end of the sequence.
 * @param n_th The digit to sort by
 * For example the third digit of 137
 * requires n_th to be 0.
 *
 */
int pivot(int a[], int first, int last, int n_th) {
  int i, p = first;
  int pivotElement = a[first];

  for (i = first + 1; i <= last; i++) {
    if (n_th_digit(a[i], n_th) <= n_th_digit(pivotElement, n_th)) {
      p++;
      swap(&a[i], &a[p]);
    }
  }

  swap(&a[p], &a[first]);

  return p;
}

/**
 * Swap the parameters.
 * @param a The first parameter.
 * @param a The second parameter.
 */
void swap(int* a, int* b) {
  // You still can use the swap that
  // does not uses an extra variable
  // from the C++ implementation.
  int temp = *a;
  *a = *b;
  *b = temp;
}

int n_th_digit(int number, int n) {
  if (number < 0)
    number *= -1;
  return fmod((number / pow(10, n)), 10);
}

/**
 * Print an array.
 * @param a The array.
 * @param N The size of the array.
 */
void print(int a[], const int N) {
  int i;
  for (i = 0; i < N; i++)
    printf("array[%d] = %d\n", i, a[i]);
}

I got the how to find the n-th digit from here and the quicksort from here.

Answer 4

Replace

void bubble_sort(int iarr[], int num) {
  ....
  if (iarr[j] > iarr[j + 1])

With

void bubble_sort(int iarr[], int num, int term) {
  unsigned pow10 = upow10(term - 1);
  ....
  if (compareu(iarr[j], iarr[j + 1], pow10) > 0) 

---

// To calculate pow(10, x) quickly
static unsigned upow10(unsigned y) {
  unsigned z = 1;
  unsigned base = 10;
  while (y) {
    if (y & 1) {
      z *= base;
    }
    y >>= 1;
    base *= base;
  }
  return z;
}

int compareu(int a1, int a2, unsigned pow10) {
  unsigned b1 = abs(a1);
  unsigned b2 = abs(a2);
  b1 = (b1 / pow10) % 10;
  b2 = (b2 / pow10) % 10;
  if (b1 > b2) return 1;
  if (b1 < b2) return -1;
  return (a1 > a2) - (a1 < a2);
}

---

[Edit] per OP's update

Q: how can be the program sensed a number with zeros I mean for 1 program sense 0001 or 00001?
A: That is part of the code that reads input which is not posted. If code needs to distinguish between "0001" and "00001", then the whole problem is one of strings and not integers. In that case save each element as a string and do compares from a textual point-of-view.

Yet I suspect that is not the true coding goal. Simply use arithmetical compares and not be concerned with differing leading zeros.

The printf() function is another matter. To print at least term digits with leading 0, use "%0*d".

term = 2; // or 6 or 9, etc.
// printf("%5d", iarr[k]);
printf("%0*d ", term, iarr[k]);