Сортировка пузырьком в коде Qualcomm

Забавной находкой поделился сегодня пользователь fj333 с Reddit. Разбираясь в появившемся год назад проприетарном коде Qualcomm Technologies для Android, он обнаружил, что неизвестный программист решил в production-коде использовать сортировку пузырьком для того, чтобы найти… максимум в массиве.

Посмотреть исходный файл вы сможете по ссылке на Github или же под катом, а оценить его в работе может любой владелец устройства с Qualcomm Snapdragon 200 MSM8610 под управлением Android.

Как известно любому, кто знаком с алгоритмами сортировки, сортировка пузырьком — алгоритм учебный, и в промышленном коде не применяющийся в силу своей неэффективности; дело в том, что в наихудшем и среднем случаях он имеет сложность О(n²), к тому же его емкостная сложность в данном случае — O(n). Кого это не убедило — использовать сортировку пузырьком не рекомендует даже Барак Обама.

И это всё не учитывая того, что для поиска максимума хватило бы и простого перебора.

#ifndef ABS
#define ABS(x)            (((x) < 0) ? -(x) : (x))
#endif

/*==============================================================================
 * Function:           bubblesort
 *
 * Description: Subroutine for sorting 1-D array elements
 *
 * Parameters: double *x    --->   input one-dimensional array
 *             int n        --->   size of input array
 *             int *m       --->   indices of sorted elements
 *============================================================================*/
void bubblesort(double *x, int n, int *m)
{
  int i, j, t1;
  double t2;

  for(i = 0; i < n; i++)
    m[i] = i;

  for(i = 0; i < n; i++) {
    for(j = 0; j <n-1; j++) {
      if(x[j] < x[j+1]) {
        t2 = x[j+1];
        x[j+1] = x[j];
        x[j] = t2;
        t1 = m[j+1];
        m[j+1] = m[j];
        m[j] = t1;
      }
    }
  }
} /* bubblesort */

/*==============================================================================
 * Function:           absmax
 *
 * Description:
 *
 * Parameters: double *x    --->   input one-dimensional array
 *             int n        --->   size of input array
 *============================================================================*/
double absmax(double *x, int n)
{
  int j, *l;
  int index = 0;
  double *y;

  l = (int *)malloc(n * sizeof(int));
  if (NULL == l) {
    CDBG("%s: Error mem alloc for l.n", __func__);
    return -1;
  }

  y = (double *)malloc(n * sizeof(double));
  if (NULL == y) {
    free(l);
    CDBG("%s: Error mem alloc for y.n", __func__);
    return -1;
  }
  for(j = 0; j < n; j++)
    y[j] = ABS(x[j]);
  bubblesort(y, n, l);
  index = l[0];

  free(l);
  free(y);
  return ABS(x[index]);
}

Проводилось ли Code Review? Об этом история умалчивает…

Автор: Владимир Маслов

Источник