AlgorithmSort

selection sort

algorithm, python, selection sort
  • selection sort(선택 정렬)
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • O(n^2)
  • simple sort
  • 제자리 정렬 알고리즘의 하나
  • 입력 리스트(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
    1. 주어진 배열 중에서 최솟값을 찾는다.
    2. 그 값을 맨 앞에 위치한 값과 교체한다.(두 수를 비교하여 pass도 가능)
    3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
    4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      import random

      def selection_sort(li):
          
          n = len(li)
          
          for i in range(0, n-1):
              min_idx = i
              
              for j in range(i+1, n):
                  if li[j] < li[min_idx]:
                      min_idx = j
                     
              # min_idx --> 맨 앞자리를 제외하고 최소값이 위치한 곳의 인덱스
              li[i], li[min_idx] = li[min_idx], li[i]
              

      if __name__ == "__main__":
          
          while True:
              num_data = int(input('데이터 개수(종료:0):'))
              if not num_data:
                  break
                  
              data = [random.randint(1,100) for _ in range(num_data)]
              print(data)
              
              selection_sort(data)
              print(data)
Share