알고리즘 정렬 효율성 비교

Question

간단한 정렬 알고리즘으로 익숙해졌고 의사 코드보다는 알고리즘 설명에서 삽입 정렬을 만들려고했습니다. 내가 근무하는 알고리즘을 만들어 나는 설명 장착 생각했다 :

import random 
nums = [] 
for i in range(10000): 
    nums.append(random.randrange(0, 1000)) 

def getSortedIndexForEle(ele, sorted): 
    for i in range(0, len(sorted)): 
     if ele < sorted[i]: 
      return i 
    return len(sorted) 

def sort(lst): 
    sorted = [] 
    for ele in lst: 
     sorted.insert(getSortedIndexForEle(ele, sorted), ele) 
    return sorted 

print(sort(nums)) 

코드가 (여전히 올바른 결과 생산) 현명한 알고리즘 compisition 일치하지 않습니다 그러나 그렇게 나는 또 다른 시도했다 :

import random 
nums = [] 
for i in range(10000): 
    nums.append(random.randrange(0, 1000)) 

def sort(lst): 
    for i in range(1, len(lst)): 
     ele = lst[i] 
     j = i - 1 
     for k in range(j, -2, -1): 
      if ele >= lst[k]: 
       break 
      lst[k + 1] = lst[k] 
     lst[k + 1] = ele 


sort(nums) 
print(nums) 

을

나는 이것이 정확하다고 생각하고, 의사 코드와 비교해 보았는데 실제로는 똑같은 일을한다.

제 질문은 알고리즘에 맞지 않는 첫 번째 알고리즘입니다. 길이가 10000이고 모든 요소가 임의의 숫자 인 목록을 사용하여 내 컴퓨터에서 실제 시간의 절반 정도를 실행합니다. 어떻게 가능할까요? 두 번째 알고리즘이 올바르지 않습니까? 나는 알고리즘의 파이썬 예제를 시도해 보았고 심지어 첫 번째 알고리즘보다 오래 걸렸다. ...

Answer 1

두 번째는 제자리에서 정렬되지 않았으므로 첫 번째 것은 정렬되지 않는다.

두 번째 알고리즘에서는 각 요소를 원래 배열에 삽입하고 그 이후의 모든 요소는 그 요소를 수용하기 위해 이동해야합니다. 시간 복잡성은 O (n2)이지만 일정 O (1) 추가 메모리 만 필요합니다.

첫 번째 경우에는 별도의 배열에 요소를 삽입하고 이미 정렬 된 큰 요소 만 이동해야합니다. 그래서 시간 복잡성은 O (n)과 O (n2) 사이의 어딘가에 있지만 O (n) 여분의 메모리가 필요합니다.

Answer 2

Heres는 내 머리 꼭대기에서 삽입 정렬합니다 (미안하지만 가상 코드로되어 있지만 실제로 작동하는 방식에 대한 기본 아이디어가 있어야합니다).

이

for (int index = 1; index < array.length; index++) 

이 하나의 작업이 컬렉션의 끝에 모든 방법을 슬라이드하는 것입니다 (우리가 두 번째 시작주의 사항 :이 방법에 대해

for (int index = 1; index < array.length; index++) { 
    for (int insertion = index; insertion > 0 && array[insertion] < array[insertion - 1]; --insertion) { 
     swap(array[insertion], array[insertion - 1]; 
    } 
} 

생각, 우리는 두 이동 커서가 첫 번째가 아니라 항목!).

for (int insertion = index; ...; --insertion) 

이 우리의 비교 포인트가 어디 index 포인트 및 이동 시작을 의미합니다 :

for (int insertion = index - 1; array[insertion] < array[insertion - 1] && insertion > 0; --insertion) 

이 하나 그래서 나는 떨어져 할게요 길이 :

그런 다음 우리는이 하나 있습니다 뒤로 반복 할 때마다입니다. (흠, 왜 거꾸로?) 우리는 뒤로 밀어 우리는 두 개의 비교를 필요로

for (; insertion > 0 && array[insertion] < array[insertion - 1];) 

:

(1) 0보다 삽입 인덱스 큰가요? 컬렉션의 '기본'에 도달하면 분명히 완료됩니다. 계속할 필요가 없으며 index 한 단계 앞으로 이동하십시오.

(2) 항목이 insertion으로 표시되어 있으며 이전 항목보다 작습니까? 그건 옳지 않아, 우린 그걸 교환해야 해.사실, 우리는 index의 왼쪽에있는 모든 것이 정렬 될 때까지 항목 쌍을 거꾸로 교환합니다.

는 기본적으로 명령문의 조합은 유지 :

이

다음 (1), (1)에서 index을 넣어 바로 왼쪽의 모든 정렬합니다. [0]과 [1]의 두 항목 만 있으므로 쉽습니다.

(2) 색인을 앞으로 이동하십시오. 이제 3 개의 항목이 있습니다. [0], [1] 및 [2]를 정렬하십시오. 하나씩 색인을 앞으로 이동하고 진행하면서 왼쪽을 정렬합니다.

(3) index을 앞쪽으로 밀어 넣음으로써 소개 된 새로운 항목이 제자리로 들어가는 것을 보장함으로써 '정렬'합니다. 그것이 바로 array[insertion] < array[insertion - 1]의 요지입니다. 즉, 새로 도입 된 항목을 원하는 위치에 앉힐 때까지 뒤로 미십시오.

(4) 왼편은 항상 정의에 따라 정렬되기 때문에, index을 증가시킨 후에해야 할 일은 새로운 항목을 제자리에 옮기는 것입니다.

증가시킨 다음 새 항목을 제자리로 밀어 넣습니다. 린스하고 반복하십시오.

시각적으로 :

[1, 2, 3, 4, 0] 

제로 그렇게 할 때 index = 4, insertion = 4뿐만 아니라, 장소를 벗어났습니다. 그런 다음 뒤로 비교를 시작합니다.

배열 [4] < 배열 [4 - 1]입니까? 예 < 4 0이 있으므로 교환 : 다시

[1, 2, 3, 0, 4] 

배열 [3] < 배열 [1 - 3]가 있습니까? 예 3 0 < 스왑 :

[1, 2, 0, 3, 4] 

거듭 우리 때문에 그 시점 배열 [삽입] < 어레이 상기 제 1 위치로 이동할 때까지 0 [삽입 - 1] 거짓 일 것이다.

기본적으로 index의 왼쪽에는 배열 [삽입] < 배열 [삽입 - 1]과 같은 항목이 없음을 확인하는 것입니다. 2 개의 요소에 해당하는 경우 3 개를 확인한 다음 4 개를 확인합니다.

흥미롭게도 정렬이 완료되면 매번 왼쪽의 전체를 검사 할 필요가 없습니다. of place of NEW 요소가 증가하여 도입되었습니다 index. 즉, 새 항목을 추가하면 에만 항목이 잘못 배치 될 수 있으므로 해당 위치로 이동하면 정의에 따라 왼쪽 전체가 정렬됩니다!