다음 선택 정렬 코드와 혼동

Question

int i,j,t; 

for(i=0;i<n-1;i++) 
{ 
    for(j=i+1;j<n;j++) 
    { 
     if(a[i]>a[j]) 
     { 
      t=a[i]; 
      a[i]=a[j]; 
      a[j]=t; 
     } 
    } 
} 

내 질문에 위의 코드가 올바른 선택 정렬 코드인지 아닌지 여부입니다. 나는 다양한 책에서이 코드를 얻었다. 틀린 경우 이유를 설명하십시오.

Answer 1

예 코드가 정확합니다. 기본적으로 배열을 오름차순으로 정렬하려면 값 비싼 O(n^2)이 필요합니다.

각 단계 i [0..n-1]에서 인덱스 에 인덱스 i 사이에 가장 작은 요소를 넣습니다.

스왑 기능을 사용하면 i 인덱스에있는 두 개의 비교 값 중 작은 값을 배치 지속적으로 있는지 확인합니다.

Answer 2

제 생각에는 질문에 표시된 정렬은 선택 정렬이 아닌 거품 정렬입니다.

다른 아카이브 코드에서 나는 다른 정렬 알고리즘에 대한 테스트 베드를 가지고 있습니다. 테스트 베드에는 버블, 선택, 삽입 및 빠른 정렬이 포함되며 비교 및 ​​스왑을 모니터링합니다.

일종의 버블 정렬과 선택을위한 코드 : 지금 거품의 외부 루프는 일종의 아니라 최대보다 카운트 다운,하지만 더 중요한 점은 선택하는 것이 왜 기억하지 않습니다

static void selection_sort(Data a[], int n) 
{ 
    for (int i = 0; i < n - 1; i++) 
    { 
     int min = i; 
     for (int j = i + 1; j < n; j++) 
     { 
      inc_comps(); 
      if (a[j] < a[min]) 
       min = j; 
     } 
     inc_comps(); 
     if (min != i) 
      swap(&a[min], &a[i]); 
    } 
} 

static void bubble_sort(Data a[], int n) 
{ 
    for (int i = n - 1; i > 0; i--) 
    { 
     for (int j = 0; j < i; j++) 
     { 
      inc_comps(); 
      if (a[j] > a[j+1]) 
       swap(&a[j], &a[j+1]); 
     } 
    } 
} 

정렬은 질문에 표시된 코드와 크게 다르며 질문의 코드는 버블 정렬과 훨씬 더 밀접한 관련이 있습니다.

또한 위키 백과에서 설명한 많은 알고리즘과 많은 알고리즘이 포함 된 Sorting Algorithm을 찾을 수 있으며 정렬에 대한 여러 소스로 연결됩니다.

테스트 베드는 다른 크기의 데이터 세트에서 다른 데이터 패턴을 사용하여 다른 알고리즘을 실행합니다. 출력의 일부는 데이터 10,000 행 (유형 int)를위한 것입니다

Number    Filler Sorter  Compares   Swaps    Time 
    10000    Random  Quick   151583   88111 PASS 0.000593 
    10000    Random Bubble  49995000  24895500 PASS 0.143897 
    10000    Random Insertion  24905489  24895500 PASS 0.028966 
    10000    Random Selection  50004999   9986 PASS 0.040409 
    10000   Ascending  Quick   151719   90480 PASS 0.000584 
    10000   Ascending Bubble  49995000  24876354 PASS 0.141219 
    10000   Ascending Insertion  24886345  24876354 PASS 0.022601 
    10000   Ascending Selection  50004999   9988 PASS 0.041173 
    10000   Descending  Quick   119881   74247 PASS 0.000251 
    10000   Descending Bubble  49995000  49995000 PASS 0.081584 
    10000   Descending Insertion  49995000  49995000 PASS 0.055118 
    10000   Descending Selection  50004999   5000 PASS 0.050586 
    10000 Forward Organ Pipe  Quick  25000000  25005000 PASS 0.034033 
    10000 Forward Organ Pipe Bubble  49995000  24995000 PASS 0.070633 
    10000 Forward Organ Pipe Insertion  25004999  24995000 PASS 0.022398 
    10000 Forward Organ Pipe Selection  50004999   9987 PASS 0.048300 
    10000 Reverse Organ Pipe  Quick  25005002  16665004 PASS 0.025632 
    10000 Reverse Organ Pipe Bubble  49995000  24995000 PASS 0.064798 
    10000 Reverse Organ Pipe Insertion  25000000  24995000 PASS 0.022568 
    10000 Reverse Organ Pipe Selection  50004999   9886 PASS 0.053838 
    10000   Uniform  Quick  49995000   19998 PASS 0.030855 
    10000   Uniform Bubble  49995000    0 PASS 0.038719 
    10000   Uniform Insertion   9999    0 PASS 0.000021 
    10000   Uniform Selection  50004999    0 PASS 0.041021 

당신은 데이터에서 볼 수 있듯이, 선택 정렬 점수도에 그것을 수행하는 스왑 수 있지만 잘에서의 수 비교. 이것은 질문에있는 알고리즘이 선택 정렬이 아닌 버블 정렬이라는 내 관찰을 검증 할 수있는 방법을 제공합니다.