{"id":758,"date":"2018-11-07T14:28:05","date_gmt":"2018-11-07T16:28:05","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/programacao\/?p=758"},"modified":"2021-06-18T14:57:33","modified_gmt":"2021-06-18T17:57:33","slug":"utilizacao-funcao-qsort","status":"publish","type":"post","link":"http:\/\/www.galirows.com.br\/meublog\/programacao\/utilizacao-funcao-qsort\/","title":{"rendered":"Utiliza\u00e7\u00e3o da fun\u00e7\u00e3o QSort em C"},"content":{"rendered":"\n<p>A fun\u00e7\u00e3o qsort() \u00e9 uma fun\u00e7\u00e3o em C utilizada para ordena\u00e7\u00e3o de arrays. O prot\u00f3tipo da fun\u00e7\u00e3o \u00e9 <em>void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))<\/em>, onde <em>base<\/em> \u00e9 um ponteiro para o primeiro elemento do array, <em>nitems<\/em> \u00e9 o n\u00famero de elementos do array, <em>size<\/em> \u00e9 o tamanho em bytes de cada elemento do array e <em>compar<\/em> \u00e9 a fun\u00e7\u00e3o criada para o problema e que compara dois elementos.<\/p>\n\n\n\n<p>Os tr\u00eas primeiros par\u00e2metros s\u00e3o simples de fornecer, mas o \u00faltimo exige maior aten\u00e7\u00e3o. Ele consiste de um ponteiro para uma fun\u00e7\u00e3o que \u00e9 respons\u00e1vel por comparar dois valores fornecidos como par\u00e2metro para a fun\u00e7\u00e3o. Essa fun\u00e7\u00e3o dever\u00e1 retornar:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Valor&nbsp;<strong>maior do que zero<\/strong>: se o primeiro valor for maior do que o segundo.<\/li><li>Valor&nbsp;<strong>menor do que zero<\/strong>: se o primeiro valor for menor do que o segundo.<\/li><li><strong>Zero<\/strong>: se os valores forem iguais.<\/li><\/ul>\n\n\n\n<p>Pode parecer estranho ter que fazer uma fun\u00e7\u00e3o que compara valores porque normalmente pensamos em um array com n\u00fameros, mas e se for fornecido um array de valores enumerados, ou um array de alguma struct? Sendo assim, a fun\u00e7\u00e3o qsort() pode ser utilizada para qualquer tipo de dado e por isso ela utiliza um ponteiro void como <em>base<\/em> e \u00e9 preciso elaborar uma fun\u00e7\u00e3o que explica como fazer a compara\u00e7\u00e3o.<\/p>\n\n\n\n<p>O c\u00f3digo a seguir exemplifica o uso da fun\u00e7\u00e3o qsort() em um array. S\u00e3o mostradas duas fun\u00e7\u00f5es para compara\u00e7\u00e3o, mas que apresentam o mesmo resultado.<\/p>\n\n\n\n<p>A fun\u00e7\u00e3o comparador() recebe dois n\u00fameros do array e os compara. Veja que a fun\u00e7\u00e3o recebe dois ponteiros void e por isso \u00e9 preciso fazer o <em>cast<\/em> para o tipo de dado do array, no caso, valores inteiros. Veja tamb\u00e9m que, em vez de fazer uma compara\u00e7\u00e3o com o uso do <em>if<\/em>, foi utilizado simplesmente uma subtra\u00e7\u00e3o dos valores. Se o valor de &#8220;a&#8221; for maior do que o valor de &#8220;b&#8221;, ent\u00e3o o resultado ser\u00e1 maior do que zero significando que o primeiro valor \u00e9 maior do que o segundo. A fun\u00e7\u00e3o comparador2() faz as compara\u00e7\u00f5es utilizando o desvio condicional <em>if<\/em>.<\/p>\n\n\n\n<pre class=\"wp-block-code lang:c decode:true\"><code lang=\"c\" class=\"language-c\">#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\nint comparador(const void *a, const void *b) {\n   return ( *(int*)a - *(int*)b );\n}\n\nint comparador2(const void *a, const void *b) {\n   if (*(int*)a &gt; *(int*)b) {\n      return 1;\n   } else if (*(int*)a &lt; *(int*)b) {\n      return -1;\n   } else {\n      return 0;\n   }\n}\n\nint main () {\n   int i, val[] = { 15, 30, 10, 20, 25 };\n\n   \/\/ordena o array\n   qsort(val, 5, sizeof(int), comparador);\n\n   \/\/mostra os valores do array\n   for( i = 0 ; i &lt; 5; i++ ) {\n      printf(\"%i \", val[i]);\n   }\n\n   return(0);\n}\n<\/code><\/pre>\n\n\n\n<p class=\"has-text-align-right\">Experimente o c\u00f3digo online em: <a href=\"https:\/\/ideone.com\/JwgKmn\" target=\"_blank\" rel=\"noopener\">https:\/\/ideone.com\/JwgKmn<\/a><\/p>\n\n\n\n<p>Veja que a fun\u00e7\u00e3o comparador \u00e9 a respons\u00e1vel por determinar a ordem dos elementos. Da maneira como \u00e9 determinado o valor de retorno, ela far\u00e1 a ordena\u00e7\u00e3o de forma crescente dos valores do array. Se eu inverter as vari\u00e1veis &#8220;a&#8221; e &#8220;b&#8221; na opera\u00e7\u00e3o, fazendo&nbsp;<em>*(int*)b &#8211; *(int*)a<\/em>, isso far\u00e1 com que o vetor passe a ser ordenado de forma decrescente.<\/p>\n\n\n\n<p>Como comentado, a fun\u00e7\u00e3o qsort() pode ser utilizada para comparar qualquer tipo de dado. O c\u00f3digo abaixo mostra sua utiliza\u00e7\u00e3o para ordenar um array de structs. Duas fun\u00e7\u00f5es de compara\u00e7\u00e3o s\u00e3o especificadas. Uma \u00e9 respons\u00e1vel por ordenar as pessoas por idade e a outra por ordenar em ordem alfab\u00e9tica o nome das pessoas.<\/p>\n\n\n\n<pre class=\"wp-block-code lang:c decode:true\"><code lang=\"c\" class=\"language-c\">#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\nstruct pessoa {\n    char nome[20];\n    int idade;\n};\n\nint compararIdade (const void *x, const void *y) {\n    int pri = ((struct pessoa *)x)-&gt;idade;\n    int seg = ((struct pessoa *)y)-&gt;idade;\n    return (pri - seg);\n}\n\nint compararNome (const void *a, const void *b) {\n    return strcmp (((struct pessoa *)a)-&gt;nome,((struct pessoa *)b)-&gt;nome);\n}\n\nint main () {\n   int i;\n   int idades[]={9,7,8,5,2};\n   char nomes[][20] =  {\"Joao\",\"Pedro\",\"Ana\",\"Maria\",\"Teste\"};\n   struct pessoa item[5];\n\n   printf(\"Pessoas sem ordem:\\n\");\n   for (i = 0; i &lt; 5; i++) {\n     strcpy(item[i].nome, nomes[i]);\n     item[i].idade = idades[i];\n     printf(\"%s: %d\\n\", item[i].nome, item[i].idade);\n   }\n\n   qsort(item, 5, sizeof(struct pessoa), compararIdade);\n\n   printf(\"Pessoas ordenadas por idade:\\n\");\n   for (i = 0; i &lt; 5; i++) {\n     printf(\"%s: %d\\n\", item[i].nome, item[i].idade);\n   }\n\n   qsort(item, 5, sizeof(struct pessoa), compararNome);\n\n   printf(\"Pessoas ordenadas por nome:\\n\");\n   for (i = 0; i &lt; 5; i++) {\n     printf(\"%s: %d\\n\", item[i].nome, item[i].idade);\n   }\n\n   return(0);\n}<\/code><\/pre>\n\n\n\n<p class=\"has-text-align-right\">Experimente o c\u00f3digo online em:&nbsp;<a href=\"https:\/\/ideone.com\/IGk2Jv\" target=\"_blank\" rel=\"noopener\">https:\/\/ideone.com\/IGk2Jv<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>A fun\u00e7\u00e3o qsort() \u00e9 uma fun\u00e7\u00e3o em C utilizada para ordena\u00e7\u00e3o de arrays. O prot\u00f3tipo da fun\u00e7\u00e3o \u00e9 void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)), onde base \u00e9 um ponteiro para o primeiro elemento do array, nitems \u00e9 o n\u00famero de elementos do array, size \u00e9 o tamanho em [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[3],"tags":[53],"class_list":["post-758","post","type-post","status-publish","format-standard","hentry","category-c","tag-funcoes"],"aioseo_notices":[],"amp_enabled":true,"_links":{"self":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/758","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/comments?post=758"}],"version-history":[{"count":4,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/758\/revisions"}],"predecessor-version":[{"id":1043,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/758\/revisions\/1043"}],"wp:attachment":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/media?parent=758"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/categories?post=758"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/tags?post=758"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}