선택 정렬

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2019년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

선택 정렬

클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	${\displaystyle O}$( ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$)${\displaystyle$O$(n^{2$})$$비교$$, $O{\displaystyle }$ (${\displaystyle n)}$ ${\displaystyle$ O$(n)}$ 스왑$$
베스트 케이스 공연	${\displaystyle O}$( ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(n^{2})$ 비교$$, $O{\displaystyle }$( ${\displaystyle 1}$) ${\displaystyle$O(1)$스왑$
평균 공연	${\displaystyle O}$( ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$)${\displaystyle$O$(n^{2$})$$비교$$, $O{\displaystyle }$ (${\displaystyle n)}$ ${\displaystyle$ O$(n)}$ 스왑$$
최악의 경우 공간 복잡성	${\displaystyle O}$( ${\displaystyle 1}$) ${\displaystyle$ O$(1)}$ 보조$$

컴퓨터 공학에서 선택 정렬은 내부 비교 정렬 알고리즘이다. O(n²) 시간의 복잡성이 있어 대형 리스트에서 비효율적이며, 일반적으로 유사한 삽입 종류보다 성능이 떨어진다. 선택 분류는 단순성으로 주목받으며 특히 보조 메모리가 제한된 특정 상황에서 더 복잡한 알고리즘에 비해 성능상의 이점을 가지고 있다.

알고리즘은 입력 목록을 두 부분으로 나눈다: 목록의 앞쪽(왼쪽)에서 왼쪽에서 오른쪽으로 쌓아올린 항목의 정렬된 하위 목록과 나머지 부분을 차지하는 나머지 비정형 항목의 하위 목록이다. 처음에 정렬된 하위 목록은 비어 있고 정렬되지 않은 하위 목록은 전체 입력 목록이다. 알고리즘은 정렬되지 않은 하위 목록에서 가장 작은 요소(또는 정렬 순서에 따라 가장 큰 요소)를 찾아 가장 왼쪽의 정렬되지 않은 요소와 교환(교환)하고 하위 목록 경계를 한 요소 오른쪽으로 이동하는 방식으로 진행한다.

선택 분류의 시간 효율성은 2차적이므로 선택 분류보다 시간 복잡성이 더 좋은 분류 기법이 많이 있다. 선택과 다른 정렬 알고리즘을 구분하는 한 가지는 가능한 최소 수의 스왑(최악의 경우 n - 1)을 만든다는 것이다.

예

다음은 다섯 가지 요소를 정렬하는 정렬 알고리즘의 예:

선택 정렬 애니메이션. 빨간색은 현재 최소값이다. 노란색은 정렬 목록이다. 파란색은 현재 아이템이다.

(마지막 두 숫자가 이미 순서대로 되어 있었기 때문에 이 마지막 두 줄에는 아무것도 변하지 않은 것으로 나타난다.)

선택 정렬은 링크된 목록과 같이 추가 및 제거를 효율적으로 만드는 목록 구조에도 사용될 수 있다. 이 경우 목록의 나머지 부분에서 최소 요소를 제거한 다음 지금까지 정렬된 값의 끝에 삽입하는 것이 더 일반적이다. 예를 들면 다음과 같다.

arr[] = 64 25 12 22 11  // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64  // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64  // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64  // Find the minimum element in arr[3...4] /// 그리고 arr[3...4] 11 12 22 25 64의 시작 부분에 놓는다.  

구현

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. (2019년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

아래는 C의 구현이다.

/* a[0] to a[aLength-1]은(는) 정렬할 어레이임 */ 인트로 i,j; 인트로 aLength; // 의 길이에 맞게 초기화  /* 전체 어레이를 통해 포지션을 확장 */ /* (단일 원소도 최소 원소이므로 aLength-1을 할 수 있음) */ 을 위해 (i = 0; i < aLength-1; i++) {     /* 정렬되지 않은 a[i... aLength-1]에서 최소 요소 찾기 */      /* 최소값이 첫 번째 원소라고 가정한다 */     인트로 jMin = i;     /* 가장 작은 */를 찾은 후 원소를 대상으로 테스트     을 위해 (j = i+1; j < aLength; j++)     {         /* 이 요소가 더 작으면 새로운 최소값 */         만일 (a[j] < a[jMin])         {             /* 새로운 최소값을 찾음. 인덱스 */를 기억하십시오.             jMin = j;         }     }      만일 (jMin != i)      {         바꾸다(a[i], a[jMin]);     } } 

복잡성

배열의 데이터에 의존하는 루프가 없기 때문에 선택 정렬은 다른 정렬 알고리즘에 비해 분석하기 어렵지 않다. 최소값을 선택하려면 $n{\displaystyle }$ ${\displaystyle n}$ 요소를$$ $검색$한 다음${\displaystyle (\mathrm{n}}$- 1 {\$displaystyle$ n-1$}$ 비교$$) 첫 번째 위치로 스와핑해야 한다. 다음으로 가장 낮은 요소를 찾으려면 나머지 $n{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle n-1}$ 요소 등을$$ 검색해야 한다. 따라서 총 비교 횟수는 다음과 같다.

${\displaystyle (n-1)+(n-2)+++...+1=\sum _{i=1}^{n-1}i}$

산술적 수열로,

${\displaystyle \sum _{i=1}^{n-1i={\frac {(n-1)+1}{2}}(n-1)={\frac {1}{1}{1}:{1}{1}{1}-n)}$

비교 횟수에 있어$$ $복잡성{\displaystyle }$ O${\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(n^{2})}$이다. 이러한 각 스캔에는 $n{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle n-1}$ 요소에$$ 대해 하나의 스왑이 필요하다(마지막 요소는 이미 제자리에 있음).

다른 정렬 알고리즘과 비교

2차 정렬 알고리즘(단순 평균 사례 θ(n²)로 정렬 알고리즘 중에서 선택 정렬은 거의 항상 버블 정렬과 gnome 정렬을 능가한다. 삽입 정렬은 k번째 반복 후에 $배열$의 첫$$번째 k {\$displaystyle$ k$}$ 요소가$$ 정렬되어 있다는 점에서 매우 유사하다. 삽입 정렬의 장점은 $k{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle k+1}$ st$$ 요소를 배치하기 위해 필요한 만큼의 요소만 스캔하는 반면 선택 정렬은 ${\displaystyle \mathrm{k}}$+ 1 ${\displaystyle k+1}$ st$$ 요소를 찾기 위해 나머지 모든 요소를 스캔해야 한다는 점이다.

간단한 계산을 통해 삽입 정렬은 정렬하기 전의 배열 순서에 따라 대개 선택 정렬의 절반 정도의 비교를 수행할 수 있지만, 일반적으로는 선택 정렬의 절반 정도의 비교를 수행할 수 있다는 것을 알 수 있다. 일부 실시간 애플리케이션에서는 어레이의 순서와 상관없이 선택 정렬이 동일하게 수행되는 반면 삽입 정렬의 실행 시간은 상당히 다를 수 있다는 장점이 있다고 볼 수 있다. 그러나 이는 어레이가 이미 정렬되어 있거나 "정렬에 가깝게" 실행될 경우 훨씬 더 효율적으로 실행된다는 점에서 삽입 정렬에 유리한 경우가 더 많다.

${\displaystyle }$ 정렬은 쓰기 수 ${\displaystyle \mathrm{측면}}$에서 삽입 정렬(n${\displaystyle }$- 1 ${\displaystyle n-1}$ 스왑$$ 대 $n{\displaystyle }$ ${\displaystyle (n}$- ${\displaystyle 1}$)${\displaystyle }$/ 2 ${\displaystyle n(n-1)/2}$ 스왑$$)을 사용하는 것이 바람직하지만, 이는 사이클 정렬에 의해 달성되는 이론적 최소값의 약 2배에 해당하며, 최대 n 쓰기 작업에서 수행된다. EEPROM이나 플래시 메모리와 같이 쓰기 비용이 읽기보다 훨씬 더 높을 경우, 쓰기 작업마다 메모리의 수명을 줄이는 것이 중요하다.

선택 정렬은 CPU 분기 예측 변수의 이익을 위해 예측 불가능한 분기 없이 구현될 수 있으며, 분기 없는 코드에서 최소값의 위치를 찾은 다음 스왑을 무조건 수행하면 된다.

마지막으로 선택 정렬은 larger${\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle n}$ $){\displaystyle \Theta(n\log$ n$)}$ 병합과 같은 분할 및 변환$$ 알고리즘에 의해 더 큰 어레이에서 크게 상회된다. 그러나 삽입 정렬 또는 선택 정렬은 작은 배열(즉, 10–20 요소 미만)에서 일반적으로 더 빠르다. 재귀 알고리즘의 실무에서 유용한 최적화는 삽입 정렬 또는 선택 정렬로 전환하여 "충분히 작은" 하위 목록을 만드는 것이다.

변형

heapsort는 암묵적 힙 데이터 구조를 사용하여 가장 낮은 기준점을 찾아 제거하는 속도를 높여 기본 알고리즘을 크게 향상시킨다. If implemented correctly, the heap will allow finding the next lowest element in ${\displaystyle \Theta (\log n)}$ time instead of ${\displaystyle \Theta (n)}$ for the inner loop in normal selection sort, reducing the total running time to ${\displaystyle \Theta (n\log n)}$.

선택 분류의 양방향 변종(이중 선택 분류 또는 칵테일 셰이커 분류와 유사하기 때문에 칵테일 분류라고 함)은 모든 통과에서 목록의 최소값과 최대값을 모두 찾는다. 이를 위해서는 두 항목당 3가지 비교가 필요하지만(한 쌍의 요소를 비교한 다음 최대값과 비교한 다음 최대값과 비교한 다음 최소값과 비교한 후 최소값과 비교한 결과) 항목당 1가지 비교가 필요하지만, 순 25% 절감액인 패스 수가 절반에 불과하다.

선택 정렬은 2단계에서 스와핑이 아닌 최소값을 첫 번째 위치에 삽입하고 간섭 값을 위로 이동하면 안정적인 정렬로 구현될 수 있다. 그러나 이 수정은 링크된 목록과 같이 효율적인 삽입 또는 삭제를 지원하는 데이터 구조를 요구하거나 $\theta {\displaystyle \mathrm{}}$(${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle \Teta (n^{2})$ 쓰기를$$ 수행하게 한다.

빙고 분류 변종에서는 가장 큰 가치를 찾기 위해 나머지 아이템을 반복적으로 훑어보고 그 값을 가진 모든 아이템을 최종 위치로 이동시켜 아이템을 분류한다.^[1] 등수를 세듯이 중복된 값이 많으면 효율적인 변종이다. 즉, 선택 분류는 이동된 항목별로 나머지 항목을 통과하는 반면 빙고 분류는 각 값에 대해 1회 통과를 하는 것이다. 가장 큰 값을 찾기 위한 초기 통과 후 후속 통과는 다음 유사 코드에서와 같이 다음 값을 찾으면서 해당 값을 가진 모든 항목을 최종 위치로 이동시킨다(광선은 0 기반이며 포루프는 Pascal에서와 같이 상단 및 하단 한계를 모두 포함한다).

바로 맞췄다(배열하다 A)  { 이 절차는 다음을 기준으로 오름차순으로 정렬됨   최대 항목을 끝까지 반복적으로 이동 } 시작되다     지난 := 길이(A) - 1;      { 첫 번째 반복은 이후의 반복과 매우 유사하게 보이도록 기록된다.       스와프 없이 말이야 }     넥스트맥스 := A[지난];     을 위해 i := 지난 - 1 완전히 0 하다         만일 A[i] > 넥스트맥스 그때             넥스트맥스 := A[i];     하는 동안에 (지난 > 0) 그리고 (A[지난] = 넥스트맥스) 하다         지난 := 지난 - 1;      하는 동안에 지난 > 0 하다 시작되다         PrevMax := 넥스트맥스;         넥스트맥스 := A[지난];         을 위해 i := 지난 - 1 완전히 0 하다              만일 A[i] > 넥스트맥스 그때                  만일 A[i] <> PrevMax 그때                      넥스트맥스 := A[i];                  다른 시작되다                      바꾸다(A[i], A[지난]);                      지난 := 지난 - 1;                  종지부를 찍다         하는 동안에 (지난 > 0) 그리고 (A[지난] = 넥스트맥스) 하다             지난 := 지난 - 1;     종지부를 찍다; 종지부를 찍다; 

따라서 평균적으로 같은 값을 가진 항목이 2개 이상일 경우 선택 분류보다 내부 루프를 더 적게 실행하기 때문에 빙고 분류가 더 빠를 것으로 예상할 수 있다.

참고 항목

• 선택 알고리즘

참조

외부 링크

Wikibook 알고리즘 구현에 다음 주제의 페이지가 있음: 선택 정렬

• 애니메이션 정렬 알고리즘: 웨이백 머신에서 선택 정렬(2015년 3월 7일 기록) – 그래픽 시연