Writing in the front

When doing a set of NetEase pen test questions on the niuke network, there is a question to insert sort, so I find out “data structure” sorting ideas to do a small summary.

Insertion sort

  • Insert sort: including direct insert sort, Hill sort

Direct insertion sort

1. The thought

The idea behind direct insertion sort is that if we want to sort an array, we use a new array to hold the sorted result. The new array starts with only one data element and increases each time. The sort ends when the new array has the same number of elements as the original array.

And just to make sure you understand that I’m using a new array, I’m not actually introducing a new array, it’s a subset of the original array, and the subset keeps getting bigger and bigger until it’s as big as the original array. Linglong stops saying new array

1. Suppose the n data elements to be sorted are stored in the array, and the subarray takes the first element A [0].

2. The first loop compares the size of a[0] and a[1], if a[0]>a[1], then put a[1] before a[0]. You go from one element to two.

3. For the second comparison, we compare the sizes of a[2] with a[1],a[0]. First compare a[2] with a[1], and put a[1] after a[2] if a[2]<a[1]. Then compare the size of a[2] and a[0] to determine whether to insert a[2] before a[0]……

4. When the last element a[n-1] is compared with the previous n-1 element, the set of data elements is arranged.

2. For example

Let’s give an example to reinforce the impression. See the order below

2. Result after the first sorting: subset is [5,64]. And then you do a second comparison where you compare 7 to 64 and then you compare 5

3. Results after the second sorting: subset [5,7,64]. Then a third comparison is made to compare 89 with the subset, and it is found that if 89 is greater than 64, no further comparison is made

4. Third sorting result: subset [5,7,64,89]. 6 is then compared with the subset for the fourth time.

5. Fourth sorting result: subset [5,6,7,64,89]. And then 24 is compared to that.

6. Fifth sorting result: the subset is equal to the original array, the sorting is finished.

3. Complexity analysis

  • Best case: the raw data is sorted, the outer layer controls n-1 times, the inner layer compares only once each time, and the element assignment statement executes twice each time, so the assignment statement executes 2 times (n-1). Time complexity O(n).
  • Worst case: Original data in reverse order, time complexity O(n*2). – Rank randomly: between best and worst.

Hill sorting

Hill sort, also known as reduced increment sort, is an updated version of direct insertion sort, so let’s look at the idea

1. The thought

Hill sort divides the number to be sorted into several groups according to step size (step size is interval ·), and conducts direct insertion sort for the elements of each group. Then reduce the step size and group again, sort each group. Until the last step =1, the last insertion sort is done when there is only one element in a group. End of sorting.

Characteristics of 2.

  • Compared with direct insertion sort, hill sort has the advantage that grouping sort can make the whole array elements close to order and improve the time efficiency.
  • The inconsistent step size of grouping shows instability.

3. For example

  • In this example, the first concession length is 6. (a) The circles, triangles and squares in the figure represent different groups. There are six groups in total, and each group is sorted in quick order.
  • Figure (b) is the sorted result in Figure A first, and then it is divided into groups with a length of 3, and a quick sort is conducted for each group.
  • (c) The graph gets the result of graph B and then groups it with step size of 1, and then sorts it. End of the sort

To summarize

  • This sort has a quadruple loop. The first loop is the number of steps (hill values), 6,3,1 in the example above. Hill value is self – set, with uncertainty. The second loop controlled the grouping, for example, the first one divided into six groups, the second one divided into three groups, and the last one only had one group. The third and fourth level loops are the same as the two levels of direct insertion sort loops mentioned above.

4. Complexity analysis

The complexity of Hill sort is uncertain. The actual time required is related to the number of groups and step size. The reasonable time complexity of sort is O(n(LBN)*2), and the space complexity is O(1).

At the end of the article

Ee ending… ee ending…