Python 선택 정렬

이 포스팅에서는 프로그램 예제와 함께 Python 선택 정렬 알고리즘에 대해 알아봅니다.

선택 정렬은 가장 쉬운 정렬 알고리즘 중 하나입니다. 선택 정렬에서 정렬되지 않은 배열을 정렬하려면 배열에서 최소값을 찾아 이를 정렬되지 않은 배열의 첫 번째 요소와 교체하면 됩니다. 각 교환 후에 배열의 시작 인덱스를 1씩 늘립니다.

오름차순으로 정렬하기 위한 것입니다. 내림차순으로 정렬하려면 최소값 대신 최대값을 찾아 정렬되지 않은 배열의 첫 번째 요소로 바꿉니다.

Python 선택 정렬

예
정렬되지 않은 배열이 있습니다.

[4,8,19,2,28,21]

1 단계:

Python 선택 정렬

2 단계:

Python 선택 정렬

3단계:

Python 선택 정렬

4단계:

Python 선택 정렬

5단계:

Python 선택 정렬

6단계:

Python 선택 정렬

연산
n개의 요소로 구성된 배열이 있는 경우.

1단계:- MIN = 0으로 설정

2단계:- 배열에서 최소 요소 찾기

존재하는 경우 MIN에서 요소로 교체합니다.

3단계:-  MIN을 1씩 늘립니다.

4단계: -  배열이 정렬될 때까지 2단계로 이동합니다(n-1회).

시간 복잡도
최선의 경우 = O(n) 2
평균 사례 = O(n) 2
최악의 경우 = O(n) 2
참고: 더 큰 배열의 경우 선택 정렬을 사용하지 않습니다.

Python 선택 정렬 프로그램

다음은 Python에서 선택 정렬을 구현한 것입니다.

arr =[4,8,19,2,28,21]

 

min = 0    #set min = 0

n = len(arr)

 

while(min <= n-1):

  s_i = min

  while(s_i <= n-1):      #finding minimum

    if (arr[s_i] < arr[min]):

      arr[min],arr[s_i] = arr[s_i],arr[min]   #swapping element at start index with minimum

    s_i = s_i+1

 

  min = min+1

 

for element in arr:

   print element

산출

2 4 8 19 21 28