Insertion sort

The basic idea

At each step, an object to be sorted is inserted into the appropriate position of the previously sorted group of objects according to its key code size until all objects are inserted.

Insertion sort algorithm

  • Move from left to right by a pointer
  • Each move compares the incoming number with the sorted number, and then inserts the appropriate position
  • Repeat the above steps until the last data is inserted into the appropriate position, and you have sorted the original array from smallest to largest

  • Divide an array into sorted and unsorted parts
  • Element 2 is divided into sorted parts
  • Each iteration then inserts an unsorted element into the appropriate sorted place
  • As the 6 enters the sorted area compare one by one from right to left until the 6 is in place

  • And then 5 goes into the sorted region
  • Compare 5 with 6. 5 is less than 6 so switch 5 and 6

  • Now we’re going to compare 5 to 2, 5 is greater than 2 so we’re not going to switch and stay where we are
  • And then you put 1 into the sorted region

  • When the 1 element is in the sorted region, it is swapped from right to left until 1 is where it should be.

Code implementation

class Solution:
    def insertionArraySor(self, nums) :
        n = len(nums)
        for i in range(1, n):
            j = i
            while nums[j-1] > nums[j] and j > 0:
                nums[j-1], nums[j] = nums[j],nums[j-1]
                j -= 1

        return nums
Copy the code
  • First initializej=i
  • thenwhile nums[j-1] > nums[j] and j > 0The inserted data is then compared to the sorted region element by element

Shell sort

Hill sort can be viewed as either optimizing insertion sort or shrinking incremental sort.

The basic idea

Let the sequence to be sorted have N elements, take an integer gap(gap<n) as the interval, divide all elements into GAP subsequence, and put all elements with gap distance in the same subsequence. Direct insertion sort is used in each subsequence. Then narrow the gap, for example, gap = gap/2, and repeat the subsequence division and sorting.

Hill sort general process

  • Divide the array with n elements into gap = N //2 n/gap number sequence, the first data and the n/2+1 data are a pair
  • A loop sorts each sequence pair
  • Then, gap = gap//2, then n/gap, sorted again
  • Repeat this process, reducing the number of sequences to one and completing the sequence

  • First, take a group of numbers at every interval (gap) 3 to perform insertion sort
  • After this iteration, we have some general appearance of the order. The larger number is on the right side of the sequence, and the smaller number is on the left
  • And that’s the beauty of Hill sort, because insertion sort has a small swap

Code implementation

    def sellArraySort(self, nums) :
        n = len(nums)
        gap = n // 2
        while gap > 0:
            for i in range(gap,n):
                anchor = nums[i]
                j = i
                while j>=gap and nums[j-gap] > anchor:
                    nums[j] = nums[j - gap]
                    j -= gap
                nums[j] = anchor
            gap = gap // 2
        return nums
Copy the code
  • range(gap,n)ifgap=3It starts at 3 and goes to the end of the array

  • First we define two Pointers I and j where I goes from gap to n
  • First, both I and J point to the current number, and then compare the j-Gap position value and the current anchor value. J-gap position value is larger than the current value, so the two values are exchanged (as shown in the figure below).

This diagram gives a graphical representation of the code to illustrate what the code means