// API callback
relpostimgcuplik({"version":"1.0","encoding":"UTF-8","feed":{"xmlns":"http://www.w3.org/2005/Atom","xmlns$openSearch":"http://a9.com/-/spec/opensearchrss/1.0/","xmlns$blogger":"http://schemas.google.com/blogger/2008","xmlns$georss":"http://www.georss.org/georss","xmlns$gd":"http://schemas.google.com/g/2005","xmlns$thr":"http://purl.org/syndication/thread/1.0","id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268"},"updated":{"$t":"2023-07-30T02:11:08.392-07:00"},"category":[{"term":"C Programs"},{"term":"Learn C"},{"term":"Common Programming Error"},{"term":"searching and sorting"},{"term":"control sturctures"},{"term":"Fundamental"},{"term":"List of C Programs"},{"term":"string"},{"term":"Array"},{"term":"Pattern"},{"term":"Contents"},{"term":"Pointers"},{"term":"functions"},{"term":"Dynamic memory allcation"},{"term":"recursion"},{"term":"C Turbo Compiler"},{"term":"File Handling"},{"term":"Structures"}],"title":{"type":"text","$t":"C Programming Tutorial"},"subtitle":{"type":"html","$t":"It is a blog about c programming. Here we provide c programs and tutorials to enhance your skills."},"link":[{"rel":"http://schemas.google.com/g/2005#feed","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/posts\/default"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/-\/searching+and+sorting?alt=json-in-script\u0026max-results=50"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/search\/label\/searching%20and%20sorting"},{"rel":"hub","href":"http://pubsubhubbub.appspot.com/"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"generator":{"version":"7.00","uri":"http://www.blogger.com","$t":"Blogger"},"openSearch$totalResults":{"$t":"8"},"openSearch$startIndex":{"$t":"1"},"openSearch$itemsPerPage":{"$t":"50"},"entry":[{"id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268.post-414329309170344542"},"published":{"$t":"2015-04-23T03:25:00.001-07:00"},"updated":{"$t":"2020-11-17T05:22:42.667-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"searching and sorting"}],"title":{"type":"text","$t":"Insertion Sort Algorithm, Time Complexity And Program In C"},"content":{"type":"html","$t":"\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/back%20to%20insertion%20sort\/#insertion sort\" name=\"insertion sort\"\u003EINSERTION SORT\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003C\/div\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003C\/div\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort in c\"\u003EInsertion Sort In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort algorithm\"\u003EAlgorithm for Insertion Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#Time Complexity\"\u003ETime Complexity Of Insertion Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort program in c\"\u003EInsertion Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Ch2\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ch2\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort in c\" name=\"insertion sort in c\"\u003EINSERTION SORT IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort\"\u003EBack to Insertion Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nIn \u003Cspan style=\"color: lime;\"\u003EInsertion Sort\u003C\/span\u003E we select a \u003Cspan style=\"color: lime;\"\u003Ekey\u003C\/span\u003E i.e an element one by one from any given list of element ( \u003Cspan style=\"color: lime;\"\u003Earray\u003C\/span\u003E ) and then we insert it in its appropriate position. We can either scan the list from\u003Cspan style=\"color: lime;\"\u003E left to right\u003C\/span\u003E or \u003Cspan style=\"color: lime;\"\u003Eright to left \u003C\/span\u003Eto find an appropriate position.\u0026nbsp;But usually we scan list from \u003Cspan style=\"color: lime;\"\u003Eright to left\u003C\/span\u003E because it is better in case of sorted and almost sorted arrays. Insertion sort is an efficient algorithm for sorting small number of elements. Though Insertion Sort is based on \u003Cspan style=\"color: lime;\"\u003Erecursive idea, \u003C\/span\u003Eit is more efficient to implement this algorithm by bottom up approach i.e\u003Cspan style=\"color: lime;\"\u003E iteratively\u003C\/span\u003E.\u0026nbsp;\u0026nbsp;\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\u003Cdiv style=\"text-align: justify;\"\u003ENeed Programming Help visit:\u0026nbsp;\u003Ca href=\"https:\/\/letstacle.com\"\u003EGet Programming Help Online\u003C\/a\u003E\u003C\/div\u003E\u003Cdiv style=\"text-align: justify;\"\u003E\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nConsider the elements to be sorted by insertion sort are :\u0026nbsp;\u003Cspan style=\"color: lime; text-align: left;\"\u003E89, 45, 68, 90, 29, 34, 17\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nAs shown in Figure below, starting with \u003Cspan style=\"color: lime;\"\u003EA[1]\u003C\/span\u003E and ending with \u003Cspan style=\"color: lime;\"\u003EA[n - 1]\u003C\/span\u003E, \u003Cspan style=\"color: lime;\"\u003EA[i]\u003C\/span\u003E is inserted in its appropriate place among the \u003Cspan style=\"color: lime;\"\u003Efirst i elements\u003C\/span\u003E of the array that have been already sorted (but, unlike selection sort, the elements are generally not in their final positions).\u0026nbsp;\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/4.bp.blogspot.com\/-vyMUb4D2iYM\/U89U7bpPZEI\/AAAAAAAAALM\/XDGoHzKCsvk\/s1600\/insertion+sort.png\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Insertion Sort In C : Showing insertion of elements\" border=\"0\" height=\"192\" src=\"http:\/\/4.bp.blogspot.com\/-vyMUb4D2iYM\/U89U7bpPZEI\/AAAAAAAAALM\/XDGoHzKCsvk\/s1600\/insertion+sort.png\" title=\"Insertion Sort Program In C\" width=\"320\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EInsertion Sort In C : Showing how elements are sorted\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\nThe above figure shows how elements \u003Cspan style=\"color: lime;\"\u003E89, 45, 68, 90, 29, 34, 17\u003C\/span\u003E \u0026nbsp;are sorted by insertion sort. A vertical bar separates the sorted part of the array from the remaining elements; the element being inserted is in bold.\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cspan style=\"color: lime;\"\u003ENote : Refer to algorithm for better understanding.\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cspan style=\"color: lime;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E \u003Cbr \/\u003E\n\u003Ch2\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort algorithm\" name=\"insertion sort algorithm\"\u003EINSERTION SORT ALGORITHM\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort\"\u003EBack to Insertion Sort\u003C\/a\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003EInsertionSort(int a[ ], int n)\u003C\/span\u003E\n\n  \u003Cspan style=\"color: blue;\"\u003E for i=1 to n-1\n       key = a[i]\n       j = i-1\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\n       while j\u0026gt;=0 and key \u0026lt; a[j]\n           a[j+1]=a[j]; \n           j=j-1;\n   \n       a[j+1] =  key\u003C\/span\u003E\n\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cspan style=\"color: lime;\"\u003ENote : The operation of the algorithm can be understood with the help of above figure.\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#Time Complexity\" name=\"Time Complexity\"\u003ETIME COMPLEXITY OF INSERTION SORT\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort\"\u003EBack to Insertion Sort\u003C\/a\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Ch3 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow;\"\u003ETime Complexity Of Insertion Sort - Best Case\u003C\/span\u003E\u003C\/h3\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli style=\"text-align: justify;\"\u003EThe best case input in an array is such that the array is already sorted.\u0026nbsp;\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003EIn this case insertion sort has linear running time i.e O(n)\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n\u003Ch3 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h3\u003E\n\u003Ch3 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow;\"\u003ETime Complexity Of Insertion Sort -\u003C\/span\u003E\u003Cspan style=\"color: yellow;\"\u003E\u0026nbsp;\u003C\/span\u003E\u003Cspan style=\"color: yellow;\"\u003EWorst Case\u003C\/span\u003E\u003C\/h3\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli style=\"text-align: justify;\"\u003EThe worst case input in an array is such that the array is sorted in reverse order.\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003EIn this case insertion sort has quadratic running time i.e O(n\u003Csup\u003E2\u003C\/sup\u003E)\u0026nbsp;\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n\u003Ch3 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h3\u003E\n\u003Ch3 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow;\"\u003ETime Complexity Of Insertion Sort -\u003C\/span\u003E\u003Cspan style=\"color: yellow;\"\u003E\u0026nbsp;\u003C\/span\u003E\u003Cspan style=\"color: yellow;\"\u003EAverage Case\u003C\/span\u003E\u003C\/h3\u003E\n\u003Cdiv\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli style=\"text-align: justify;\"\u003EInput in this case is a random input.\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003EIn this case also insertion sort has quadratic running time i.e O(n\u003Csup\u003E2\u003C\/sup\u003E)\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003EInsertion Sort is very efficient in sorting very small arrays.\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003EIts impractical to sort very large arrays using insertion sort due to its time complexity of\u0026nbsp;O(n\u003Csup\u003E2\u003C\/sup\u003E)\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort program in c\" name=\"insertion sort program in c\"\u003EINSERTION SORT PROGRAM IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#insertion sort\"\u003EBack to Insertion Sort\u003C\/a\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/ Insertion sort program in c\n\n#include\u0026lt;stdio.h\u0026gt; \n\nvoid InsertionSort(int a[],int n) ;\n\nint main() \n{ \n int a[20],i,n; \n printf(\"Enter number of elements in array : \"); \n scanf(\"%d\",\u0026amp;n);\n  \n \/\/ Inputting elements\n for(i=0;i\u0026lt;n;i++) \n { \n    printf(\"Enter number %d: \",i+1); \n    scanf(\"%d\",\u0026amp;a[i]);\n } \n \n \/\/ Displaying Elements before insertion sort\n printf(\"Items in the array are : \"); \n for(i=0;i\u0026lt;n;i++)\n { \n    printf(\"%d \",a[i]); \n } \n \n \/\/Applying insertion sort\n InsertionSort(a,n); \n \n \/\/ Displaying elements after insertion sort\n printf(\"\\nElements after insertion sort : \"); \n for(i=0;i\u0026lt;n;i++) \n { \n    printf(\"%d \",a[i]); \n } \n return 0; \n} \n\nvoid InsertionSort(int a[],int n) \n{ \n int i,key,j; \n \n for(i=1;i\u0026lt;n;i++) \n { \n  key=a[i]; \n  j=i-1;\u0026nbsp;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  \/\/ Finding appropriate position to insert key\n  while((key\u0026lt;a[j])\u0026amp;\u0026amp;(j\u0026gt;=0))  \n  { \n   a[j+1]=a[j]; \n   j=j-1; \n  }\n \u0026nbsp;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  \/\/ Inserting key\n  a[j+1]=key; \n } \n}\u003C\/span\u003E \n\n\n\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cspan style=\"color: yellow;\"\u003EMore Informative Posts :\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html\"\u003EInsertion Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/merge-sort-program-in-c.html\"\u003EMerge Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html\"\u003EQuick Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/counting-sort-program-in-c.html\"\u003ECounting Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html\"\u003EBubble Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html\"\u003EHeap Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003EBucket Sort Program In C\u003C\/li\u003E\n\u003Cli\u003EShell Sort Program In C\u003C\/li\u003E\n\u003Cli\u003ERadix Sort Program In C\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n"},"link":[{"rel":"replies","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/414329309170344542\/comments\/default","title":"Post Comments"},{"rel":"replies","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html#comment-form","title":"0 Comments"},{"rel":"edit","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/414329309170344542"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/414329309170344542"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html","title":"Insertion Sort Algorithm, Time Complexity And Program In C"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"media$thumbnail":{"xmlns$media":"http://search.yahoo.com/mrss/","url":"http:\/\/4.bp.blogspot.com\/-vyMUb4D2iYM\/U89U7bpPZEI\/AAAAAAAAALM\/XDGoHzKCsvk\/s72-c\/insertion+sort.png","height":"72","width":"72"},"thr$total":{"$t":"0"}},{"id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268.post-79527827849284415"},"published":{"$t":"2015-01-01T13:23:00.002-08:00"},"updated":{"$t":"2020-11-17T05:08:22.252-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"searching and sorting"}],"title":{"type":"text","$t":"Heap Sort Program In C"},"content":{"type":"html","$t":"\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort\" name=\"Heap Sort\"\u003EHEAP SORT\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort In C\"\u003EHeap Sort In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Pseudocode To Add Node\"\u003EPseudocode to Add Node In Heap\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Pseudocode To Remove Root\"\u003EPseudocode to Remove Root From Heap\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort Performed\"\u003EHow Heap Sort Is Performed\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort Program In C\"\u003EHeap Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort Program With Output\"\u003EHeap Sort Program Output\u003C\/a\u003E\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Cdiv\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort In C\" name=\"Heap Sort In C\"\u003EHEAP SORT IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort\"\u003EBack To Heap Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\nHeap sort uses a binary heap, which is a complete binary tree. \u0026nbsp;\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cspan style=\"color: lime;\"\u003EBinary Tree :\u003C\/span\u003E\u0026nbsp;A Binary Tree is a hierarchical structure \u0026nbsp;that is either empty or consists of an element, called the root, and two distinct binary trees, called the left subtree and right subtree.\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\u003Cbr \/\u003E\u003C\/div\u003E\u003Cdiv\u003ENeed HTML Homework Help:\u0026nbsp;\u003Ca href=\"https:\/\/letstacle.com\/html-homework-assignment-help-css-javascript\"\u003EGet Best HTML CSS JavaScript Homework Help\u003C\/a\u003E\u003Cbr \/\u003E\u003C\/div\u003E\u003Cdiv class=\"g\" style=\"background-color: white; clear: both; color: #202124; font-family: arial, sans-serif; font-size: 14px; line-height: 1.2; margin: 0px; padding-bottom: 16px; padding-left: 16px; padding-right: 16px; width: 600px;\"\u003E\u003Cdiv class=\"rc\" data-hveid=\"CAEQAA\" data-ved=\"2ahUKEwj7ov_w0IntAhXJ7HMBHQs9B-QQFSgAMAF6BAgBEAA\" style=\"clear: both; padding-bottom: 0px; position: relative;\"\u003E\u003C\/div\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\u0026nbsp;Example :\u0026nbsp;\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"float: left; margin-right: 1em; text-align: left;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/2.bp.blogspot.com\/-a8hXEF_Z4tQ\/VKWPiN2VjZI\/AAAAAAAAANY\/5-0iFuIFc4o\/s1600\/binary_tree.png\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Heap Sort : Binary Tree\" border=\"0\" height=\"182\" src=\"http:\/\/2.bp.blogspot.com\/-a8hXEF_Z4tQ\/VKWPiN2VjZI\/AAAAAAAAANY\/5-0iFuIFc4o\/s1600\/binary_tree.png\" title=\"Heap Sort Program In C\" width=\"200\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EHeap Sort : Binary Tree\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\nHeap is a binary tree with the following properties :\u0026nbsp;\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli\u003EIt is a complete binary tree.\u003C\/li\u003E\n\u003Cli\u003E\u0026nbsp;Each node is greater than or equal to any of its children.\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cspan style=\"color: lime;\"\u003EComplete Binary Tree :\u003C\/span\u003E\u0026nbsp;A binary tree is complete if each of its levels is full, except that the last level may not be full and all the leaves on the last level are placed leftmost.\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nExample :\u0026nbsp;\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Ctable cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"float: left; margin-right: 1em; text-align: left;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/3.bp.blogspot.com\/-JcCc4yt4R9s\/VKWTYvmpIwI\/AAAAAAAAANk\/92g56U31U-o\/s1600\/complete_binary_tree.png\" style=\"clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Heap Sort : Complete Binary Tree\" border=\"0\" height=\"132\" src=\"http:\/\/3.bp.blogspot.com\/-JcCc4yt4R9s\/VKWTYvmpIwI\/AAAAAAAAANk\/92g56U31U-o\/s1600\/complete_binary_tree.png\" title=\"Heap Sort Program In C\" width=\"200\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EHeap Sort : Complete Binary Tree\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\nHeap Example :\u0026nbsp;\u003C\/div\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Ctable cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"float: left; margin-right: 1em; text-align: left;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/2.bp.blogspot.com\/-ZI24XB_mzWU\/VKWUy32tMQI\/AAAAAAAAANs\/5awI8uAIJKQ\/s1600\/heap.png\" style=\"clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Heap Sort : Heap\" border=\"0\" height=\"114\" src=\"http:\/\/2.bp.blogspot.com\/-ZI24XB_mzWU\/VKWUy32tMQI\/AAAAAAAAANs\/5awI8uAIJKQ\/s1600\/heap.png\" title=\"Heap Sort Program In C\" width=\"200\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EHeap Sort : Heap\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cspan style=\"color: lime; font-weight: normal;\"\u003ENote :\u0026nbsp;\u003C\/span\u003EWe represent heaps in level order, going from left to right. The array corresponding to the heap above is \u0026nbsp;:\u0026nbsp;\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cspan style=\"color: lime;\"\u003E[45, 24, 32, 16,19,12, 21].\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cspan style=\"color: lime;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Ch2 style=\"text-align: justify;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Pseudocode To Add Node\" name=\"Pseudocode To Add Node\"\u003EPSEUDOCODE TO ADD NODE IN HEAP\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort\"\u003EBack To Heap Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cdiv\u003E\nTo add a new node to the heap, first add it to the end of the heap and then rebuild the tree as follows:\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003ELet the last node be the current node;\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003Ewhile (the current node is greater than its parent) {\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003ESwap the current node with its parent;\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003ENow the current node is one level up;\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003E}\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\nSuppose we want to insert \u003Cspan style=\"color: lime;\"\u003E3, 5, 1, 19, 11, 22. \u003C\/span\u003EWe assume that the heap is initially empty.\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003C\/div\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003C\/div\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003C\/div\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/4.bp.blogspot.com\/-ZM736jicFgE\/VKWrwjagM3I\/AAAAAAAAAOY\/Ik-p7Hsd7qU\/s1600\/add_node.png\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Heap Sort : Adding Node In Heap\" border=\"0\" height=\"236\" src=\"http:\/\/4.bp.blogspot.com\/-ZM736jicFgE\/VKWrwjagM3I\/AAAAAAAAAOY\/Ik-p7Hsd7qU\/s1600\/add_node.png\" title=\"Heap Sort Program In C\" width=\"400\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EHeap Sort : Adding Node In Heap\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Ch2\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003ENow lets insert a new node \u003Cspan style=\"color: lime;\"\u003E88\u003C\/span\u003E in the above heap.\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003C\/div\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003C\/div\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/2.bp.blogspot.com\/-Gd8XNUt3y0I\/VKWw6_VTx6I\/AAAAAAAAAPA\/kHdjKjvlzO8\/s1600\/new_node.png\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Heap Sort : Rebuilding of Heap after adding a new node\" border=\"0\" height=\"168\" src=\"http:\/\/2.bp.blogspot.com\/-Gd8XNUt3y0I\/VKWw6_VTx6I\/AAAAAAAAAPA\/kHdjKjvlzO8\/s1600\/new_node.png\" title=\"Heap Sort Program In C\" width=\"640\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EHeap Sort : Rebuilding of Heap after adding a new node\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Ch2\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Pseudocode To Remove Root\" name=\"Pseudocode To Remove Root\"\u003EPSEUDOCODE TO REMOVE ROOT FROM HEAP\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort\" style=\"text-align: left;\"\u003EBack To Heap Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nOften you need to remove the max element, which is the root in a heap. After the root is removed, the tree must be rebuilt to maintain the heap property. The algorithm for rebuilding the tree can be described as follows:\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003EMove the last node to replace the root;\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003ELet the root be the current node;\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003Ewhile (the current node has children and the current node is\u0026nbsp;\u003C\/span\u003E\u003Cspan style=\"color: lime;\"\u003Esmaller than one of its children) {\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003ESwap the current node with the larger of its children;\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003ENow the current node is one level down;\u003C\/span\u003E\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"color: lime;\"\u003E}\u003C\/span\u003E\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003C\/div\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/2.bp.blogspot.com\/-ob98SM_bMjc\/VKWzcoFCyZI\/AAAAAAAAAPU\/IL8mD0Uwpr0\/s1600\/remove.png\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Heap Sort : Removing Root and Rebuilding Heap\" border=\"0\" height=\"170\" src=\"http:\/\/2.bp.blogspot.com\/-ob98SM_bMjc\/VKWzcoFCyZI\/AAAAAAAAAPU\/IL8mD0Uwpr0\/s1600\/remove.png\" title=\"Heap Sort Program In C\" width=\"640\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"font-size: 13px;\"\u003E\u003Cspan style=\"color: lime;\"\u003EHeap Sort : Removing Root and Rebuilding Heap\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort Performed\" name=\"Heap Sort Performed\"\u003EHOW HEAP SORT IS PERFORMED\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort\"\u003EBack To Heap Sort\u003C\/a\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli style=\"text-align: justify;\"\u003EFirst we take input in an array.\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003EThen we insert these element in heap.\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003EAs we know that root of the heap is maximum element so we remove root and rebuild heap so that the next maximum element is at root. Rebuilding ensures that our tree is in the form of heap.\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003EWe store the root ( maximum element ) in decreasing order of array length. We could have used another array as well to store the root.\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cbr \/\u003E\n\u003C\/h2\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort Program In C\" name=\"Heap Sort Program In C\"\u003EHEAP SORT PROGRAM IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort\"\u003EBack To Heap Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/ C Program ( Code ) for Heap sort\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E#include\u0026lt;stdio.h\u0026gt;\n\nvoid insert(int a[], int n, int item);\nint deleteheap(int a[],int n);\n\nint main()\n{\n   int a[20],i,n,item;\n   printf(\" Enter number of elements in array : \");\n   scanf(\"%d\",\u0026amp;n);\n   for(i=0;i\u0026lt;n;i++)\n   {\n     printf(\" Enter number %d : \",i+1);\n     scanf(\"%d\",\u0026amp;a[i]);  \n   }\n \n   for(i=0;i\u0026lt;n;i++)\n   {\n\n     item=a[i];\n     insert(a,i,item);\n   }\n   printf(\"\\n Heap is : \");\n   for(i=0;i\u0026lt;n;i++)\n   {\n     printf(\"%d \",a[i]);\n   }\n\n\n   for(i=n;i\u0026gt;=1;i--)\n   { \n     item=deleteheap(a,i);\n         \n     \/\/ Stores item=Maximum element in decreasing order of array length\n     a[i-1]=item;\n   }\n\n\n   printf(\"\\n SORTED LIST IS!!!!\\n\");\n   for(i=0;i\u0026lt;n;i++)\n   {\n     printf(\" %d \",a[i]);\n   }\n \n }\n \n  \/\/ Used to Build Heap\n  void insert(int a[], int n, int item)\n  {\n     int ptr,par,temp;\n \n     ptr=n;\n     while(ptr\u0026gt;=1)\n     { \n       par=(ptr-1)\/2;\n \n       if(a[par]\u0026gt;=item)\n       { \n         a[ptr]=item;\n         return;\n       }\n       else\n       {\n         a[ptr]=a[par];\n         ptr=par;\n       }\n    \n       a[ptr]=item;\n     }\n }\n \n  \/* Remove root which is the maximum element in Heap and rebuild heap \n     so that the next maximum element is at root. Rebuilding ensures \n     that our tree is in the form of heap.\n     Returns item = a[0] wcich contains the root of the heap.\n   *\/\n  int deleteheap(int a[],int n)\n  {\n    int i=0,item,temp;\n    \n    \/\/ a[0] - contains the root of the heap\n    item=a[0];\n    a[0]=a[n-1];\n    n=n-1;\n    while(((a[i]\u0026lt;a[2*i+1])||(a[i]\u0026lt;a[2*i+2]))\u0026amp;\u0026amp;((2*i+1)\u0026lt;n))\n    {\n      if(a[2*i+1]\u0026gt;a[2*i+2])\n      {\n        temp=a[i];\n        a[i]=a[2*i+1];\n        a[2*i+1]=temp;\n        i=2*i+1;\n      }\n \n      else\n      {\n        temp=a[i];\n        a[i]=a[2*i+2];\n        a[2*i+2]=temp;\n        i=2*i+2;\n      }\n    }\n    \n    \/\/ Root of the heap is returned\n    return item;\n  }\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort Program With Output\" name=\"Heap Sort Program With Output\"\u003EHEAP SORT PROGRAM OUTPUT\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#Heap Sort\"\u003EBack To Heap Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"float: left; margin-right: 1em; text-align: left;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/1.bp.blogspot.com\/-c39rseIPm00\/VKW2MwXBKtI\/AAAAAAAAAPw\/_X9P_8ZQZgQ\/s1600\/heap_output.png\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Heap Sort : Heap sort code output\" border=\"0\" height=\"148\" src=\"http:\/\/1.bp.blogspot.com\/-c39rseIPm00\/VKW2MwXBKtI\/AAAAAAAAAPw\/_X9P_8ZQZgQ\/s1600\/heap_output.png\" title=\"Heap Sort Program In C With Output\" width=\"400\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EHeap Sort Output\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cspan style=\"color: yellow;\"\u003EMore Informative Posts :\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html\"\u003ECounting Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html\"\u003EQuick Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/merge-sort-program-in-c.html\"\u003EMerge Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html\"\u003EBubble Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html\"\u003ESelection Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html\"\u003EInsertion Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003EShell sort Program In C\u003C\/li\u003E\n\u003Cli\u003ERadix Sort Program In C\u003C\/li\u003E\n\u003Cli\u003EBucket Sort Program In C\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n"},"link":[{"rel":"replies","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/79527827849284415\/comments\/default","title":"Post Comments"},{"rel":"replies","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html#comment-form","title":"0 Comments"},{"rel":"edit","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/79527827849284415"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/79527827849284415"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html","title":"Heap Sort Program In C"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"media$thumbnail":{"xmlns$media":"http://search.yahoo.com/mrss/","url":"http:\/\/2.bp.blogspot.com\/-a8hXEF_Z4tQ\/VKWPiN2VjZI\/AAAAAAAAANY\/5-0iFuIFc4o\/s72-c\/binary_tree.png","height":"72","width":"72"},"thr$total":{"$t":"0"}},{"id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268.post-888623995431464502"},"published":{"$t":"2014-08-04T08:39:00.001-07:00"},"updated":{"$t":"2018-05-26T14:07:49.753-07:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"searching and sorting"}],"title":{"type":"text","$t":"Counting Sort Program In C"},"content":{"type":"html","$t":"\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort\" name=\"Counting Sort\"\u003ECOUNTING SORT\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort%20In%20C\"\u003ECounting Sort In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort%20Algorithm\"\u003EAlgorithm for Counting Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort%20Program%20In%20C\"\u003ECounting Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow; font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort%20In%20C\" name=\"Counting Sort In C\"\u003ECOUNTING SORT IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort\"\u003EBack To Counting Sort\u003C\/a\u003E\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nIn the code for counting sort, we assume that the input is an array A[1 . . . n] and \u0026nbsp;we require two other arrays: the array B[1 . . . n] holds the sorted output, and the array C[0 . . . k] provides temporary working storage. Here\u003Cspan style=\"color: blur;\"\u003E \u003C\/span\u003E\u003Cspan style=\"color: blue;\"\u003Ek = maximum element\u003C\/span\u003E\u003Cspan style=\"color: blur;\"\u003E \u003C\/span\u003Epresent in array.\u003C\/div\u003E\n\u003Cbr \/\u003E\nConsider following elements to be sorted using counting sort :\u003Cspan style=\"color: blue;\"\u003E\u0026nbsp;\u003C\/span\u003E\u003Cspan style=\"color: blue;\"\u003E2, 5, 3, 0, 2, 3, 0, 3\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\nSo we have in array A[1 . . . 8 ] :\u003Cbr \/\u003E\n\u003Ctable border=\"1\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd\u003E\u0026nbsp;2\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;5\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;3\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;2\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;3\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;3\u0026nbsp;\u003C\/td\u003E \u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cbr \/\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nNow what we have to do is initialize the auxiliary array \u003Cspan style=\"color: blue;\"\u003EC[0 . . . k]\u003C\/span\u003E with \u003Cspan style=\"color: blue;\"\u003E0.\u003C\/span\u003E Here \u003Cspan style=\"color: blue;\"\u003Ek = 5.\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nSo C[0 . . . 5] becomes :\u003C\/div\u003E\n\u003Ctable border=\"1\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cbr \/\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nNext step is to count the frequency of each element and store it in their respective index position i.e here \u003Cspan style=\"color: blue;\"\u003Efrequency of 0 = 2.\u003C\/span\u003E So we place \u003Cspan style=\"color: blue;\"\u003E'2'\u003C\/span\u003E at index position \u003Cspan style=\"color: blue;\"\u003E'0'.\u003C\/span\u003E\u003Cspan style=\"color: blue;\"\u003E \u003C\/span\u003ESimilarly we place each element and the array becomes C[0 . . . 5] :\u003C\/div\u003E\n\u003Ctable border=\"1\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd\u003E\u0026nbsp;2\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;2\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;3\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;1\u0026nbsp;\u003C\/td\u003E \u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nNow we add the \u003Cspan style=\"color: blue;\"\u003Ecurrent index position\u003C\/span\u003E with its \u003Cspan style=\"color: blue;\"\u003Eprevious index position\u003C\/span\u003E and store it in the \u003Cspan style=\"color: blue;\"\u003Ecurrent index position\u003C\/span\u003E i.e \u003Cspan style=\"color: blue;\"\u003E\u003Cspan style=\"color: blue;\"\u003EC[ i ] = C[ i ] +\u0026nbsp;C[ i -\u0026nbsp;1 ]\u003C\/span\u003E\u0026nbsp;\u003C\/span\u003Ewhere \u003Cspan style=\"color: blue;\"\u003E'i'\u003C\/span\u003E starts from \u003Cspan style=\"color: blue;\"\u003E'\u003C\/span\u003E\u003Cspan style=\"color: blue;\"\u003E1'.\u003C\/span\u003E\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\nSo C[ 0 . . . 5 ] becomes :\u0026nbsp;\u003C\/div\u003E\n\u003Ctable border=\"1\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd\u003E\u0026nbsp;2\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;2\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;4\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;7\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;7\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;8\u0026nbsp;\u003C\/td\u003E \u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cbr \/\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nThe final step is to place the elements in \u003Cspan style=\"color: blue;\"\u003EB[ 1 . . . 8 ]\u003C\/span\u003E with reference to\u003Cspan style=\"color: blue;\"\u003E \u003Cspan style=\"color: blue;\"\u003E\u003Cspan style=\"color: blue;\"\u003EC[ 0 . . . 5 ]\u003C\/span\u003E \u003C\/span\u003E\u003C\/span\u003Ei.e \u0026nbsp;Now we treat elements in\u0026nbsp;\u003Cspan style=\"color: blue;\"\u003EC[ 0 . . . 5 ]\u003C\/span\u003E as index of\u0026nbsp;\u003Cspan style=\"color: blue;\"\u003EB[ 1 . . . 8 ]\u003C\/span\u003E and index of\u0026nbsp;\u003Cspan style=\"color: blue;\"\u003EC[ 0 . . . 5 ]\u003C\/span\u003E as elements of\u0026nbsp;\u003Cspan style=\"color: blue;\"\u003E\u003Cspan style=\"color: blue;\"\u003EB[ 1 . . . 8 ].\u003C\/span\u003E \u003C\/span\u003ESo at index position \u003Cspan style=\"color: blue;\"\u003E'8'\u003C\/span\u003E we have element\u003Cspan style=\"color: blue;\"\u003E \u003Cspan style=\"color: blue;\"\u003E'5'\u003C\/span\u003E\u003C\/span\u003E so we place \u003Cspan style=\"color: blue;\"\u003E'5'\u003C\/span\u003E at index position of \u003Cspan style=\"color: blue;\"\u003E\u003Cspan style=\"color: blue;\"\u003E'8'\u003C\/span\u003E of\u0026nbsp;\u003Cspan style=\"color: blue;\"\u003EB[ 1 . . . 8 ]\u003C\/span\u003E\u003C\/span\u003E\u0026nbsp;( B[ 8 ] = 5 ) and we reduce the index position by \u003Cspan style=\"color: blue;\"\u003E\u003Cspan style=\"color: blue;\"\u003E'1'\u003C\/span\u003E i.e \u003Cspan style=\"color: blue;\"\u003E8-1 = 7\u003C\/span\u003E\u003C\/span\u003E. Now note that we have element\u003Cspan style=\"color: blue;\"\u003E \u003Cspan style=\"color: blue;\"\u003E'7'\u003C\/span\u003E\u003C\/span\u003E\u003Cspan style=\"color: blue;\"\u003E\u0026nbsp;\u003C\/span\u003E in \u003Cspan style=\"color: blue;\"\u003E\u003Cspan style=\"color: blue;\"\u003EC[ 4 ]\u003C\/span\u003E \u003C\/span\u003Eposition but \u003Cspan style=\"color: blue;\"\u003E'4'\u003C\/span\u003E is not present in the original array so we skip it and move to \u003Cspan style=\"color: blue;\"\u003EC[ 3 ]\u003C\/span\u003E position, so we place \u003Cspan style=\"color: blue;\"\u003E'3'\u003C\/span\u003E\u003Cspan style=\"color: blue;\"\u003E \u003C\/span\u003Eat index position \u003Cspan style=\"color: blue;\"\u003E'7'\u003C\/span\u003E of\u003Cspan style=\"color: blue;\"\u003E \u003Cspan style=\"color: blue;\"\u003EB[ 1 . . . 8 ].\u003C\/span\u003E\u003C\/span\u003E Similarly we place each element in \u003Cspan style=\"color: blue;\"\u003E\u003Cspan style=\"color: blue;\"\u003EB[ 1 . . . 8 ]\u003C\/span\u003E \u003C\/span\u003Eand we get sorted array.\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\nSo the sorted array\u0026nbsp;B[ 1 . . . 8 ] \u0026nbsp;is :\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Ctable border=\"1\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;0\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;2\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;2\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;3\u0026nbsp;\u003C\/td\u003E \u003Ctd\u003E\u0026nbsp;3\u0026nbsp;\u003C\/td\u003E\u003Ctd\u003E\u0026nbsp;3\u0026nbsp;\u003C\/td\u003E\u003Ctd\u003E\u0026nbsp;5\u0026nbsp;\u003C\/td\u003E \u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort%20Algorithm\" name=\"Counting Sort Algorithm\"\u003ECOUNTING SORT ALGORITHM\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort\"\u003EBack To Counting Sort\u003C\/a\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/ Counting Sort algorithm\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003ECountingSort(A,B,n,k)\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E   int C[0 . . . k ]\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  \u0026nbsp;for i=0 to k\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E      C[i]=0\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E   for j=1 to n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E      C[A[j]] = C[A[j]] + 1;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E   for i=1 to k\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E      C[i] = C[i] + C[i-1];\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E   for j=n downto 1\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E      B[C[A[j]]] = A[j];\n      C[a[j]] = C[A[j]] - 1;\u003C\/span\u003E\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u0026nbsp; \u003Cbr \/\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort%20Program%20In%20C\" name=\"Counting Sort Program In C\"\u003ECOUNTING SORT PROGRAM IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#Counting%20Sort\"\u003EBack To Counting Sort\u003C\/a\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/ Counting sort program in c\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\n#include\u0026lt;stdio.h\u0026gt; \n\nvoid CountingSort(int a[], int sorted_array[], int max_element, int n);\n\nint main() \n{ \n int a[20],i,n; \n int max_element, sorted_array[20];\n \n printf(\"Enter number of elements in array : \"); \n scanf(\"%d\",\u0026amp;n);\n  \n \/\/ Inputting elements\n for(i=1;i\u0026lt;=n;i++) \n { \n    printf(\"Enter number %d: \",i+1); \n    scanf(\"%d\",\u0026amp;a[i]);\n } \n \n \/\/ Displaying Elements before counting sort\n printf(\"Items in the array are : \"); \n for(i=1;i\u0026lt;=n;i++)\n { \n    printf(\"%d \",a[i]); \n } \n \n \/\/ Finding Maximum element\n max_element=a[1];\n \n for(i=2;i\u0026lt;=n;i++)\n {\n  if(a[i] \u0026gt; max_element)\n  {\n           max_element = a[i];\n  }\n }\n \n \/\/Applying counting sort\n CountingSort(a, sorted_array, max_element, n); \n \n \/\/ Displaying elements after count sort\n printf(\"\\nElements after count sort : \"); \n for(i=1;i\u0026lt;=n;i++) \n { \n    printf(\"%d \",sorted_array[i]); \n } \n    \n return 0; \n} \n\nvoid CountingSort(int a[],int sorted_array[],int max_element, int n)\n{\n int aux_array[max_element];\n int i,j;\n \n \/\/ Initializing auxiliary array\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E        for(i=0;i\u0026lt;=max_element;i++)\n {\n  aux_array[i]=0;\n }\n \u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E        \/\/ Placing Frequency of each element in aux_array\n for(j=1;j\u0026lt;=n;j++)\n {\n  aux_array[a[j]]=aux_array[a[j]]+1;\n }\n \u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E        \/\/ Adding elements of current and previous index position\n for(i=1;i\u0026lt;=max_element;i++)\n {\n  aux_array[i]=aux_array[i]+aux_array[i-1];\n }\n \u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E        \/\/ Placing elements in sorted_array \n for(j=n;j\u0026gt;=1;j--)\n {\n  sorted_array[aux_array[a[j]]] = a[j];\n  aux_array[a[j]] = aux_array[a[j]] - 1;\n }\n}\u003C\/span\u003E\n\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cspan style=\"color: #4c1130;\"\u003E\u0026nbsp;More Informative Posts :\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html\"\u003EInsertion Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html\"\u003ESelection Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html\"\u003EQuick Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/counting-sort-program-in-c.html\"\u003ECounting Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html\"\u003EBubble Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html\"\u003EHeap Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003EBucket Sort Program In C\u003C\/li\u003E\n\u003Cli\u003EShell Sort Program In C\u003C\/li\u003E\n\u003Cli\u003ERadix Sort Program In C\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n"},"link":[{"rel":"replies","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/888623995431464502\/comments\/default","title":"Post Comments"},{"rel":"replies","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html#comment-form","title":"3 Comments"},{"rel":"edit","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/888623995431464502"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/888623995431464502"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html","title":"Counting Sort Program In C"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"thr$total":{"$t":"3"}},{"id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268.post-1508337220602865553"},"published":{"$t":"2014-07-26T22:34:00.000-07:00"},"updated":{"$t":"2015-03-01T04:15:33.696-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"searching and sorting"}],"title":{"type":"text","$t":"Selection Sort Program In C"},"content":{"type":"html","$t":"\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html#Selection Sort\" name=\"Selection Sort\"\u003ESelection Sort\u003C\/a\u003E\u003Cbr \/\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html#Selection Sort In C\"\u003ESelection Sort In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html#Selection Sort Algorithm\"\u003EAlgorithm For Selection Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html#Selection Sort Program In C\"\u003ESelection Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Ch2\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ch2\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html#Selection Sort In C\" name=\"Selection Sort In C\"\u003ESELECTION SORT IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\nWe start \u003Cspan style=\"color: lime;\"\u003ESelection Sort\u003C\/span\u003E by scanning the entire given list to find its smallest element and exchange it with the first element, putting the smallest element in its final position in the sorted list. Then we scan the list, starting with the second element, to find the smallest among the \u003Cspan style=\"color: lime;\"\u003Elast n - 1\u003C\/span\u003E elements and exchange it with the second element, putting the second smallest element in its final position. Generally, on the \u003Cspan style=\"color: lime;\"\u003Eith pass\u003C\/span\u003E through the list, which we number from \u003Cspan style=\"color: lime;\"\u003E0 to n - 2,\u003C\/span\u003E the algorithm searches for the smallest item among the last \u003Cspan style=\"color: lime;\"\u003En - i\u003C\/span\u003E elements and swaps it with \u003Cspan style=\"color: lime;\"\u003EA[i].\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cspan style=\"color: lime;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003Cbr \/\u003E\nConsider the following element that is to be sorted using selection sort :\u0026nbsp;\u0026nbsp;\u003Cspan style=\"color: lime;\"\u003E89, 45, 68, 90, 29, 34, 17.\u003C\/span\u003E\u003Cbr \/\u003E\nThe analysis of selection sort is straightforward. The input's size is given by the \u003Cspan style=\"color: lime;\"\u003Enumber of elements 'n'\u003C\/span\u003E and the algorithm's basic operation is the key comparison \u003Cspan style=\"color: lime;\"\u003EA[j] \u0026lt; A[min].\u003C\/span\u003E The number of times it is executed depends only on the array's size.\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/2.bp.blogspot.com\/-NphjInjCYGY\/U84dJsUVV6I\/AAAAAAAAAK8\/KpdOKU5vuUQ\/s1600\/Selection+Sort.png\" imageanchor=\"1\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Selection Sort In C : Showing how elements are sorted\" border=\"0\" src=\"http:\/\/2.bp.blogspot.com\/-NphjInjCYGY\/U84dJsUVV6I\/AAAAAAAAAK8\/KpdOKU5vuUQ\/s1600\/Selection+Sort.png\" height=\"252\" title=\"Selection Sort Program In C\" width=\"400\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003ESelection Sort In C : Showing how elements are sorted\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cbr \/\u003E\nThe above figure shows how given elements\u0026nbsp;\u003Cspan style=\"color: lime;\"\u003E89, 45, 68, 90, 29, 34, 17\u003C\/span\u003E\u0026nbsp;are sorted according to selection sort. Each line corresponds to one iteration of the algorithm i.e. a pass through the list tail to the right of the vertical bar. An element in bold indicates the smallest element found. Elements to the left of the vertical bar are in their final positions and are not considered in this and subsequent iterations.\u0026nbsp;\u003C\/div\u003E\n\u003Ch2 style=\"text-align: justify;\"\u003E\n\u003Cspan style=\"color: yellow; font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html#Selection Sort Algorithm\" name=\"Selection Sort Algorithm\"\u003ESELECTION SORT ALGORITHM\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003ESelectionSort(int a[],int n)\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E   for i=0 to n-2\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E     min=i\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E     for j=i+1 to n-1\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E        if a[min] \u0026gt; a[j]\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E           min = j\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  \u0026nbsp;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E     swap a[i] with a[min]\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cspan style=\"color: blue;\"\u003E\u0026nbsp; \u0026nbsp;\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html#Selection Sort Program In C\" name=\"Selection Sort Program In C\"\u003ESELECTION SORT PROGRAM IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/ Selection sort program in c\n\n#include\u0026lt;stdio.h\u0026gt; \n\nvoid SelectionSort(int [],int); \n \n\nint main() \n{ \n int a[20],i,n; \n printf(\"Enter number of elements in array : \"); \n scanf(\"%d\",\u0026amp;n);\n  \n \/\/ Inputting elements\n for(i=0;i\u0026lt;n;i++) \n { \n    printf(\"Enter number %d: \",i+1); \n    scanf(\"%d\",\u0026amp;a[i]);\n } \n \n \/\/ Displaying Elements before selection sort\n printf(\"Items in the array are : \"); \n for(i=0;i\u0026lt;n;i++)\n { \n    printf(\"%d \",a[i]); \n } \n \n \/\/Applying selection sort\n SelectionSort(a,n); \n \n \/\/ Displaying elements after selection sort\n printf(\"\\nElements after selection sort : \"); \n for(i=0;i\u0026lt;n;i++) \n { \n printf(\"%d \",a[i]); \n } \n return 0; \n} \n\nvoid SelectionSort(int a[],int n) \n{ \n int i,loc,j,min,temp; \n for(i=0;i\u0026lt;=n-2;i++) \n { \n   min = i;\n \n   for(j=i+1;j\u0026lt;=n-1;j++) \n   {   \n     \/\/ Finding minimum element\n     if(a[min] \u0026gt;a[j])  \n     { \n       min=j;  \n     } \n   }\n  \n   \/\/Swapping a[i] with a[min]\n   temp=a[i]; \n   a[i]=a[min]; \n   a[min]=temp;\n } \n}\u003C\/span\u003E\n\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cspan style=\"color: yellow;\"\u003EMore Informative Posts :\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html\"\u003EInsertion Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/merge-sort-program-in-c.html\"\u003EMerge Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html\"\u003EQuick Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/counting-sort-program-in-c.html\"\u003ECounting Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html\"\u003EBubble Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html\"\u003EHeap Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003EBucket Sort Program In C\u003C\/li\u003E\n\u003Cli\u003EShell Sort Program In C\u003C\/li\u003E\n\u003Cli\u003ERadix Sort Program In C\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n"},"link":[{"rel":"replies","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/1508337220602865553\/comments\/default","title":"Post Comments"},{"rel":"replies","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html#comment-form","title":"0 Comments"},{"rel":"edit","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/1508337220602865553"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/1508337220602865553"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html","title":"Selection Sort Program In C"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"media$thumbnail":{"xmlns$media":"http://search.yahoo.com/mrss/","url":"http:\/\/2.bp.blogspot.com\/-NphjInjCYGY\/U84dJsUVV6I\/AAAAAAAAAK8\/KpdOKU5vuUQ\/s72-c\/Selection+Sort.png","height":"72","width":"72"},"thr$total":{"$t":"0"}},{"id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268.post-5301024430722820563"},"published":{"$t":"2014-07-23T01:35:00.000-07:00"},"updated":{"$t":"2015-03-01T04:19:14.017-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"searching and sorting"}],"title":{"type":"text","$t":"Bubble Sort Program In C"},"content":{"type":"html","$t":"\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Ch2\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort\" name=\"Bubble Sort\" style=\"font-weight: normal;\"\u003EBubble Sort\u003C\/a\u003E\u003C\/h2\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort In C\"\u003EBubble Sort In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort Algorithm\"\u003EAlgorithm for Bubble Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort Program In C\"\u003EBubble Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Cbr \/\u003E\n\u003Ch2\u003E\n\u003Cspan style=\"color: yellow; font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort In C\" name=\"Bubble Sort In C\"\u003EBUBBLE SORT IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cspan style=\"color: lime;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort\"\u003EBack To Bubble Sort\u003C\/a\u003E\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cspan style=\"color: lime;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E \u003Cspan style=\"color: lime;\"\u003EBubble Sort\u003C\/span\u003E is a popular but inefficient sorting algorithm. \u0026nbsp;Bubble Sort is another brute-force application to the sorting problem that compares adjacent elements of the list and exchange them if they are out of order. By doing it repeatedly, we end up \"bubbling up\" the largest element to the last position on the list. The next pass bubbles up the second largest element, and so on until, after \u003Cspan style=\"color: lime;\"\u003En - 1\u003C\/span\u003E passes, the list is sorted. Pass \u003Cspan style=\"color: lime;\"\u003Ei \u003C\/span\u003E(\u003Cspan style=\"color: lime;\"\u003E0 \u0026lt;= i \u0026lt;= n - 2\u003C\/span\u003E) of bubble sort can be represented by the following diagram:\u0026nbsp;\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nConsider element to be sorted are :\u0026nbsp;\u003Cspan style=\"color: lime;\"\u003E89, 45, 68, 90, 29, 34, 17\u003C\/span\u003E\u0026nbsp;\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/4.bp.blogspot.com\/-vRBUD0Sa1y4\/U84K16FwyPI\/AAAAAAAAAKs\/t9NjWBWOKy4\/s1600\/bubblesort.png\" imageanchor=\"1\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Bubble Sort In C : Swapping elements\" border=\"0\" src=\"http:\/\/4.bp.blogspot.com\/-vRBUD0Sa1y4\/U84K16FwyPI\/AAAAAAAAAKs\/t9NjWBWOKy4\/s1600\/bubblesort.png\" title=\"Bubble Sort Program In C\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EQuick Sort In C : Showing how elements are sorted\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\nFirst \u003Cspan style=\"color: lime;\"\u003Etwo passes\u003C\/span\u003E of bubble sort on the given list \u003Cspan style=\"color: lime;\"\u003E89, 45, 68, 90, 29, 34, 17 \u003C\/span\u003Eis shown in above figure. \u0026nbsp;A new line is shown after a swap of two elements is done. The elements to the right of the vertical bar are in their final positions and are not considered in \u0026nbsp;subsequent iterations of the algorithm.\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort Algorithm\" name=\"Bubble Sort Algorithm\"\u003EBUBBLE SORT ALGORITHM\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort\" style=\"text-align: justify;\"\u003EBack To Bubble Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/ Algorithm for Bubble Sort\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003EBubbleSort(int a[],int n)\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  for i=0 to n-2\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E    for j=0 to n-2-i\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E      if a[j] \u0026gt; a[j+1]\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E        swap a[j] with a[j+1]\u003C\/span\u003E\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort Program In C\" name=\"Bubble Sort Program In C\"\u003EBUBBLE SORT PROGRAM IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#Bubble Sort\" style=\"text-align: justify;\"\u003EBack To Bubble Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/ Bubble sort program in c\n\n#include\u0026lt;stdio.h\u0026gt; \n\nvoid bubblesort(int a[],int n);\n\nint main() \n{ \n int a[20],i,n; \n printf(\"Enter number of elements in array : \"); \n scanf(\"%d\",\u0026amp;n);\n  \n \/\/ Inputting elements\n for(i=0;i\u0026lt;n;i++) \n { \n printf(\"Enter number %d: \",i+1); \n scanf(\"%d\",\u0026amp;a[i]);\n } \n \n \/\/ Displaying Elements before bubble sort\n printf(\"Items in the array are : \"); \n for(i=0;i\u0026lt;n;i++)\n { \n printf(\"%d \",a[i]); \n } \n \n \/\/Applying bubble sort\n bubblesort(a,n); \n \n \/\/ Displaying elements after bubble sort\n printf(\"\\nElements after bubble sort : \"); \n for(i=0;i\u0026lt;n;i++) \n { \n   printf(\"%d \",a[i]); \n } \n return 0; \n} \n\nvoid bubblesort(int a[],int n) \n{ \n  int i,j;\n  for(i=0; i\u0026lt;=n-2; i++) \n  { \n    for(j=0;j\u0026lt;=n-i-2;j++) \n    { \n       \/\/ Swapping elements\n       if(a[j]\u0026gt;a[j+1]) \n       { \n         int temp=a[j]; \n         a[j]=a[j+1]; \n         a[j+1]=temp; \n      } \n   } \n } \n} \u003C\/span\u003E\n\n\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cspan style=\"color: yellow;\"\u003EMore Informative Posts : \u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html\"\u003ESelection Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html\"\u003EInsertion Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/merge-sort-program-in-c.html\"\u003EMerge Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html\"\u003EQuick Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html\"\u003EHeap Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html\"\u003ECounting Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003ERadix Sort Program In C\u003C\/li\u003E\n\u003Cli\u003EBucket Sort Program In C\u003C\/li\u003E\n\u003Cli\u003EShell Sort Program In C\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n"},"link":[{"rel":"replies","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/5301024430722820563\/comments\/default","title":"Post Comments"},{"rel":"replies","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html#comment-form","title":"0 Comments"},{"rel":"edit","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/5301024430722820563"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/5301024430722820563"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html","title":"Bubble Sort Program In C"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"media$thumbnail":{"xmlns$media":"http://search.yahoo.com/mrss/","url":"http:\/\/4.bp.blogspot.com\/-vRBUD0Sa1y4\/U84K16FwyPI\/AAAAAAAAAKs\/t9NjWBWOKy4\/s72-c\/bubblesort.png","height":"72","width":"72"},"thr$total":{"$t":"0"}},{"id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268.post-1372654398411515917"},"published":{"$t":"2014-06-15T03:10:00.002-07:00"},"updated":{"$t":"2020-11-17T05:18:54.643-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"searching and sorting"}],"title":{"type":"text","$t":"Quick Sort Program In C"},"content":{"type":"html","$t":"\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort\" name=\"Quick Sort\"\u003EQuick Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort In C\"\u003EQuick Sort In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort Algorithm\"\u003EAlgorithm For Quick Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort Program In C\"\u003EQuick Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort Program Output\"\u003EQuick Sort Program Output\u003C\/a\u003E\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003C\/h2\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow; font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort In C\" name=\"Quick Sort In C\"\u003EQUICK SORT IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort\"\u003EBack to Quick Sort\u003C\/a\u003E\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cspan style=\"color: lime;\"\u003EQuick Sort\u003C\/span\u003E is another sorting algorithm that is based on divide and conquer approach. Unlike merge sort that divides input elements according to their position in array, quick sort divides input element according to their values. Here is a three-step divide and conquer process for sorting a typical sub-array.\u003Cbr \/\u003E\n\u003Cbr \/\u003ENeed Python Homework Help:\u0026nbsp;\u003Ca href=\"https:\/\/letstacle.com\/help-with-python-homework\"\u003EGet Python Homework Help from Epert\u003C\/a\u003E\u003C\/div\u003E\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\u003Cbr \/\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\u003Cspan style=\"color: lime;\"\u003E\u003Cb\u003EDivide \u003C\/b\u003E:\u003C\/span\u003E\u003Cspan style=\"font-weight: normal;\"\u003E Partition or rearrange the array \u003Cspan style=\"color: lime;\"\u003Ea[p . . r]\u003C\/span\u003E into two sub-arrays \u003Cspan style=\"color: lime;\"\u003Ea[ p . . q-1 ]\u003C\/span\u003E and \u003Cspan style=\"color: lime;\"\u003Ea[q+1 . . r]\u003C\/span\u003E such that \u003Cspan style=\"color: lime;\"\u003Ea[ p . . q-1 ] \u0026lt;= a[q] \u0026lt;= a[q+1 . . r] . \u003C\/span\u003ECompute the \u003Cspan style=\"color: lime;\"\u003Eindex q\u003C\/span\u003E as part of this partition procedure. Here \u003Cspan style=\"color: lime;\"\u003Ea[q]\u003C\/span\u003E is called the pivot element.\u003C\/span\u003E\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\u003Cspan style=\"color: lime;\"\u003E\u003Cb\u003EConquer \u003C\/b\u003E:\u003C\/span\u003E \u003Cspan style=\"font-weight: normal;\"\u003ESort the two sub-arrays \u003Cspan style=\"color: lime;\"\u003Ea[ p . . q-1 ] \u003C\/span\u003Eand \u003Cspan style=\"color: lime;\"\u003Ea[q+1 . . r] \u003C\/span\u003E\u0026nbsp;by recursive calls to quick sort.\u003C\/span\u003E\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\u003Cspan style=\"color: lime;\"\u003E\u003Cb\u003ECombine \u003C\/b\u003E:\u003C\/span\u003E \u003Cspan style=\"font-weight: normal;\"\u003EBecause the sub-arrays are already sorted, no work is needed to combine them : the entire array \u003Cspan style=\"color: lime;\"\u003Ea[ p . . r ]\u003C\/span\u003E is now sorted.\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003ELets understand Quick Sort with the help of an example :\u0026nbsp; \u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E Array Elements ( List ) : \u003Cspan style=\"color: lime;\"\u003E2 8 7 1 3 5 6 4\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cspan style=\"color: lime;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E Steps :\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli style=\"text-align: justify;\"\u003ESelect the pivot element (\u003Cspan style=\"color: lime;\"\u003E 4\u003C\/span\u003E in this case )\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003ERearrange elements such that elements before pivot element are less than it and element after pivot element are greater than it. This arrangement of elements in accordance with the pivot element is called \u003Cspan style=\"color: lime;\"\u003Epartition operation.\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli style=\"text-align: justify;\"\u003ESort the sub-array recursively.\u0026nbsp;\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/4.bp.blogspot.com\/-BRSv3TNTZEw\/VD34kuLh2rI\/AAAAAAAAAL4\/NLsvaW0gzaY\/s1600\/quick%2Bsort.png\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Steps for Quick Sort\" border=\"0\" height=\"320\" src=\"https:\/\/4.bp.blogspot.com\/-BRSv3TNTZEw\/VD34kuLh2rI\/AAAAAAAAAL4\/NLsvaW0gzaY\/s1600\/quick%2Bsort.png\" title=\"Quick Sort Algorithm And Program In C\" width=\"169\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003ESteps for Quick Sort\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cdiv style=\"text-align: justify;\"\u003E\n\u003Cul\u003E\n\u003Cli\u003EThe above image shows the partition of Array elements ( Initial list ).\u003C\/li\u003E\n\u003Cli\u003ESimilarly the two sub-array before and after pivot element are partitioned.\u003C\/li\u003E\n\u003Cli\u003EThe complete steps of quick sort is shown below.\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Cdiv\u003E\n\u003Ctable align=\"center\" cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/1.bp.blogspot.com\/-Y38rz6vSWIg\/VD4fikqsXmI\/AAAAAAAAAMQ\/Xh4ri6YPjoE\/s1600\/quick%2Bsort%2Bstep.jpg\" style=\"margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Quick Sort Program In C\" border=\"0\" height=\"640\" src=\"https:\/\/1.bp.blogspot.com\/-Y38rz6vSWIg\/VD4fikqsXmI\/AAAAAAAAAMQ\/Xh4ri6YPjoE\/s1600\/quick%2Bsort%2Bstep.jpg\" title=\"Quick Sort Algorithm And Program In C\" width=\"145\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EQuick Sort\u0026nbsp;\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003C\/div\u003E\n\u003Cdiv class=\"separator\" style=\"clear: both; text-align: center;\"\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003C\/div\u003E\n\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow; font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort Algorithm\" name=\"Quick Sort Algorithm\"\u003EQUICK SORT ALGORITHM\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort\"\u003EBack to Quick Sort\u003C\/a\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/ Algorithm for Quick Sort\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003EQUICKSORT(a, p, r)\n  if p\u0026lt;r\n    q = PARTITION(a, p, r)\n    QUICKSORT(a, p, q-1)\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E    \u003C\/span\u003E\u003Cspan style=\"color: blue;\"\u003EQUICKSORT(a, q+1, r)\u003C\/span\u003E\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cspan style=\"color: #660000;\"\u003E\u003Cbr \/\u003E\u003C\/span\u003E\n\u003Cspan style=\"color: #660000;\"\u003EPartitioning the array :\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cbr \/\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003EPARTITION(a, p, r)\n  x=a[r]\n  i=p-1\n \u0026nbsp;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  for j=p to r-1\n     if(a[j]\u0026lt;=x)\n        i=i+1\n        swap a[i] with a[j]\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  end loop\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  \n  swap a[i+1] with a[r]\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E  return i+1\u003C\/span\u003E\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cbr \/\u003E\n\u003C\/span\u003E\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort Program In C\" name=\"Quick Sort Program In C\"\u003EQUICK SORT PROGRAM IN C\u003C\/a\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort\"\u003EBack to Quick Sort\u003C\/a\u003E\u003C\/span\u003E\u003C\/div\u003E\n\u003Cdiv\u003E\n\u003Cbr \/\u003E\u003C\/div\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\/\/Quick sort program ( code ) in c\n\n#include\u0026lt;stdio.h\u0026gt; \n\nvoid quicksort(int a[],int p, int r); \nint partition(int a[],int p, int r); \n\nint main() \n{ \n int a[20],i,n; \n printf(\"Enter number of elements in array : \"); \n scanf(\"%d\",\u0026amp;n);\n  \n \/\/ Inputting elements\n for(i=0;i\u0026lt;n;i++) \n { \n    printf(\"Enter number %d: \",i+1); \n    scanf(\"%d\",\u0026amp;a[i]);\n } \n \n \/\/ Displaying Elements before quick sort\n printf(\"Items in the array are : \"); \n for(i=0;i\u0026lt;n;i++)\n { \n    printf(\"%d \",a[i]); \n } \n \n \/\/Applying quick sort\n quicksort(a,0,n-1); \n \n \/\/ Displaying elements after quick sort\n printf(\"\\nElements after quick sort : \"); \n for(i=0;i\u0026lt;n;i++) \n { \n    printf(\"%d \",a[i]); \n } \n return 0; \n} \n\nvoid quicksort(int a[],int p, int r) \n{\n   int q;\n   if(p\u0026lt;r)\n   {\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E     \/\/ q - index at which pivot element lies\n     q=partition(a,p,r);\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E     \/\/ Sorting sub-array recursively\n     quicksort(a,p,q-1);\n     quicksort(a,q+1,r);\n   }\n}\n\nint partition(int a[],int p, int r)\n{\n   int temp;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E   \u003C\/span\u003E\u003Cspan style=\"color: blue;\"\u003Eint i=p-1;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E   int j;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E\n\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E   \/\/ pivot element around which partition is done\n   int x=a[r];\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E \n   for(j=p;j\u0026lt;=r-1;j++)\n   {\n     if(a[j]\u0026lt;=x)\n     {\n       i=i+1;\n       temp=a[i];\n       a[i]=a[j];\n       a[j]=temp;\n     }\n   }\n \n   temp=a[i+1];\n   a[i+1]=a[r];\n   a[r]=temp;\n   return (i+1);\n}\u003C\/span\u003E\n\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cbr \/\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"font-weight: normal;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#Quick Sort Program Output\" name=\"Quick Sort Program Output\"\u003EQuick Sort Program Output\u003C\/a\u003E\u003C\/span\u003E\u003C\/h2\u003E\n\u003Ctable cellpadding=\"0\" cellspacing=\"0\" class=\"tr-caption-container\" style=\"margin-left: auto; margin-right: auto; text-align: center;\"\u003E\u003Ctbody\u003E\n\u003Ctr\u003E\u003Ctd style=\"text-align: center;\"\u003E\u003Ca href=\"http:\/\/2.bp.blogspot.com\/-B7a4fzKM-qQ\/VRXCDh3WXJI\/AAAAAAAAAQo\/KOt-Mt0G2cU\/s1600\/quick%2Bsort.png\" style=\"clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;\"\u003E\u003Cimg alt=\"Quick Sort Program In C With Output\" border=\"0\" src=\"https:\/\/2.bp.blogspot.com\/-B7a4fzKM-qQ\/VRXCDh3WXJI\/AAAAAAAAAQo\/KOt-Mt0G2cU\/s1600\/quick%2Bsort.png\" title=\"Quick Sort Program In C\" \/\u003E\u003C\/a\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003Ctr\u003E\u003Ctd class=\"tr-caption\" style=\"text-align: center;\"\u003E\u003Cspan style=\"color: lime;\"\u003EQuick Sort : Quick Sort Program Output\u003C\/span\u003E\u003C\/td\u003E\u003C\/tr\u003E\n\u003C\/tbody\u003E\u003C\/table\u003E\n\u003Cbr \/\u003E\n\u003Cspan style=\"color: #660000;\"\u003EMore Informative Posts :\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html\"\u003ECounting Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html\"\u003EHeap Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/merge-sort-program-in-c.html\"\u003EMerge Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html\"\u003EBubble Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html\"\u003ESelection Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html\"\u003EInsertion Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003EShell sort Program In C\u003C\/li\u003E\n\u003Cli\u003ERadix Sort Program In C\u003C\/li\u003E\n\u003Cli\u003EBucket Sort Program In C\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Cul\u003E\u003C\/ul\u003E\n\u003C\/div\u003E\n"},"link":[{"rel":"replies","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/1372654398411515917\/comments\/default","title":"Post Comments"},{"rel":"replies","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html#comment-form","title":"2 Comments"},{"rel":"edit","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/1372654398411515917"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/1372654398411515917"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html","title":"Quick Sort Program In C"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"media$thumbnail":{"xmlns$media":"http://search.yahoo.com/mrss/","url":"https:\/\/4.bp.blogspot.com\/-BRSv3TNTZEw\/VD34kuLh2rI\/AAAAAAAAAL4\/NLsvaW0gzaY\/s72-c\/quick%2Bsort.png","height":"72","width":"72"},"thr$total":{"$t":"2"}},{"id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268.post-4639410090947205978"},"published":{"$t":"2014-06-12T00:55:00.001-07:00"},"updated":{"$t":"2015-03-01T04:13:27.415-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"searching and sorting"}],"title":{"type":"text","$t":"Searching And Sorting In C"},"content":{"type":"html","$t":"\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\n\u003Cdiv style=\"text-align: left;\"\u003E\nOther Searching and Sorting technique will be published soon.\u003C\/div\u003E\n\u003Ch2 style=\"text-align: left;\"\u003E\n\u003Cspan style=\"color: yellow; font-weight: normal;\"\u003ESORTING\u003C\/span\u003E\u003C\/h2\u003E\n\u003Cdiv\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html\"\u003EBubble Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html\"\u003EQuick Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html\"\u003ESelection Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html\"\u003EInsertion Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/merge-sort-program-in-c.html\" target=\"_blank\"\u003EMerge Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/08\/counting-sort-program-in-c.html\"\u003ECounting Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html\"\u003EHeap Sort\u003C\/a\u003E\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003Cul style=\"text-align: left;\"\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n\u003C\/div\u003E\n"},"link":[{"rel":"replies","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/4639410090947205978\/comments\/default","title":"Post Comments"},{"rel":"replies","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/06\/searching-and-sorting.html#comment-form","title":"0 Comments"},{"rel":"edit","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/4639410090947205978"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/4639410090947205978"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/06\/searching-and-sorting.html","title":"Searching And Sorting In C"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"thr$total":{"$t":"0"}},{"id":{"$t":"tag:blogger.com,1999:blog-8285804830535272268.post-3780073962876284526"},"published":{"$t":"2014-06-12T00:49:00.000-07:00"},"updated":{"$t":"2015-03-01T04:22:58.934-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"searching and sorting"}],"title":{"type":"text","$t":"Merge Sort Program In C"},"content":{"type":"html","$t":"\u003Cdiv dir=\"ltr\" style=\"text-align: left;\" trbidi=\"on\"\u003E\nHere I am providing you with \u003Cspan style=\"color: lime;\"\u003EMerge Sort\u003C\/span\u003E program in c.\u003Cbr \/\u003E\n\u003Cdiv class=\"mokcode\"\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E#include\u0026lt;stdio.h\u0026gt; \n\nvoid mergesort(int a[],int i, int j); \nvoid merge(int a[],int p , int q, int r1); \n\nint main() \n{ \n int a[20],i,n,item; \n printf(\"Enter number of elements in array : \"); \n scanf(\"%d\",\u0026amp;n);\n  \n \/\/ Inputting elements\n for(i=0;i\u0026lt;n;i++) \n { \n   printf(\"Enter number %d: \",i+1); \n   scanf(\"%d\",\u0026amp;a[i]);\n } \n \n \/\/ Displaying Elements before merge sort\n printf(\"Items in the array are : \"); \n for(i=0;i\u0026lt;n;i++)\n { \n   printf(\"%d \",a[i]); \n } \n \n \/\/Applying merge sort\n mergesort(a,0,n-1); \n \n \/\/ Displaying elements after merge sort\n printf(\"\\nElements after merge sort : \"); \n for(i=0;i\u0026lt;n;i++) \n { \n   printf(\"%d \",a[i]); \n } \n return 0; \n} \n\nvoid mergesort(int a[],int i, int j) \n{ \n int mid; \n if(i\u0026gt;=j) \n return; \n \n else \n { \n   mid=(i+j)\/2; \n   mergesort(a,i,mid); \n   mergesort(a,mid+1,j); \n   merge(a,i,mid,j);  \n } \n} \n\nvoid merge(int a[],int p , int q, int r) \n{ \n int n1=q-p+1; \n int n2=r-q;\n int left[n1+1];\n int right[n2+1]; \n\n int i=0;\n int j=0;\n int k=0;\n \n \n for(i=0;i\u0026lt;n1;i++) \n {\n   left[i]=a[p+i]; \n }\n \n for(i=0;i\u0026lt;n2;i++) \n {\n   right[i]=a[q+i+1];\n }\n \n left[n1]=9999; \n right[n2]=9999;  \n \n i=0;\n j=0;\n \n for(k=p;k\u0026lt;=r;k++) \n { \n \n   if(left[i]\u0026lt;right[j]) \n   { \n     a[k]=left[i]; \n     i++; \n   } \n \n   else \n   { \n     a[k]=right[j]; \n     j++; \n   } \n }\u0026nbsp;\u003C\/span\u003E\u003C\/pre\u003E\n\u003Cpre\u003E\u003Cspan style=\"color: blue;\"\u003E} \u003C\/span\u003E\n\n\u003C\/pre\u003E\n\u003C\/div\u003E\n\u003Cspan style=\"color: yellow;\"\u003EMore Informative Posts :\u003C\/span\u003E\u003Cbr \/\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/12\/insertion-sort-algorithm-time-complexity-and-program-in-c.html\"\u003EInsertion Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/selection-sort-program-in-c.html\"\u003ESelection Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Cspan style=\"color: yellow;\"\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/06\/quick-sort-program-in-c.html\"\u003EQuick Sort Program In C\u003C\/a\u003E\u003C\/span\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/counting-sort-program-in-c.html\"\u003ECounting Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2014\/07\/bubble-sort-program-in-c.html\"\u003EBubble Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003E\u003Ca href=\"http:\/\/www.comp-psyche.com\/2015\/01\/heap-sort-program-in-c.html\"\u003EHeap Sort Program In C\u003C\/a\u003E\u003C\/li\u003E\n\u003Cli\u003EBucket Sort Program In C\u003C\/li\u003E\n\u003Cli\u003EShell Sort Program In C\u003C\/li\u003E\n\u003Cli\u003ERadix Sort Program In C\u003C\/li\u003E\n\u003C\/ul\u003E\n\u003C\/div\u003E\n"},"link":[{"rel":"replies","type":"application/atom+xml","href":"https:\/\/www.comp-psyche.com\/feeds\/3780073962876284526\/comments\/default","title":"Post Comments"},{"rel":"replies","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/06\/merge-sort-program-in-c.html#comment-form","title":"0 Comments"},{"rel":"edit","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/3780073962876284526"},{"rel":"self","type":"application/atom+xml","href":"https:\/\/www.blogger.com\/feeds\/8285804830535272268\/posts\/default\/3780073962876284526"},{"rel":"alternate","type":"text/html","href":"https:\/\/www.comp-psyche.com\/2014\/06\/merge-sort-program-in-c.html","title":"Merge Sort Program In C"}],"author":[{"name":{"$t":"Mantu Kumar"},"uri":{"$t":"http:\/\/www.blogger.com\/profile\/02897308282659594376"},"email":{"$t":"noreply@blogger.com"},"gd$image":{"rel":"http://schemas.google.com/g/2005#thumbnail","width":"16","height":"16","src":"https:\/\/img1.blogblog.com\/img\/b16-rounded.gif"}}],"thr$total":{"$t":"0"}}]}});