선택 정렬 (selection sort)
이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
잔재미코딩 소식 공유
좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을
오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
● 잔재미코딩 유투브 오픈
[구독해보기]
5. 대표적인 정렬3: 선택 정렬 (selection sort)¶
1. 선택 정렬 (selection sort) 란?¶
- 다음과 같은 순서를 반복하며 정렬하는 알고리즘
- 주어진 데이터 중, 최소값을 찾음
- 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
- 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함
직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting¶
2. 어떻게 코드로 만들까?¶
- 데이터가 두 개 일때
- 예: dataList = [9, 1]
- data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_ list[1] 값을 교환
- 예: dataList = [9, 1]
- 데이터가 세 개 일때
- 예: data_list = [9, 1, 7]
- 처음 한번 실행하면, 1, 9, 7 이 됨
- 두 번째 실행하면, 1, 7, 9 가 됨
- 예: data_list = [9, 1, 7]
- 데이터가 네 개 일때
- 예: data_list = [9, 3, 2, 1]
- 처음 한번 실행하면, 1, 3, 2, 9 가 됨
- 두 번째 실행하면, 1, 2, 3, 9 가 됨
- 세 번째 실행하면, 변화 없음
- 예: data_list = [9, 3, 2, 1]
프로그래밍 연습
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
* 데이터가 두 개 일때
- 예: 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 가 됨
- 예: data_list = [9, 1, 7]
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
프로그래밍 연습
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
- 데이터가 네 개 일때
- 예: data_list = [9, 3, 2, 1]
- 처음 한번 실행하면, 1, 3, 2, 9 가 됨
- 두 번째 실행하면, 1, 2, 3, 9 가 됨
- 세 번째 실행하면, 변화 없음
- 예: data_list = [9, 3, 2, 1]
3. 알고리즘 구현¶
- for stand in range(len(data_list) - 1) 로 반복
- lowest = stand 로 놓고,
- for num in range(stand, len(data_list)) stand 이후부터 반복
- 내부 반복문 안에서 data_list[lowest] > data_list[num] 이면,
- lowest = num
- 내부 반복문 안에서 data_list[lowest] > data_list[num] 이면,
- 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 }$
프로그래밍 연습
지금 설명한 선택 정렬을 지금 다시 스스로 작성해보세요
지금 설명한 선택 정렬을 지금 다시 스스로 작성해보세요