Эффективность выбора Сортировка против вставки Сортировка

Question

В настоящее время я пытаюсь реализовать сортировку и сортировку вставки в python. Обе мои реализации работают. Однако, когда я сортирую сортировку, сортировка сортировки последовательно выполняет примерно в 1,5 раза быстрее, чем сортировка вставки, хотя моя реализация сортировки вставки составляет примерно половину такого количества сравнений, что и моя реализация сортировки. Кажется, я не могу найти причины для этого.

def select_sort(data): 
    for i in range(len(data)): 
     minimum, index = None, i 
     for j in range(i, len(data)): 
      if minimum is None: 
       minimum = data[j] 
      if data[j] < minimum: 
       minimum = data[j] 
       index = j 
     data[i], data[index] = data[index], data[i] 
    return data 

def insert_sort(data): 
    for i in range(1, len(data)): 
     for j in range(i, 0, -1): 
      if data[j] >= data[j - 1]: 
       break 
      data[j], data[j - 1] = data[j - 1], data[j] 
    return data 

def time_sort(S): 
    elapsed = [] 

    start = time() 
    insert_sort(copy(S)) 
    elapsed.append(time() - start) 

    start = time() 
    select_sort(copy(S)) 
    elapsed.append(time() - start) 

    return elapsed 

Answer 1

insert_sort делает O (N 2 ) свопы, в то время как select_sort делает N свопы.

Подкачка находится во внешнем контуре select_sort, но во внутреннем контуре insert_sort.