추천, 2024

에디터의 선택

삽입 정렬 및 선택 정렬의 차이점

삽입 정렬 및 선택 정렬은 데이터를 정렬하는 데 사용되는 기법입니다. 주로 삽입 정렬 및 선택 정렬은 데이터를 정렬하는 데 사용하는 방법으로 구분할 수 있습니다. 삽입 정렬은 미리 값이 지정된 파일에 값을 삽입하여 값 집합을 정렬합니다. 한편, 선택 정렬은 목록에서 최소 숫자를 찾아서 순서대로 정렬합니다.

정렬은 배열의 요소가 검색 가능성을 높이기 위해 특정 순서로 배열되는 기본 작업입니다. 간단히 말하면, 데이터는 쉽게 검색 될 수 있도록 정렬됩니다.

비교 차트

비교 근거삽입 정렬선택 정렬
기본
데이터는 기존 정렬 된 파일에 데이터를 삽입하여 정렬됩니다.정렬 된 위치에 연속 요소를 선택하여 배치하여 데이터를 정렬합니다.
자연
안정된불안정한
따라야 할 과정
요소는 미리 위치를 지정하는 동안 미리 검색됩니다.요소가 검색되는 동안 위치는 이전에 알려졌습니다.
즉각적인 데이터
삽입 정렬은 즉각적인 데이터를 처리 할 수있는 실시간 정렬 기법입니다.즉각적인 데이터를 처리 할 수 ​​없기 때문에 처음에는 데이터가 있어야합니다.
최상의 사례 복잡성에)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 개의 요소를 소트하기 위해 동일한 처리가 수행된다.

예 :

삽입 정렬 및 선택 정렬의 주요 차이점

  1. 삽입 정렬은 대개 삽입 작업을 수행합니다. 반대로, 선택 정렬은 필수 요소의 선택과 위치 지정을 수행합니다.
  2. 삽입 정렬은 안정적인 것으로 알려져 있지만 선택 정렬은 안정적인 알고리즘이 아닙니다.
  3. 삽입 정렬 알고리즘에서 요소는 이전에 알려져 있습니다. 반면, 선택 정렬에는 미리 위치가 포함됩니다.
  4. 삽입 정렬은 실시간 정렬 기법으로 도착하는 요소가 목록에서 즉시 정렬되는 반면 선택 정렬은 즉각적인 데이터에서 제대로 작동하지 않습니다.
  5. 삽입 정렬에는 최상의 경우에 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)

결론

두 정렬 알고리즘 중에서 삽입 정렬은 빠르고 효율적이며 안정적이며 선택 정렬은 작은 요소 집합이 포함되거나 목록이 부분적으로 이전에 정렬 될 때 효율적으로 작동합니다. 선택 정렬에 의한 비교 횟수는 수행 된 이동보다 크며 요소를 이동하거나 교체 한 횟수는 삽입 정렬에서 비교 한 것보다 큽니다.

Top