이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
5. 선택 정렬 (selection sort)¶
- 다음과 같이 리스트에 숫자가 낮은 순으로 위치를 바꾸는 것
- 파이썬에는 sorted() 함수가 있음, 우리는 정렬을 하는 다양한 알고리즘을 익히면서, 잘 작성된 알고리즘을 이해하고, 모사하며 연습한다!
In [ ]:
data_list
In [ ]:
sorted(data_list)
프로그래밍 연습
1 ~ 100까지 랜덤한 값을 2개 가지는 리스트 변수를 만들고
항상 인덱스 0번부터 낮은 값이 넣어질 수 있도록 바꿔보세요
1 ~ 100까지 랜덤한 값을 2개 가지는 리스트 변수를 만들고
항상 인덱스 0번부터 낮은 값이 넣어질 수 있도록 바꿔보세요
# 데이터 준비: data_list 10개 만들기 import random data_list = random.sample(range(100), 10)
In [ ]:
import random
data_list = random.sample(range(100), 2)
In [ ]:
def sorting(data):
if data[0] > data[1]:
data[1], data[0] = data[0], data[1]
return data
sorting(data_list)
프로그래밍 연습
1 ~ 100까지 랜덤한 값을 3개 가지는 리스트 변수를 만들고
항상 인덱스 0번부터 낮은 값이 넣어질 수 있도록 바꿔보세요
1 ~ 100까지 랜덤한 값을 3개 가지는 리스트 변수를 만들고
항상 인덱스 0번부터 낮은 값이 넣어질 수 있도록 바꿔보세요
In [ ]:
import random
data_list = random.sample(range(100), 3)
In [ ]:
def sorting(data):
if data[0] > data[1]:
data[1], data[0] = data[1], data[0]
if data[1] > data[2]:
data[1], data[2] = data[2], data[1]
return data
sorting(data_list)
프로그래밍 연습
1 ~ 100까지 랜덤한 값을 4개 가지는 리스트 변수를 만들고
항상 인덱스 0번부터 낮은 값이 넣어질 수 있도록 바꿔보세요
1 ~ 100까지 랜덤한 값을 4개 가지는 리스트 변수를 만들고
항상 인덱스 0번부터 낮은 값이 넣어질 수 있도록 바꿔보세요
In [ ]:
def sorting(data_list):
for index in range(len(data_list) - 1):
if data_list[index] > data_list[index + 1]:
data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]
return data_list
In [ ]:
print(data_list)
sorting(data_list)
selection sort 알고리즘 기본 원리¶
- 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting
- 맨 처음 값부터 비교해서 리스트 중 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 리스트를 동일한 방법으로 진행한다.
In [ ]:
import random
data_list = random.sample(range(100), 10)
In [ ]:
def selection_sort(data_list):
for index in range(len(data_list) - 1):
lowest = index
for index2 in range(index + 1, len(data_list)):
if data_list[lowest] > data_list[index2]:
lowest = index2
data_list[index], data_list[lowest] = data_list[lowest], data_list[index]
return data_list
In [ ]:
selection_sort(data_list)
어떻게 코드로 만들까?¶
- 데이터가 두 개 일때
- 예: dataList = [9, 1]
- data_list[0] > data_list[1] 이므로 datalist[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]
프로그래밍 연습
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
* 데이터가 두 개 일때 - 예: dataList = [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>
- 예: data_list = [9, 1, 7]
프로그래밍 연습
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
데이터가 두개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
- 데이터가 네 개 일때
- 예: data_list = [9, 3, 2, 1]
- 처음 한번 실행하면, 1, 3, 2, 9 가 됨
- 두 번째 실행하면, 1, 2, 3, 9 가 됨
- 세 번째 실행하면, 변화 없음 </pre>
- 예: data_list = [9, 3, 2, 1]
In [ ]:
# 데이터 준비: data_list 10개 만들기
import random
data_list = random.sample(range(100), 10)
In [ ]:
data_list
In [ ]:
def selection_sort(data_list):
for index in range(len(data_list) - 1):
lowest = data_list[index]
for index2 in range(index, len(data_list)):
print (index2)
In [ ]:
def selection_sort(data_list):
for index in range(len(data_list) - 1):
lowest = index
for index2 in range(index, len(data_list)):
if data_list[lowest] > data_list[index2]:
lowest = index2
data_list[index], data_list[lowest] = data_list[lowest], data_list[index]
return data_list
In [ ]:
selection_sort(data_list)
In [ ]:
def selection_sort(data_list):
for index in range(len(data_list) - 1):
알고리즘 생각해보기¶
- 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)
알고리즘 분석¶
- 반복문이 두 개 O($n^2$)
- 실제로 상세하게 계산하면, $\frac { n * (n - 1)}{ 2 }$
프로그래밍 연습
지금 설명한 선택 정렬을 지금 다시 스스로 작성해보세요
프로그래밍 근육을 키우는 방법
지금 설명한 선택 정렬을 지금 다시 스스로 작성해보세요
프로그래밍 근육을 키우는 방법