선택 정렬 - 안정

Question

스와핑하는 대신 선택 정렬을 안정적인 정렬로 변경하기 위해 삽입 할 수 있음을 읽었습니다. 나는 같은 온라인을 다음과 같이 구현했다. ( (1,0), (2,0), (5,0), (4,0), 5,1를 :

 void selection (int a[], int n) 

    { 
while (--n > 0) { 
    int i, max = n; 

    for (i = 0; i < n; i++) { 
     if (a[i] >= a[max]) 
     max = i; 
    } 

    if (max != n) { 
     int save = a[max]; 

     for (i = max; i < n; i++) 
     a[i] = a[i + 1]; 

     a[n] = save; 
    } 
} 
} 

나는이 다음에 대한 안정적인 정렬 될 것입니다 방법을 이해 해달라고

)

나는 위에서 언급 한 구현은 내가 볼 해달라고 (,) 5,0)

을 (1,0), (2,0), (4,0), (5,1을 줄 것이라고 생각 이것은 안정적인 행동으로 이해합니다. 나 맞아. 그렇다면 안정적인 선택 정렬을 어떻게 구현할 수 있습니까?

다음 코드를 변경하면 안정적인 선택 정렬이 가능합니다. 내가 틀렸다면 나를 바로 잡아라. 이 경우, 우리에게 내가 생각 원하는 결과를주지 않을 줄

for (i = 0; i < n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

, 그것은 늘 내가 정렬 준 데이터에 대한 안정적인 결과를 제공합니다. 나는 다음 코드가 잘 될 것이라고 생각한다.

for (i = 0; i <= n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

내가 잘못하면 나를 교정 해 주시겠습니까?

감사

Answer 1

당신이 게시 코드는 안정적인 일종의 것 같다.

선택 루프에서 마지막으로 최대 값 발생이 항상 선택됩니다. 이는 a[i] > a[max]이 아닌 a[i] >= a[max]이라고 말하기 때문입니다.

for (i = 0; i < n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

그런 다음 선택한 요소가 끝에 배치됩니다 (안정된 정렬을 적용해야 함). 요소의 나머지 부분은 교체되지 않고 모두 이동되기 때문에 순서는 변경되지 않습니다. 이렇게하면 같은 값을 가진 요소가 동일한 순서, 즉 안정적인 정렬로 유지됩니다.