정렬은 배열의 요소가 검색 가능성을 높이기 위해 특정 순서로 배열되는 기본 작업입니다. 간단히 말하면, 데이터는 쉽게 검색 될 수 있도록 정렬됩니다.
비교 차트
| 비교 근거 | 삽입 정렬 | 선택 정렬 |
|---|---|---|
| 기본 | 데이터는 기존 정렬 된 파일에 데이터를 삽입하여 정렬됩니다. | 정렬 된 위치에 연속 요소를 선택하여 배치하여 데이터를 정렬합니다. |
| 자연 | 안정된 | 불안정한 |
| 따라야 할 과정 | 요소는 미리 위치를 지정하는 동안 미리 검색됩니다. | 요소가 검색되는 동안 위치는 이전에 알려졌습니다. |
| 즉각적인 데이터 | 삽입 정렬은 즉각적인 데이터를 처리 할 수있는 실시간 정렬 기법입니다. | 즉각적인 데이터를 처리 할 수 없기 때문에 처음에는 데이터가 있어야합니다. |
| 최상의 사례 복잡성 | 에) | O (n2) |
삽입 정렬의 정의
삽입 정렬 은 기존 정렬 된 파일에 값 집합을 삽입하여 작동합니다. 한 번에 하나의 요소를 삽입하여 정렬 된 배열을 생성합니다. 이 과정은 전체 배열이 어떤 순서로 정렬 될 때까지 계속됩니다. 삽입 정렬의 기본 개념은 각 항목을 최종 목록의 적절한 위치에 삽입하는 것입니다. 삽입 정렬 방법은 효과적인 메모리 양을 절약합니다.
삽입 정렬 작업
- 하나는 정렬 된 데이터를 저장하고 다른 하나는 정렬되지 않은 데이터를 저장하는 두 세트의 배열을 사용합니다.
- 정렬 알고리즘은 정렬되지 않은 집합에 요소가있을 때까지 작동합니다.
- 배열에 'n'숫자 요소가 있다고 가정 해 봅시다. 처음에는 인덱스가 0 (LB = 0) 인 요소가 정렬 된 집합에 있습니다. 나머지 요소는 목록의 정렬되지 않은 파티션에 있습니다.
- 정렬되지 않은 부분의 첫 번째 요소에는 배열 인덱스 1 (LB = 0 인 경우)이 있습니다.
- 각 반복 후에 정렬되지 않은 파티션의 첫 번째 요소를 선택하고 정렬 된 집합의 적절한 위치에 삽입합니다.
삽입 정렬의 장점
- 작은 데이터 세트와 함께 사용하면 쉽게 구현되고 매우 효율적입니다.
- 삽입 정렬의 추가 메모리 공간 요구 사항이 적습니다 (즉, O (1)).
- 새 요소를 받으면 목록을 정렬 할 수 있으므로 라이브 정렬 기술로 간주됩니다.
- 다른 정렬 알고리즘보다 빠릅니다.
예 :
선택의 정의 정렬
선택 정렬 은 최소 값 번호를 검색하여 순서 (오름차순 또는 내림차순)에 따라 첫 번째 또는 마지막 위치에 배치하여 정렬을 수행합니다. 최소 키를 검색하여 올바른 위치에 배치하는 프로세스는 모든 요소가 올바른 위치에 놓일 때까지 계속됩니다.
선택 정렬 작업
- 메모리에 N 개의 요소가있는 배열 ARR을 가정합니다.
- 첫 번째 패스에서 가장 작은 키가 위치와 함께 검색되면 ARR [POS]가 ARR [0]과 바뀝니다. 따라서 ARR [0]이 정렬됩니다.
- 두 번째 패스에서 N-1 요소의 부분 배열에서 다시 가장 작은 값의 위치가 결정됩니다. ARR [POS]과 ARR [1]을 교환하십시오.
- 패스 N-1에서는 N 개의 요소를 소트하기 위해 동일한 처리가 수행된다.
예 :
삽입 정렬 및 선택 정렬의 주요 차이점
- 삽입 정렬은 대개 삽입 작업을 수행합니다. 반대로, 선택 정렬은 필수 요소의 선택과 위치 지정을 수행합니다.
- 삽입 정렬은 안정적인 것으로 알려져 있지만 선택 정렬은 안정적인 알고리즘이 아닙니다.
- 삽입 정렬 알고리즘에서 요소는 이전에 알려져 있습니다. 반면, 선택 정렬에는 미리 위치가 포함됩니다.
- 삽입 정렬은 실시간 정렬 기법으로 도착하는 요소가 목록에서 즉시 정렬되는 반면 선택 정렬은 즉각적인 데이터에서 제대로 작동하지 않습니다.
- 삽입 정렬에는 최상의 경우에 O (n) 실행 시간이 있습니다. 반대로, 선택 정렬의 런타임 최적화가 가장 좋은 경우는 O (n2)입니다.
삽입 정렬의 복잡성
삽입 정렬의 가장 복잡한 경우는 O (n) 번입니다. 즉 배열이 이전에 정렬 된 경우입니다. 같은 방법으로 배열이 역순으로 정렬 될 때 정렬되지 않은 배열의 첫 번째 요소는 정렬 된 집합의 각 요소와 비교됩니다. 최악의 경우, 삽입 정렬의 실행 시간은 2 차식입니다 (예 : O (n2)) . 평균적인 경우에도 최소 (k-1) / 2 비교를해야합니다. 따라서, 평균 경우도 2 차 주행 시간 O (n2)를 갖는다.
선택 정렬의 복잡성
선택 작업으로 sort는 배열 요소의 원래 순서에 의존하지 않으므로 선택 정렬의 최상의 경우와 최악의 경우의 복잡성간에 큰 차이는 없습니다.
선택 정렬은 최소값 요소를 선택하고, 선택 프로세스에서 모든 'n'개의 요소가 스캔됩니다. 따라서 n-1 비교는 첫 번째 단계에서 이루어집니다. 그런 다음 요소가 상호 교환됩니다. 마찬가지로 두 번째 패스에서 두 번째로 작은 요소를 찾으려면 나머지 n-1 요소를 검색해야하며 전체 배열이 정렬 될 때까지 프로세스가 계속됩니다.
따라서, 선택 정렬의 실행 시간 복잡도는 O (n2) 이다.
= (n-1) + (n-2) + ......... .. + 2 + 1
= n (n-1) / 2 = O (n2)
결론
두 정렬 알고리즘 중에서 삽입 정렬은 빠르고 효율적이며 안정적이며 선택 정렬은 작은 요소 집합이 포함되거나 목록이 부분적으로 이전에 정렬 될 때 효율적으로 작동합니다. 선택 정렬에 의한 비교 횟수는 수행 된 이동보다 크며 요소를 이동하거나 교체 한 횟수는 삽입 정렬에서 비교 한 것보다 큽니다.
