Painted levels: being fostered fostered fostered

Tags: “Algorithm” “D&C” “quickSort” author: MrLiuQ Review: QiShare team

The previous article introduced recursion and tail recursion. This article will introduce quicksort based on recursion.

Read this article and you will learn:

  • The idea of divide and rule: abbreviationD&C, a recursive problem solving solution.
  • Quicksort: useD&CThe idea is to realize an efficient sorting method.

I. The idea of “Divide and rule” (D&C)

Divide and conquer (D&C) is a well-known recursive problem-solving method.

A problem solving algorithm is of limited use, but D&C provides us with an idea. When faced with a complex problem, we should ask ourselves: “Can D&C solve this problem?”

So, what is D&C?

1.1 What is D&C?

The problem solving process with D&C is divided into two steps:

  1. Find a baseline condition that is as simple as possible. (See above for definitions of baseline conditions)
  2. Keep breaking the problem down (reducing the size) until all the baseline conditions are met.

1.2 Examples of D&C

Scenario: Suppose you are a farmer and you have a rectangular piece of land (168m x 64m).

Question: Now you need to divide the field into several squares (easy to manage and grow vegetables). Ask what is the maximum size that can be divided into smaller squares. (Note: do not leave the land empty, to maximize the use of land resources)

  • Plan 1: find out the largest common divisor of “length” and “width”. (My first thought was this.)

  • Plan 2: using D&C idea, first remove several largest squares from the big rectangle, then remove several largest squares from the small rectangle, and keep looking until there are no small rectangles.

Steps:

  1. Find the baseline condition: length is an integer multiple of width
  2. Decompose continuously: After removing all the largest squares, decompose the small rectangles

Diagram:

First: Find two large squares with sides of 64m, remove them, leaving smaller rectangles of 64m x 40m.

The second time: find a small square with a side length of 40m, remove it, leaving a small rectangle of 40m x 24m.

Third time: find a small square with a side length of 24m, remove it, leaving a small rectangle of 24m x 16m.

Fourth time: find a small square with a side length of 16m, take it out, leaving a small rectangle of 16m x 8m.

Fifth time: find two small squares with 8m sides, just finish dividing.

Therefore, the farm is divided into small square fields with a maximum side length of 8m.

And the idea of solving the problem is D&C thought.

Let’s review the core of D&C’s thinking:

  • Identify simple baseline conditions.
  • Determine how to reduce the size of the problem to fit the baseline criteria.

Second, quicksort

QuickSort takes advantage of this D&C idea. It is an efficient sorting scheme.

2.1 Idea of fast Sorting (based on D&C)

  • Baseline condition: If the number of elements in the sorted array is less than 2, this parameter is returned.
  • Downsizing: Take one element at a time from the array to be sorted (base value), place elements less than or equal to that element on one side, and elements greater than that element on the other side. I’m going to do the same thing with the small arrays on both sides.

2.2 Example of fast queue

Based on Python, a quick sorting is implemented: the code is as follows:

def quickSort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]

        return quickSort(less) + [pivot] + quickSort(greater)

print quickSort([10, 2, 6, 4, 7, 2])
Copy the code

Read the code:

PS: The base value can be the first element or the last element.

2.3 Animation demonstration of fast row

In this Demo, the last element of the array is the base value, and the elements less than or equal to the base value are placed on the left, and the elements greater than the base value are placed on the right.

Recommended articles:

IOS avoid common crashes (2) algorithm small column: select sort iOS Runloop (a) iOS common debugging method: LLDB command iOS common debugging method: breakpoint iOS common debugging method: static analysis iOS message forwarding strange dance weekly