이 문서는 자바 스크립트에서 정렬 알고리즘을 다루는 시리즈의 일부입니다. 당신은 여기에 시리즈의 나머지 부분을 찾을 수 있습니다. 정렬 알고리즘 또는 일반적으로 알고리즘을 처음 사용하는 경우 먼저 읽어 앞으로 나아갈 수있는 견고한 기반을 확보하십시오. 오늘 나는 삽입 정렬의 기능과 아웃을 다룰 것입니다. 삽입 정렬은 더 복잡하지만 거품 정렬보다 조금 더 유용합니다. 그것에 대한 최악의 시나리오는 버블 정렬과 비슷하지만 가장 좋은 경우는 목록이 거의 정렬되었거나 이미 정렬 된 것으로 확신 할 때 적합합니다. 큰 그림을 보자.
삽입 정렬은 목록 내의 각 요소를보고(두 번째 요소부터 시작)이전 항목과 비교하여 작동합니다. 앞의 항목이 큰 경우,그들은 교환된다. 이 항목은 우리가 목록의 다음 요소에 대해 동일한 작업을 수행하는 시점에서 작은 때까지 계속됩니다.
삽입 정렬이 모두 나쁜 것은 아닙니다.. 당신이 적당한 상황에서 그것을 사용할 한.작은 목록에 대한 정렬 알고리즘보다 더 빠릅니다.
복잡성
이 알고리즘의 시간 복잡도는 최악의 경우 2 차—영형(엔 2). 으로 엔 무한대에 접근 평균 케이스는 최악의 경우를 2 로 나눈 값에 접근합니다. 그러나 목록이 정렬되거나 거의 정렬 된 경우 최상의 시나리오에서 영형(엔)이 될 수 있으므로 해당 시나리오에 잘 적응할 수 있습니다.
빠른 경우
위에서 언급 한 바와 같이 특정 상황에서 빠를 수 있습니다. 배열을 고려하십시오,병합 정렬과 같은 알고리즘을 사용할 때 우리는 여전히 모든 항목을 분할 한 다음 다시 병합해야합니다. 삽입 정렬을 사용하면 올바른’지금까지 정렬 된’순서에 있는지 확인한 다음 모두 1 에 대해 하나의 인덱스를 이동해야합니다.
삽입 정렬은 적응 형 정렬이기 때문에’온라인 알고리즘’이기도하므로 모든 항목을 가져 오기 전에 정렬을 시작한 다음 부분 정렬이 완료되면 목록을 병합 할 수 있습니다.
의사 코드
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
코드
다음은? 정렬 병합. 오늘날 브라우저에서 가장 널리 사용되는 정렬 알고리즘 중 하나입니다.
