Algorithms
Raiting:
5

Sort by bubble in Qualcomm code


An amusing find was shared today by the user fj333 with Reddit . Analyzing Qualcomm Technologies' proprietary code for Android, which appeared one year ago, he found that an unknown programmer decided to use the sorting with a bubble in production-code in order to find ... maximum in the array.

You can view the original file by under the link to Github or under the cut, and any owner of the device with Qualcomm Snapdragon 200 MSM8610 running Android can estimate it in operation.

As anyone who is familiar with sorting algorithms knows, sorting by a bubble is an educational algorithm, and in industrial code it is usually not used due to its inefficiency ; The matter is that in the worst and average cases it has the complexity O (n2) , besides its capacitive complexity in this case - O (n) . Whom it was not convinced - to use the sorting by a bubble does not recommend even Barack Obama .

And this is all not taking into account the fact that to search for the maximum would be enough and a simple search.

#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]);
}
Was there a Code Review? The story is silent about this ...
v1d0q 22 september 2017, 14:54
Vote for this post
Bring it to the Main Page
 

Comments

Leave a Reply

B
I
U
S
Help
Avaible tags
  • <b>...</b>highlighting important text on the page in bold
  • <i>..</i>highlighting important text on the page in italic
  • <u>...</u>allocated with tag <u> text shownas underlined
  • <s>...</s>allocated with tag <s> text shown as strikethrough
  • <sup>...</sup>, <sub>...</sub>text in the tag <sup> appears as a superscript, <sub> - subscript
  • <blockquote>...</blockquote>For  highlight citation, use the tag <blockquote>
  • <code lang="lang">...</code>highlighting the program code (supported by bash, cpp, cs, css, xml, html, java, javascript, lisp, lua, php, perl, python, ruby, sql, scala, text)
  • <a href="http://...">...</a>link, specify the desired Internet address in the href attribute
  • <img src="http://..." alt="text" />specify the full path of image in the src attribute