Insertion Sort

Computing the number of swaps in insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as “Quick Sort”, “Heap Sort”, or “Merge Sort”. However, insertion sort provides several advantages: simple implementation, efficient for (quite) small data sets, O(1)O(1) extra space.
When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.
Source: Wikipedia
Although it is one of the elementary sorting algorithms with O(n2)O(n2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).
For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as “Merge Sort” or “Quick Sort”.
Visualization by David R. Martin: http://www.sorting-algorithms.com/insertion-sort

Problem

Insertion sort is a simple algorithm with quadratic running time that builds the final sorted array one item at a time.

Given: A positive integer n≤103n≤103 and an array A[1..n]A[1..n] of integers.
Return: The number of swaps performed by insertion sort algorithm on A[1..n]A[1..n].

Sample Dataset

6
6 10 4 5 1 2

Sample Output

12

from typing import List
def insertSort(nums: List[int]) -> int:
    n = len(nums)
    cnt = 0
    for i in range(1, n):
        k = i  # 插入起始
        while k > 0 and nums[k-1] > nums[k]:  # ascending
            nums[k-1], nums[k] = nums[k], nums[k-1]
            k -= 1
            cnt += 1
    print(nums)
    return cnt
print(insertSort([6, 10, 4, 5, 1, 2]))

Discussion

For this problem, it is enough to implement the pseudocode above with a quadratic running time and to count the number of swaps performed. Note however that there exists an algorithm counting the number of swaps in .
Note also that Insertion Sort is an in-place algorithm as it only requires storing a few counters.

见评论区的二叉搜索树查找（即交换多少次）并实现插入 ，当然这个过程是进行查找 次的同时 x 就是树中的节点，还进行插入操作。因而当 时，最坏时间复杂度为 ，比上面排序快很多！

import java.util.Arrays;
import java.util.List;
class Node {
    private Node left, right;
    private int value;
    public Node(int value) {
        this.value = value;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public void setRight(Node right) {
        this.right = right;
    }
    public Node getLeft() {
        return left;
    }
    public Node getRight() {
        return right;
    }
    public int getValue() {
        return value;
    }
}
class BinaryTree {
    private int swaps = 0;
    public BinaryTree(List<Integer> values) {
        Node root = new Node(values.get(0));
        for (int i = 1; i < values.size(); i++) {
            Node currentNode = new Node(values.get(i));
            insert(root, currentNode);
            count(root, currentNode);
        }
    }
    private void insert(Node root, Node node) {
        if(node.getValue() < root.getValue()){
            Node left = root.getLeft();
            if (left == null){
                root.setLeft(node);
            }
            else{
                insert(root.getLeft(), node);
            }
        }
        else{
            Node right = root.getRight();
            if (right == null){
                root.setRight(node);
            } else{
                insert(root.getRight(), node);
            }
        }
    }
    private void count(Node root, Node currentNode){
        if(root != null){
            if(root.getValue() > currentNode.getValue()){
                swaps++;
            }
            count(root.getRight(), currentNode);
            count(root.getLeft(), currentNode);
        }
    }
    public int getSwaps(){
        return swaps;
    }
}
public class Main {
    public static void main(String[] args) {
        List<Integer> values= Arrays.asList(VALUES_SEPARATED_BY_COMMA);
        BinaryTree tree = new BinaryTree(values);
        System.out.println(tree.getSwaps());
    }
}