{"id":9888,"date":"2025-03-06T15:30:25","date_gmt":"2025-03-06T13:30:25","guid":{"rendered":"https:\/\/blue.pri.ee\/ttu\/?page_id=9888"},"modified":"2025-03-06T15:30:25","modified_gmt":"2025-03-06T13:30:25","slug":"data-type-agnostic-bubble-sort","status":"publish","type":"page","link":"https:\/\/blue.pri.ee\/ttu\/programming-ii\/code-samples\/data-type-agnostic-bubble-sort\/","title":{"rendered":"Data type agnostic bubble sort"},"content":{"rendered":"<p>The following code shows a data type agnostic bubble sort implementation. The purpose of the example is to bring out similarities with the\u00a0 <span class=\"lang:c highlight:0 decode:true crayon-inline\">qsort()<\/span>\u00a0 function call and show why we need to create a comparison function.<\/p>\n<pre class=\"lang:c decode:true \">\/**\r\n * File:         agnostic_bubble.c\r\n * Author:       Risto Heinsar\r\n * Created:      02.03.2025\r\n * Modified      06.03.2025\r\n *\r\n * Description:  Example shows data type agnostic bubble sort. Used too show\r\n *               similarities with qsort() function parameters.\r\n *\/\r\n#include &lt;stdio.h&gt;\r\n#include &lt;stdbool.h&gt;\r\n#include &lt;string.h&gt;\r\n\r\n#define STR_LEN 64\r\n\r\ntypedef unsigned char byte;\r\n\r\nstruct Student\r\n{\r\n    char name[STR_LEN];\r\n    int score;\r\n};\r\n\r\nint ComparInt(const void *pA, const void *pB);\r\nint ComparStudentScore(const void *pA, const void *pB);\r\n\r\nvoid BubbleSort(void *data, size_t n, size_t size, \r\n                int(*Compar)(const void *a, const void *b));\r\n\r\nvoid PrintIntArr(int *data, int n);\r\nvoid PrintStudents(struct Student *data, int n);\r\n\r\nint main(void)\r\n{\r\n    int vals[] = {1, 9, 2, 8, -5, 14};\r\n    int nVals = sizeof(vals) \/ sizeof(int);\r\n    \r\n    struct Student students[] = {{\"Mari\", 75},\r\n                                 {\"Kati\", 50},\r\n                                 {\"Mihkel\", 85},\r\n                                 {\"Priit\", 45},\r\n                                 {\"Tiina\", 68}};\r\n    int nStudents = sizeof(students) \/ sizeof(struct Student);\r\n    \r\n    BubbleSort(vals, (size_t)nVals, sizeof(int), ComparInt);\r\n    BubbleSort(students, (size_t)nStudents, sizeof(struct Student), \r\n               ComparStudentScore);\r\n    \r\n    PrintIntArr(vals, nVals);\r\n    PrintStudents(students, nStudents);\r\n    \r\n    return 0;\r\n}\r\n\r\n\/**\r\n * Description:    Data type agnostic bubble sort\r\n *\r\n * Parameters:     data - array with items to sort\r\n *                 n - number of items\r\n *                 size - size in bytes for each item\r\n *                 Compar - comparison function to identify order of items\r\n *\r\n * Return:         none\r\n *\/\r\nvoid BubbleSort(void *data, size_t n, size_t size, \r\n                int(*Compar)(const void *a, const void *b))\r\n{\r\n    \/* End correction to avoid overflow in comparison *\/\r\n    n = n - 1;\r\n    \r\n    while (1)\r\n    {\r\n        bool sorted = true;\r\n        for (size_t i = 0; i &lt; n; i++)\r\n        {\r\n            \/* Calculate pointers for current and next member *\/\r\n            void *pA = data + i * size;\r\n            void *pB = data + (i + 1) * size;\r\n            \r\n            \/* Check if items are in the wrong order *\/\r\n            if (Compar(pA, pB) &gt; 0)\r\n            {\r\n                \/* Swap the two items *\/\r\n                byte temp[size];\r\n                memcpy(temp, pA, size);\r\n                memcpy(pA, pB, size);\r\n                memcpy(pB, temp, size);\r\n                \r\n                sorted = false;\r\n            }\r\n        }\r\n        \r\n        \/* No swaps, array sorted *\/\r\n        if (sorted)\r\n            return;\r\n        \r\n        n--;\r\n    }\r\n}\r\n\r\n\/**\r\n * Description:    Compares integers based on value\r\n *\r\n * Parameters:     pA - pointer to first integer\r\n *                 pB - pointer to second integer\r\n *\r\n * Return:         &lt; 0 pA has higher value, comes first\r\n *                 = 0 if order doesn't matter\r\n *                 &gt; 0 pB has higher value, comes first\r\n *\/\r\nint ComparInt(const void *pA, const void *pB)\r\n{\r\n    return *(int *)pA - *(int *)pB;\r\n}\r\n\r\n\/**\r\n * Description:    Compares students based on score, descending order\r\n *\r\n * Parameters:     pA - first student struct pointer\r\n *                 pB - pointer to the second student struct\r\n *\r\n * Return:         &lt; 0 pA has higher score, comes first\r\n *                 = 0 if order doesn't matter\r\n *                 &gt; 0 pB has higher score, comes first\r\n *\/\r\nint ComparStudentScore(const void *pA, const void *pB)\r\n{\r\n    return ((struct Student *)pB)-&gt;score - ((struct Student *)pA)-&gt;score;\r\n}\r\n\r\n\r\n\/**\r\n * Description:    Prints the integer array on screen\r\n *\r\n * Parameters:     data - integer array\r\n *                 n - number of integers\r\n *\r\n * Return:         none\r\n *\/\r\nvoid PrintIntArr(int *data, int n)\r\n{\r\n    printf(\"Sorted array (asc):\\n\");\r\n    for (int i = 0; i &lt; n; i++)\r\n    {\r\n        printf(\"%d \", data[i]);\r\n    }\r\n    printf(\"\\n\\n\");\r\n}\r\n\r\n\r\n\/**\r\n * Description:    Prints the student struct array on screen\r\n *\r\n * Parameters:     data - student struct array\r\n *                 n - number of students\r\n *\r\n * Return:         none\r\n *\/\r\nvoid PrintStudents(struct Student *data, int n)\r\n{\r\n    printf(\"Top students:\\n\");\r\n    for (int i = 0; i &lt; n; i++)\r\n    {\r\n        printf(\"%15s %3d\\n\", data[i].name, data[i].score);\r\n    }\r\n    printf(\"\\n\");\r\n}\r\n<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The following code shows a data type agnostic bubble sort implementation. The purpose of the example is to bring out similarities with the\u00a0 qsort()\u00a0 function call and show why we need to create a comparison function. \/** * File: agnostic_bubble.c * Author: Risto Heinsar * Created: 02.03.2025 * Modified 06.03.2025 * * Description: Example shows &hellip; <a href=\"https:\/\/blue.pri.ee\/ttu\/programming-ii\/code-samples\/data-type-agnostic-bubble-sort\/\" class=\"more-link\">Loe edasi <span class=\"screen-reader-text\">Data type agnostic bubble sort<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":2361,"menu_order":7,"comment_status":"closed","ping_status":"closed","template":"page-templates\/code-width-wide.php","meta":{"footnotes":""},"class_list":["post-9888","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/pages\/9888","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/comments?post=9888"}],"version-history":[{"count":1,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/pages\/9888\/revisions"}],"predecessor-version":[{"id":9889,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/pages\/9888\/revisions\/9889"}],"up":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/pages\/2361"}],"wp:attachment":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/media?parent=9888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}