선택 정렬: 알고리즘 설명 Python 코드 예제
사라 첸
선택 정렬이란 무엇입니까?
선택 정렬 임의의 항목 목록을 오름차순으로 정렬하는 데 사용되는 비교 정렬 알고리즘입니다. 비교에는 많은 추가 공간이 필요하지 않습니다. 시간 변수에 대해 하나의 추가 메모리 공간만 필요합니다.
이것은 그 자리에서 정렬. 선택 정렬의 시간 복잡도는 O(n2) 여기서 n은 목록의 총 항목 수입니다. 시간 복잡도는 목록을 정렬하는 데 필요한 반복 횟수를 측정합니다. 목록은 두 개의 파티션으로 나뉩니다. 첫 번째 목록에는 정렬된 항목이 포함되고 두 번째 목록에는 정렬되지 않은 항목이 포함됩니다.
기본적으로 정렬된 목록은 비어 있고 정렬되지 않은 목록에는 모든 요소가 포함되어 있습니다. 그런 다음 정렬되지 않은 목록에서 최소값을 검색한 다음 정렬된 목록에 배치합니다. 모든 값이 비교되고 정렬될 때까지 이 프로세스가 반복됩니다.
선택 정렬은 어떻게 작동하나요?
정렬되지 않은 파티션의 첫 번째 항목을 오른쪽의 모든 값과 비교하여 최소값인지 확인합니다. 최소값이 아닌 경우 위치는 최소값으로 교체됩니다.
예시
- 예를 들어, 최소값의 인덱스가 3인 경우 인덱스 3을 가진 요소의 값은 인덱스 0에 배치되고 인덱스 0에 있던 값은 인덱스 3에 배치됩니다. 정렬되지 않은 파티션의 첫 번째 요소가 최소값이면 위치를 반환합니다.
- 최소값으로 결정된 요소는 정렬된 목록인 왼쪽 파티션으로 이동됩니다.
- 이제 분할된 쪽에는 하나의 요소가 있고 분할되지 않은 쪽에는 (n – 1)개의 요소가 있습니다. 여기서 n은 목록의 총 요소 수입니다. 이 프로세스는 모든 항목이 값에 따라 비교되고 정렬될 때까지 계속해서 반복됩니다.
문제 정의
무작위 순서로 정렬된 요소의 목록은 오름차순으로 정렬해야 합니다. 다음 목록을 예로 들어 보겠습니다.
[21,6,9,33,3]
위 목록을 정렬하면 다음 결과가 생성됩니다.
[3,6,9,21,33]
솔루션(알고리즘)
단계 1) 배열의 전체 크기인 n 값을 가져옵니다.
단계 2) 목록을 정렬된 섹션과 정렬되지 않은 섹션으로 분할합니다. 정렬된 섹션은 처음에는 비어 있지만 정렬되지 않은 섹션에는 전체 목록이 포함되어 있습니다.
단계 3) 분할되지 않은 섹션에서 최소값을 선택하여 정렬된 섹션에 배치합니다.
단계 4) 목록의 모든 요소가 정렬될 때까지 이 과정을 (n – 1)번 반복합니다.
시각적 표현
5개의 요소 목록이 주어졌을 때, 다음 이미지는 선택 정렬 알고리즘이 정렬할 때 값을 반복하는 방식을 보여줍니다.
다음 이미지는 정렬되지 않은 목록을 보여줍니다.
단계 1)
첫 번째 값인 21을 나머지 값과 비교하여 최소값인지 확인합니다.
3이 최소값이므로 21과 3의 위치가 바뀌었습니다. 녹색 배경의 값은 목록의 정렬된 파티션을 나타냅니다.
단계 2)
정렬되지 않은 파티션의 첫 번째 요소인 값 6을 나머지 값과 비교하여 더 낮은 값이 존재하는지 확인합니다.
값 6은 최소값이므로 위치를 유지합니다.
단계 3)
정렬되지 않은 목록의 첫 번째 요소인 9 값은 나머지 값과 비교되어 최소값인지 확인합니다.
값 9는 최소값이므로 정렬된 파티션에서 해당 위치를 유지합니다.
단계 4)
값 33은 나머지 값과 비교됩니다.
값 21은 33보다 낮으므로 위치가 바뀌어 위의 새 목록이 생성됩니다.
단계 5)
분할되지 않은 목록에는 하나의 값만 남습니다. 따라서 이미 정렬되어 있습니다.
최종 목록은 위 이미지와 같습니다.
다음을 사용한 선택 정렬 프로그램 Python 3
다음 코드는 다음을 사용하여 선택 정렬 구현을 보여줍니다. Python 3
def selectionSort( itemsList ):
n = len( itemsList )
for i in range( n - 1 ):
minValueIndex = i
for j in range( i + 1, n ):
if itemsList[j] < itemsList[minValueIndex] :
minValueIndex = j
if minValueIndex != i :
temp = itemsList[i]
itemsList[i] = itemsList[minValueIndex]
itemsList[minValueIndex] = temp
return itemsList
el = [21,6,9,33,3]
print(selectionSort(el))
위 코드를 실행하면 다음과 같은 결과가 생성됩니다.
[3, 6, 9, 21, 33]
코드 설명
코드에 대한 설명은 다음과 같습니다
코드 설명은 다음과 같습니다.
- SelectionSort라는 함수를 정의합니다.
- 목록의 총 요소 수를 가져옵니다. 값을 비교할 때 수행할 패스 수를 결정하려면 이 정보가 필요합니다.
- 외부 루프. 루프를 사용하여 목록의 값을 반복합니다. 반복 횟수는 (n – 1)입니다. n의 값은 5이므로 (5 – 1)은 4를 제공합니다. 이는 외부 반복이 4번 수행된다는 의미입니다. 각 반복에서 변수 i의 값은 변수 minValueIndex에 할당됩니다.
- 내부 루프. 루프를 사용하여 가장 왼쪽 값을 오른쪽에 있는 다른 값과 비교합니다. 그러나 j의 값은 인덱스 0에서 시작하지 않습니다. (i + 1)에서 시작합니다. 이는 이미 정렬된 값을 제외하므로 아직 정렬되지 않은 항목에 중점을 둡니다.
- 정렬되지 않은 목록에서 최소값을 찾아 적절한 위치에 배치합니다.
- 스와핑 조건이 true일 때 minValueIndex 값을 업데이트합니다.
- minValueIndex와 i 인덱스 번호의 값을 비교하여 같지 않은지 확인합니다.
- 가장 왼쪽 값은 시간 변수에 저장됩니다.
- 오른쪽에서 낮은 값이 첫 번째 위치를 차지합니다.
- 임시값에 저장되어 있던 값은 이전에 최소값에 의해 유지되었던 위치에 저장됩니다.
- 정렬된 목록을 함수 결과로 반환합니다.
- 난수가 포함된 el 목록을 생성합니다.
- el을 매개변수로 전달하여 선택 Sort 함수를 호출한 후 정렬된 목록을 인쇄합니다.
선택 정렬의 시간 복잡도
정렬 복잡도는 목록을 정렬하는 데 걸리는 실행 횟수를 표현하는 데 사용됩니다. 구현에는 두 개의 루프가 있습니다.
목록에서 값을 하나씩 선택하는 외부 루프는 n 번 실행됩니다. 여기서 n은 목록의 총 값 수입니다.
외부 루프의 값을 나머지 값과 비교하는 내부 루프도 n번 실행됩니다. 여기서 n은 목록에 있는 요소의 총 개수입니다.
따라서 실행횟수는 (n*n)이며, 이는 O(n)으로도 표현할 수 있다.2).
선택 정렬에는 복잡도에 따라 세 가지 범주가 있습니다.
- 최악의 경우 – 제공된 목록이 내림차순으로 표시됩니다. 알고리즘은 [Big-O] O(n)으로 표현되는 최대 실행 횟수를 수행합니다.2)
- 최고의 사례 – 제공된 목록이 이미 정렬되어 있는 경우 발생합니다. 알고리즘은 [Big-Omega] ?(n으로 표현되는 최소 실행 횟수를 수행합니다.2)
- 평균 사례 – 이것은 목록이 무작위 순서일 때 발생합니다. 평균 복잡도는 [Big-theta] ?(n으로 표현됩니다.2)
선택 정렬은 값을 바꾸는 데 사용되는 하나의 시간 변수가 필요하므로 O(1)의 공간 복잡도를 갖습니다.
선택 정렬은 언제 사용하나요?
선택 정렬은 다음과 같은 경우에 가장 적합합니다.
- 작은 항목 목록을 오름차순으로 정렬해야 합니다.
- 가치 교환 비용이 미미한 경우
- 또한 목록의 모든 값이 확인되었는지 확인해야 하는 경우에도 사용됩니다.
선택 정렬의 장점
선택 정렬의 장점은 다음과 같습니다.
- 작은 목록에서는 매우 잘 수행됩니다.
- 내부 알고리즘입니다. 정렬에 많은 공간이 필요하지 않습니다. 시간 변수를 보유하는 데는 하나의 추가 공간만 필요합니다.
- 이미 정렬된 항목에 대해 잘 수행됩니다.
선택 정렬의 단점
선택 정렬의 단점은 다음과 같습니다.
- 거대한 목록을 작업할 때는 성능이 좋지 않습니다.
- 정렬 중 반복 횟수는 n제곱입니다. 여기서 n은 목록의 총 요소 수입니다.
- 퀵정렬 등의 다른 알고리즘은 선택 정렬에 비해 더 나은 성능을 보입니다.
요약
- 선택 정렬은 무작위 목록을 정렬된 목록으로 정렬하는 데 사용되는 제자리 비교 알고리즘입니다. 시간 복잡도는 O(n2)
- 목록은 정렬된 섹션과 정렬되지 않은 섹션의 두 섹션으로 나뉩니다. 정렬되지 않은 섹션에서 최소값을 선택하여 정렬된 섹션에 배치합니다.
- 모든 항목이 정렬될 때까지 이 작업이 반복됩니다.
- 의사 코드 구현 Python 3에서는 두 개의 for 루프와 if 문을 사용하여 스와핑이 필요한지 확인합니다.
- 시간 복잡도는 목록을 정렬하는 데 필요한 단계 수를 측정합니다.
- 최악의 경우 시간 복잡도는 목록이 내림차순일 때 발생합니다. [Big-O] O(n2)
- 최상의 경우 시간 복잡도는 목록이 이미 오름차순일 때 발생합니다. 이는 [Big-Omega] ?(n의 시간 복잡도를 갖습니다.2)
- 평균 케이스 시간 복잡도는 목록이 무작위 순서로 정렬된 경우 발생합니다. [Big-theta] ?(n의 시간 복잡도를 갖습니다.2)
- 선택 정렬은 정렬할 항목 목록이 적고, 값 교환 비용이 중요하지 않으며, 모든 값을 확인해야 하는 경우에 가장 적합합니다.
- 거대한 목록에서는 선택 정렬이 제대로 수행되지 않습니다.
- 퀵정렬과 같은 다른 정렬 알고리즘은 선택 정렬보다 성능이 더 좋습니다.
