선택 정렬. 안정적인 알고리즘으로 선택 정렬하는 방법?

Question

나는이 선택 정렬 알고리즘을 사용하고있다. 이 구현을 안정적으로 수행하는 방법은 무엇입니까? 나는 그것의 불가능을 생각/

int selection_sort1 (int ai_numbers[], const int ci_count) 
{ 
    int counter = 0; 
    int i, minIndex, j; 

    for (i = 0; i < ci_count; i++) 
    { 
     minIndex = i; 
     for (j = i + 1; j < ci_count; j++) 
     { 
      if (ai_numbers[j] < ai_numbers[minIndex]) 
      { 
       minIndex = j; 
      } 
     } 
     swap (&ai_numbers[i], &ai_numbers[minIndex]); 
     counter++; 
    } 


    return counter; 
} 

Answer 1

귀하의 구현 은 안정되지 않습니다. 반복 할 때마다 배열의 i 위치에있는 요소를 가져 와서 나머지 배열의 임의 위치에 놓습니다. 그러면 원래 순서가 엉망이됩니다. 이미 교환하지 않고 장소 i에 삽입을

을 같이

• 나머지 목록 이리저리 최소의 요소를 선택 : 당신이 안정적인 정렬하려면

  당신은해야합니다. 즉, 남은 요소를 오른쪽으로 이동하여 배치 할 요소의 공간을 확보해야합니다.

는

이 동일한 값을 갖는 요소가 정렬 된 배열과 배열의 기존 순서에 위치 보장한다.

(실수를 지적 주석 Groo 덕분에) 위키 피 디아에서 직접 찍은

Answer 2

:

선택 종류의 안정적인 종류로 구현 될 수있다. 2 단계에서 스와핑하지 않고 첫 번째 위치에 최소값을 삽입하면 (즉, 모든 중간 항목이 아래로 이동 한 경우) 알고리즘이 안정적입니다. 그러나이 수정에는 링크 된 목록과 같은 효율적인 삽입 또는 삭제를 지원하는 데이터 구조가 필요하거나 Θ (n2) 쓰기를 수행해야합니다. 당신은 항상 (적은 다음에 반대하거나 값과 동일한으로) 최소값 후 작은 값을 교환하기 때문에

그래서 기본적으로는 안정적인 종류가 않습니다.