Using standard Qsort function in AVR-GCC

Qsort function is a generic sorting function which allows to choose your own sorting criterion. Not often but sometimes you may need to have some sort of array of data. Dont go to much in to it what data type you will be storing in your embedded application but lets say it is a simple notebook based on AVR. Lets analyse simple program how data can be sorted by using function pointer.

Lets start with sample data. In my example I will use simple structure of four fields:

struct persons

{
	char First_Name[31];
	char Last_name[50];
	uint8_t Age;
	uint8_t Address[50];
}

so you may require to sort persons by age, by name. You would write separate sorting functions for string and numerical variables. But there is smarter option- to use qsort() function from stdlib.h library:

void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );

qsort function sorts an array of objects pointed by buf pointer. Each object is specified by its size, num shows the number of object and compare function pointer shows to function which return an integer less then, equal or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

Lets see how does it look in example program:

#include <avr/io.h>
#include <stdlib.h>	//where qsort library is
struct persons {//declare strucutre to be sorted
	uint8_t First_Name[31];
	uint8_t Last_name[50];
	uint8_t age;
	uint8_t Address[50];
};  
typedef struct persons per;//define structure type
int cmp_names(const void *name1, const void *name2)
{
	//comparefunction by First names
    const per *tn1 = name1;
    const per *tn2 = name2;
    return strcmp(tn1->First_Name, tn2->First_Name);
}

int cmp_ages(const void *age1, const void *age2)
{
	//compare function by age
    const per *te1 = age1;
    const per *te2 = age2;
    return te1->age - te2->age;
}
int main(void)
{
per pers[] = //array of person records
    {
        {"Jim",  "Johnson",   45, "Laview 25"},
        {"Tony", "Linger",   49, "46 Mountain"},
        {"Sara", "Evans", 12, "River rd"},
        {"Tom",  "Emers",  45, "Next exit"},
        {"Liza", "Anderson", 54, "Wilkes"}
    };
    //sort structure by First_name
	qsort(pers, 5, sizeof pers[0], cmp_ages);
	//you may print result on LCD
	//sort structure by age
	qsort(pers, 5, sizeof pers[0], cmp_names);
	//you may print result on LCD
	return 0;
}

As wee see using standard sorting function gives us flexibility to use various sorting criteria in a such short program code. But look what I have got after compilation:


AVR Memory Usage

----------------

Device: atmega8

Program: 4904 bytes (59.9% Full)

(.text + .data + .bootloader)

Data: 656 bytes (64.1% Full)

(.data + .bss + .noinit)

 

Flash memory reached 59.9% and RAM 64.1% due to record size of five elements. For bigger data sizes and amount consider of using External memory like SD card or dataflash.

 

If you have limited resources its is better no to use this function as it require big amount of resources including Flash and processing power, better write your own or use more optimal and less universal. In bigger microcontrollers I don't see reason why not except if you want very optimal code running.

 

And note! - This is only demonstration of one of Qsort() algorithm usage which may be used differently depending on requirements.

 

Comments

Holo ,I need qsort a file (.txt) from SD card and i need your help please, if you have a sample code. thanks