DAA-선택 정렬

이러한 유형의 정렬을 Selection Sort반복적으로 요소를 정렬하여 작동합니다. 다음과 같이 작동합니다. 먼저 배열에서 가장 작은 요소를 찾아 첫 번째 위치의 요소와 교환 한 다음 두 번째로 작은 요소를 찾아 두 번째 위치의 요소와 교환하고 전체 배열이 될 때까지이 방식으로 계속합니다. 정렬되었습니다.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

선택 정렬은 가장 간단한 정렬 기술 중 하나이며 작은 파일에 매우 적합합니다. 각 항목이 실제로 최대 한 번 이동하므로 매우 중요한 응용 프로그램이 있습니다.

섹션 정렬은 매우 큰 개체 (레코드)와 작은 키가있는 파일을 정렬하기 위해 선택하는 방법입니다. 배열이 이미 내림차순으로 정렬되어 있고 오름차순으로 정렬하려는 경우 최악의 경우가 발생합니다.

그럼에도 불구하고 선택 정렬 알고리즘에 필요한 시간은 정렬 할 배열의 원래 순서에 크게 민감하지 않습니다. A[j] < min x 모든 경우에 정확히 동일한 횟수로 실행됩니다.

선택 정렬은 배열의 정렬되지 않은 부분에서 최소 요소를 찾는 데 대부분의 시간을 소비합니다. 선택 정렬과 버블 정렬의 유사성을 명확하게 보여줍니다.

버블 정렬은 각 단계에서 남은 최대 요소를 선택하지만 배열의 정렬되지 않은 부분에 순서를 부여하는 데 약간의 노력을 낭비합니다.
선택 정렬은 최악의 경우와 평균적인 경우 모두 2 차적이며 추가 메모리가 필요하지 않습니다.

각각 i ...에서 1 ...에 n - 1, 하나의 교환이 있고 n - i 비교, 그래서 총 n - 1 교환 및

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 비교.

이러한 관찰은 입력 데이터가 무엇이든 관계없이 유지됩니다.

최악의 경우 2 차가 될 수 있지만 평균적인 경우이 수량은 O(n log n). 그것은running time of Selection sort is quite insensitive to the input.

이행

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}