선택 정렬 (selection sort)

이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
잔재미코딩 소식 공유
좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 사이트와, 다음 두 채널도 오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
●  잔재미코딩 뉴스레터 오픈 [구독해보기]
●  잔재미코딩 유투브 오픈 [구독해보기]

5. 대표적인 정렬3: 선택 정렬 (selection sort)

1. 선택 정렬 (selection sort) 란?

  • 다음과 같은 순서를 반복하며 정렬하는 알고리즘
    1. 주어진 데이터 중, 최소값을 찾음
    2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
    3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

출처: https://en.wikipedia.org/wiki/Selection_sort

2. 어떻게 코드로 만들까?

  • 데이터가 두 개 일때
    • 예: dataList = [9, 1]
      • data_list[0] > data_list[1] 이므로 datalist[0] 값과 data list[1] 값을 교환
  • 데이터가 세 개 일때
    • 예: data_list = [9, 1, 7]
      • 처음 한번 실행하면, 1, 9, 7 이 됨
      • 두 번째 실행하면, 1, 7, 9 가 됨
  • 데이터가 네 개 일때
    • 예: data_list = [9, 3, 2, 1]
      • 처음 한번 실행하면, 1, 3, 2, 9 가 됨
      • 두 번째 실행하면, 1, 2, 3, 9 가 됨
      • 세 번째 실행하면, 변화 없음

프로그래밍 연습
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법

* 데이터가 두 개 일때
  - 예: data_list = [9, 1]
    - data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_ list[1] 값을 교환
프로그래밍 연습
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
  • 데이터가 세 개 일때
    • 예: data_list = [9, 1, 7]
      • 처음 한번 실행하면, 1, 9, 7 이 됨
      • 두 번째 실행하면, 1, 7, 9 가 됨 </pre>
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
프로그래밍 연습
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
  • 데이터가 네 개 일때
    • 예: data_list = [9, 3, 2, 1]
      • 처음 한번 실행하면, 1, 3, 2, 9 가 됨
      • 두 번째 실행하면, 1, 2, 3, 9 가 됨
      • 세 번째 실행하면, 변화 없음 </pre>

3. 알고리즘 구현

  1. for stand in range(len(data_list) - 1) 로 반복
  2. lowest = stand 로 놓고,
  3. for num in range(stand, len(data_list)) stand 이후부터 반복
    • 내부 반복문 안에서 data_list[lowest] > data_list[num] 이면,
      • lowest = num
  4. data_list[num], data_list[lowest] = data_list[lowest], data_list[num]
In [ ]:
def selection_sort(data_list):    
    for stand in range(len(data_list) - 1):
        print (stand)
        lowest = stand
        for num in range(stand, len(data_list)):
            if data_list[lowest] > data_list[num]:
                lowest = num
        data_list[stand], data_list[lowest] = data_list[lowest], data_list[stand]
        print (data_list)
    return data_list
In [ ]:
# 데이터 준비: data_list 10개 만들기
import random 
data_list = random.sample(range(100), 10)
In [ ]:
# 테스트 해보기
selection_sort(data_list)
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

4. 알고리즘 분석

  • 반복문이 두 개 O($n^2$)
    • 실제로 상세하게 계산하면, $\frac { n * (n - 1)}{ 2 }$
프로그래밍 연습
지금 설명한 선택 정렬을 지금 다시 스스로 작성해보세요