선택의 효율성 정렬 대 삽입 정렬

Question

현재 삽입 정렬과 선택 정렬을 모두 Python으로 구현하려고합니다. 두 가지 구현 모두 작동합니다. 그러나 정렬을 수행 할 때 선택 정렬은 삽입 정렬보다 약 1.5 배 빠르기 때문에 정렬 정렬을 구현하면 선택 정렬을 절반으로 구현할 수 있습니다. 나는 이것에 대한 이유를 찾을 수없는 것 같습니다. select_sort는 N 스왑 않지만

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이지만 안쪽 루프의 insert_sort입니다.