Selection Sort(선택정렬)

• 정렬 알고리즘은 대표적으로 네가지가 있다.
  • 선택정렬
  • 버블정렬
  • 삽입정렬
  • 퀵정렬
• Selection sort
  • for loop을 두번 돈다. Innerloop의 요소는 Outerloop의 요소 후에 있는 리스트의 모든 요소이다. 리스트의 길이가 n일때 인덱스 0는 인덱스 1, 인덱스 2, ... 인덱스 n까지 비교하고 인덱스 1은 인덱스 2, 인덱스 3,...인덱스 n까지 비교하는 것. 따라서 비교하는 총 횟수는 (n-1) + (n-2) + (n-3) .... 2 + 1 = n(n-1)/2. 시간복잡도는 Big O의 n^2.
  • It has O(n^2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.
  • 비교 후 값이 더 큰 요소가 후순위일 경우 인덱스를 교체해준다.
  • Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited (Auxiliary memory (also referred to as secondary storage) is the non-volatile memory lowest-cost, highest-capacity, and slowest-access storage in a computer system).

선택정렬을 구현해보자

def selectionSort(nums):

  if len(nums)>1:
    for i in range(0, len(nums)):
      for j in range(i+1, len(nums)):
        if nums[i] > nums[j]:
          smallest = nums[j]
          bigger   = nums[i]
          nums[i]  = smallest
          nums[j]  = bigger

  return nums