{"id":25225,"date":"2017-10-15T15:53:29","date_gmt":"2017-10-15T10:23:29","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25225"},"modified":"2017-10-15T15:53:29","modified_gmt":"2017-10-15T10:23:29","slug":"lower-bound-comparison-based-sorting-algorithms","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/lower-bound-comparison-based-sorting-algorithms\/","title":{"rendered":"Lower bound for comparison based sorting algorithms"},"content":{"rendered":"

The problem of sorting can be viewed as following.<\/span><\/p>\n

Input:<\/strong> A sequence of n<\/em> numbers <a<\/em>1<\/sub>, a<\/em>2<\/sub>, . . . , an<\/sub><\/em>>.
\nOutput:<\/strong> A permutation (reordering) <a<\/em>\u20181<\/sub>, a<\/em>\u20182<\/sub>, . . . , a<\/em>\u2018n<\/sub><\/em>> of the input sequence such that a<\/em>\u20181<\/sub> <= a<\/em>\u20182<\/sub> \u2026.. <= a\u2018n<\/sub><\/em>.<\/p>\n

A sorting algorithm is comparison based if it uses comparison operators to find the order between two numbers.\u00a0 Comparison sorts can be viewed abstractly in terms of decision trees. A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.\u00a0T<\/span><\/span>he execution of the sorting algorithm corresponds to tracing a path from the root of the decision tree to a leaf. At each internal node, a comparison ai<\/sub><\/em> <= aj<\/sub><\/em> is made. The left subtree then dictates subsequent comparisons for ai<\/sub><\/em> <= aj<\/sub><\/em>, and the right subtree dictates subsequent comparisons for ai<\/sub><\/em> > aj<\/sub><\/em>. When we come to a leaf, the sorting algorithm has established the ordering. So we can say following about the decison tree.<\/p>\n

1) <\/strong>Each of the n<\/em>! permutations on n<\/em> elements must appear as one of the leaves of the decision tree for the sorting algorithm to sort properly.<\/p>\n

2) <\/strong>Let x be the maximum number of comparisons in a sorting algorithm. The maximum height of the decison tree would be x. A tree with maximum height x has at most 2^x leaves.<\/p>\n[ad type=”banner”]\n

After combining the above two facts, we get following relation.<\/p>\n

  \r\n      n!\u00a0 <= 2^x\r\n\r\n Taking Log on both sides.\r\n      log2<\/sub>(n!)  <= x\r\n\r\n Since log2<\/sub>(n!)  = \u0398(nLogn),  we can say\r\n      x = \u03a9(nLog2<\/sub>n)\r\n<\/pre>\n
Therefore, any comparison based sorting algorithm must make at least nLog2<\/sub>n comparisons to sort the input array, and Heapsort and merge sort are asymptotically optimal comparison sorts.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Lower bound for comparison based sorting algorithms – Searching and sorting – A sorting algorithm is comparison based if it uses comparison operators to find the order between two numbers.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,71670],"tags":[72320,72319,72318,72317,71893,72337,72339,72302,72321,72315,72329,72326,71146,72341,72314,72344,72336,72313,72324,72312,71885,72343,72311,70271,70876,72327,70873,70880,72333,70075,72316,72332,72345,71274,72334,72342,71709,71714,71702,71880,70016,72145,70548,72322,72328,72340,71695,70020,71161,71149,72101,72335,71142,72325,70544,72330,72323,72338,72331],"class_list":["post-25225","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-searching-and-sorting","tag-algorithm-decision-tree","tag-algorithm-for-decision-tree","tag-algorithm-for-heap-sort-in-data-structure","tag-algorithm-of-heap-sort-in-data-structure","tag-algorithm-sort","tag-analysis-of-sorting-algorithms","tag-best-algorithm-for-sorting","tag-best-sorting","tag-binary-decision-tree-algorithm","tag-blower","tag-comparison-of-all-sorting-algorithms","tag-comparison-of-running-times","tag-comparison-of-sorting-algorithms","tag-comparison-of-sorting-algorithms-in-data-structure","tag-comparison-of-sorting-algorithms-pdf","tag-comparison-of-sorting-methods-in-data-structure","tag-data-structure-sorting-algorithms","tag-decision-tree-algorithm","tag-decision-tree-elements","tag-decision-tree-model","tag-decision-tree-sorting","tag-define-heap-sort-in-data-structure","tag-fastest-sort","tag-heap-sort","tag-heap-sort-algorithm-in-data-structure","tag-heap-sort-algorithm-with-example-in-data-structure","tag-heap-sort-in-data-structure","tag-heapsort-example","tag-lg-n","tag-linear-sort","tag-lower-bound-theory-comparison-trees-for-searching-and-sorting","tag-material2","tag-merge-k-sorted-lists","tag-merge-sort-algorithm-in-data-structure","tag-merge-sort-ppt","tag-n-nlogn","tag-quick-sort-ppt","tag-quicksort-algorithm-in-data-structure","tag-quicksort-algorithm-with-example-in-data-structure","tag-radix-sort-in-c","tag-selection-sort-algorithm","tag-selection-sort-algorithm-with-example","tag-selection-sort-in-data-structure","tag-sort-3","tag-sort-b","tag-sort-tree","tag-sorted","tag-sorting-algorithms","tag-sorting-algorithms-comparison","tag-sorting-algorithms-in-data-structures","tag-sorting-algorithms-pdf","tag-sorting-algorithms-ppt","tag-sorting-in-data-structure","tag-sorting-network-in-parallel-computing","tag-time-complexity-of-merge-sort","tag-tree-comparison","tag-tree-comparison-algorithm","tag-tree-sort-algorithm","tag-what-is-heap-sort-in-data-structure-with-example"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25225","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25225"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25225\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25225"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25225"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25225"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}