Divide-and-conquer algorithm: Difference between revisions

Revision as of 01:10, 3 September 2023

Revision as of 12:08, 23 December 2023

Line 9:

[[File:Merge sort algorithm diagram.svg|thumb|Divide-and-conquer approach to sort the list (38, 27, 43, 3, 9, 82, 10) in increasing order. ''Upper half:'' splitting into sublists; ''mid:'' a one-element list is trivially sorted; ''lower half:'' composing sorted sublists.]]

The divide-and-conquer paradigm is often used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve them in turn, and to compose their solutions to solve the given problem. Problems of sufficient simplicity are solved directly.

For example, to sort a given list of ''n'' [[Natural number|natural numbers]], split it into two lists of about ''n''/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). This approach is known as the [[merge sort]] algorithm.

The name "divide and conquer" is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as the [[binary search]] algorithm for finding a record in a sorted list (or its analogue in [[numerical algorithm|numerical computing]], the [[bisection algorithm]] for [[root-finding algorithm|root finding]]).<ref name="CormenLeiserson2009">{{cite book|author1=Thomas H. Cormen|author2=Charles E. Leiserson|author3=Ronald L. Rivest|author4=Clifford Stein|title=Introduction to Algorithms|url=https://books.google.com/books?id=aefUBQAAQBAJ&q=%22Divide-and-conquer%22|date=31 July 2009|publisher=MIT Press|isbn=978-0-262-53305-8}}</ref> These algorithms can be implemented more efficiently than general divide-and-conquer algorithms; in particular, if they use [[tail recursion]], they can be converted into simple [[loop (computing)|loops]]. Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a "divide-and-conquer algorithm". Therefore, some authors consider that the name "divide and conquer" should be used only when each problem may generate two or more subproblems.<ref>Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.</ref> The name '''decrease and conquer''' has been proposed instead for the single-subproblem class.<ref>Anany V. Levitin, ''Introduction to the Design and Analysis of Algorithms'' (Addison Wesley, 2002).</ref>