선택 정렬 알고리즘

선택 정렬이란 무엇입니까?

선택 정렬 알고리즘은 배열을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나눕니다. 처음에는 정렬된 부분은 비어 있고 정렬되지 않은 부분에는 모든 요소가 포함되어 있습니다. 알고리즘은 정렬되지 않은 부분에서 가장 작은(또는 정렬 순서에 따라 가장 큰) 요소를 찾아 이를 정렬되지 않은 부분의 첫 번째 요소와 바꾸는 방식으로 작동합니다. 이 프로세스는 전체 배열이 정렬될 때까지 계속됩니다.

알고리즘 단계

1. 배열의 첫 번째 요소부터 시작하여 가장 작은 요소라고 가정합니다.
2. 이 요소를 배열의 다른 요소와 비교하세요.
3. 더 작은 요소를 찾으면 첫 번째 요소로 바꾸세요.
4. 배열의 다음 요소로 이동하고 정렬되지 않은 나머지 요소에 대해 프로세스를 반복합니다.
5. 전체 배열이 정렬될 때까지 이 과정을 계속합니다.

#Suppose we have the following array:

arr = [64, 25, 12, 22, 11]

패스 1:

• 인덱스 0과 배열의 나머지 부분 사이의 가장 작은 요소는 11입니다.
• 64를 11로 바꿉니다.

첫 번째 패스 이후의 배열: [11, 25, 12, 22, 64]

패스 2:

• 이제 인덱스 1부터 시작하는 하위 배열에 초점을 맞춥니다. 25, 12, 22, 64 사이의 가장 작은 요소는 12입니다.
• 25를 12로 바꿉니다.

두 번째 패스 이후의 배열: [11, 12, 25, 22, 64]

패스 3:

• 25, 22, 64 사이의 가장 작은 요소는 22입니다.
• 25를 22로 교환합니다.

세 번째 패스 이후의 배열: [11, 12, 22, 25, 64]

패스 4:

• 이제 하위 배열에는 25, 64가 포함됩니다. 이미 순서가 지정되어 있으므로 스왑이 필요하지 않습니다.

최종 정렬 배열: [11, 12, 22, 25, 64]

def selection_sort(arr):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Find the minimum element in the remaining unsorted part
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

정렬된 배열: [11, 12, 22, 25, 64]

선택 정렬의 시간 복잡도:

• 최상의 경우: O(n²)

• 평균 사례: O(n²)

• 최악의 경우: O(n²)

선택 정렬은 작은 데이터세트에서는 잘 작동하지만 시간 복잡도가 O(n²)이므로 대규모 배열에는 적합하지 않습니다. 그러나 선택 정렬이 제자리에 있으므로(추가 메모리가 필요하지 않음) 구현하기 쉽고 메모리가 문제가 되는 경우 유용할 수 있습니다.

장점과 단점

장점:

• 이해와 구현이 간단합니다.

• 작은 목록에서 좋은 성능을 발휘합니다.

• 배열을 제자리에 정렬해주기 때문에 추가 메모리가 필요하지 않습니다.

단점:

• O(n²) 시간 복잡도로 인해 대규모 데이터 세트에는 비효율적입니다.

• 안정적인 정렬 알고리즘이 아니므로 동일한 요소가 서로 상대적인 순서를 유지하지 못할 수 있습니다.

위 내용은 선택 정렬 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!