{"id":815,"date":"2017-04-02T18:38:10","date_gmt":"2017-04-03T02:38:10","guid":{"rendered":"http:\/\/www.tech.dimprash.com\/?p=815"},"modified":"2017-04-15T18:00:49","modified_gmt":"2017-04-16T02:00:49","slug":"sort-algorithms","status":"publish","type":"post","link":"http:\/\/www.tech.dimprash.com\/?p=815","title":{"rendered":"Sort Algorithms"},"content":{"rendered":"<p><strong>Stable Sort:<\/strong>   A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, <\/p>\n<p><strong>Complete Binary Tree:<\/strong> A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.  A Binary Heap is a complete Binary Tree. <\/p>\n<p>Heap Sort:<br \/>\n<a href=\"http:\/\/quiz.geeksforgeeks.org\/heap-sort\/\">http:\/\/quiz.geeksforgeeks.org\/heap-sort\/<\/a><br \/>\nKarumanchi is also good for explanation , pg 180-185<\/p>\n<pre>\r\n\/\/ To heapify a subtree rooted with node i which is\r\n\/\/ an index in arr[]. n is size of heap\r\nvoid heapify(int arr[], int n, int i)\r\n{\r\n    int largest = i;  \/\/ Initialize largest as root\r\n    int l = 2*i + 1;  \/\/ left = 2*i + 1\r\n    int r = 2*i + 2;  \/\/ right = 2*i + 2\r\n \r\n    \/\/ If left child is larger than root\r\n    if (l < n &#038;&#038; arr[l] > arr[largest])\r\n        largest = l;\r\n \r\n    \/\/ If right child is larger than largest so far\r\n    if (r < n &#038;&#038; arr[r] > arr[largest])\r\n        largest = r;\r\n \r\n    \/\/ If largest is not root\r\n    if (largest != i)\r\n    {\r\n        swap(arr[i], arr[largest]);\r\n \r\n        \/\/ Recursively heapify the affected sub-tree\r\n        heapify(arr, n, largest);\r\n    }\r\n}\r\n \r\n\/\/ main function to do heap sort\r\nvoid heapSort(int arr[], int n)\r\n{\r\n    \/\/ Build heap (rearrange array)\r\n    for (int i = n \/ 2 - 1; i >= 0; i--)\r\n        heapify(arr, n, i);\r\n \r\n    \/\/ One by one extract an element from heap\r\n    for (int i=n-1; i>=0; i--)\r\n    {\r\n        \/\/ Move current root to end\r\n        swap(arr[0], arr[i]);\r\n \r\n        \/\/ call max heapify on the reduced heap\r\n        heapify(arr, i, 0);\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Stable Sort: A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, Complete Binary Tree: A complete binary tree is a &hellip; <a href=\"http:\/\/www.tech.dimprash.com\/?p=815\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Sort Algorithms<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-815","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/815","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=815"}],"version-history":[{"count":4,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/815\/revisions"}],"predecessor-version":[{"id":891,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/815\/revisions\/891"}],"wp:attachment":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=815"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=815"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=815"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}