Selection Sort

yijin3018·2021년 11월 11일
0
  • 개념 : 현재 선택된 데이터 이후의 정렬 되지 않은 데이터 중에서 가장 작은(혹은 가장 큰) 데이터를 선택해 현재의 데이터와 위치를 교환하는 방식으로 정렬되는 방식.
  • 특징
    • unstable sort
    • 제자리 정렬
  • 시간 복잡도 : O(n2)O(n^2) (최선, 평균, 최악 모두 동일)
  • 공간복잡도 : O(1)O(1)
  • 장점
    • 자료 이동 횟수가 미리 결정됨.
  • 단점
    • 안정성 x
    • 같은 값의 상대적인 위치가 바뀔 수 있다. ex) [2,1,2,1] - 위치가 역전될수도 있음.
arr = [4,2,5,6,1,3]

for i in range(len(arr)-1):
    min_index = i
    for j in range(i+1, len(arr)):
        if arr[j] < arr[min_index]:
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
    print(arr)

#[1, 2, 5, 6, 4, 3]
#[1, 2, 5, 6, 4, 3]
#[1, 2, 3, 6, 4, 5]
#[1, 2, 3, 4, 6, 5]
#[1, 2, 3, 4, 5, 6]
profile
💻 For Computer Science..

0개의 댓글