알고리즘_정렬
1. 버블정렬
처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
nums = [10,2,7,21,0]
print(f'not sorted nums : {nums}')
for i in range(len(nums)-1):
for j in range(len(nums)-1):
if nums[j] > nums[j+1]:
# temp = nums[j]
# nums[j] = nums[j+1]
# nums[j+1] = temp
nums[j], nums[j+1] = nums[j+1], nums[j]
#파이썬 제공 자리바꾸기
print(f'sorting nums : {nums}')
print()
print(f'sorted nums : {nums}')💡list idx를 활용한 자리바꾸는 Tip
nums[idx번호],nums[바꿀 idx 번호] = nums[바꿀 idx 번호], nums[idx번호]
📁python 실습
새 학년이 되어 학급에 20명의 새로운 학생들이 모였다.
학생들을 키 순서로 줄 세워보자
학생들의 키는 random 모듈을 이용해서 170~185사이로 생성한다.
❗실수과정
- sample 사용하려고 하였으나, 범위가 샘플로 가져올 수보다 작아서 error 발생한점
- 얕은 복사로 인해 sorted.bubble 함수 실행 시 원본도 정렬되어버린다는점
#bubble 모듈
def sorted(list):
for i in range(len(copy_list)-1) :
for j in range(len(copy_list)-1) :
if copy_list[j] > copy_list[j+1] :
copy_list[j] , copy_list[j+1] = copy_list[j+1], copy_list[j]
return copy_list#실행파일에서 실행
import random
import bubble
students = random.sample(range(170,186),20)
students = bubble.sorted(students)
print(students)
# ValueError: Sample larger than population or is negative1번의 경우 radint와 for문으로 해결
2번의 경우, 모듈에 deepcopy=True를 넣어줄것
#bubble 모듈
def sorted(list,deepcopy = True):
import copy
if deepcopy:
copy_list = copy.copy(list)
else :
copy_list = list
for i in range(len(copy_list)-1) :
for j in range(len(copy_list)-1) :
if copy_list[j] > copy_list[j+1] :
copy_list[j] , copy_list[j+1] = copy_list[j+1], copy_list[j]
return copy_list
#실행파일에서 실행
import random
student=[]
for i in range(20) :
student.append(random.randint(170,186))
import bubble
student_sorted = bubble.sorted(student,True)
print(f'student_ori : {student}')
print(f'student_sorted : {student_sorted}')
#student_ori : [170, 178, 173, 184, 176, 175, 175, 179, 176, 175, 176, 182, 170, 173, 179, 175, 172, 183, 173, 170]
#student_sorted : [170, 170, 170, 172, 173, 173, 173, 175, 175, 175, 175, 176, 176, 176, 178, 179, 179, 182, 183, 184]
#얕은복사로 인해 원본 데이터까지 정렬
student_sorted = bubble.sorted(student,False)
print(f'student_ori : {student}')
print(f'student_sorted : {student_sorted}')
#student_ori : [170, 170, 170, 172, 173, 173, 173, 175, 175, 175, 175, 176, 176, 176, 178, 179, 179, 182, 183, 184]
#student_sorted : [170, 170, 170, 172, 173, 173, 173, 175, 175, 175, 175, 176, 176, 176, 178, 179, 179, 182, 183, 184]
2. 삽입정렬
정렬되어 있는 자료배열과 비교해서 정렬위치를 찾는다. (나의이해 : 작은수를 temp에 담아놓고 그 자리에 앞자리를 넣은 후 그 앞에 끼워넣기)....?
🫥끄적끄적..
nums = [10,5,2,1,0]일때
뒤에 숫자(5)를 temp에 담아두고 앞(10)과 비교해서
앞(10)이 크다면 뒤의 숫자에 앞 숫자를 넣어주고
-> nums = [10,10,2,1,0]
앞에 temp를 넣어준다
-> nums = [5,10,2,1,0]
끝까지 반복
python으로 차근차근 진행해보기
nums = [10,5,2,1,0]
for i1 in range(1,len(nums)) :
i0 = i1-1
temp = nums[i1]
while nums[i0] > temp and i0 >= 0 :
#i1에 nums[i2]값 넣기
nums[i0+1] = nums[i0]
i0 -= 1
nums[i0+1] = temp
print(f'nums : {nums}')1. 앞과 비교해야하기 때문에 idx는 1번부터 시작
즉 1번부터 idx끝까지 비교for i1 in range(1,len(nums)) :2. 비교할 앞자리세팅 즉 i0는 i1의 앞숫자 idx번호
처음 시작할경우 nums[i1] = 5 / nums[i0] = 10i0 = i1-13. 뒷자리(5) temp에 담아놓기
temp = nums[i1] #54. 앞 숫자가 뒷 숫자보다 클 때 정렬
while nums[i0] > temp and i0 >= 0 :5. i1자리에 i2넣기
nums[i0+1] = nums[i0] #[10,10,2,1,0]6. 무한반복막기 + while문의 and i2 >= 0
i0 -= 17. 앞자리까지 모두 비교가 끝난 후에 temp값 자리이동
nums[i0+1] = temp
음..🫥
유튜브 방식으로 버블정렬과 반대로 하는게 조금 더 쉽다.
버블정렬은 앞에서 뒤를 비교해서 큰 수를 밀어내는거라면,
삽입정렬은 뒤에서 앞과 비교해서 작은수를 앞으로 보내버린다.
https://youtu.be/LFlRzDhgIOw?si=dTaeRxBFtqQb3Rbs
nums = [10,5,2,1,0]
for i in range(1,len(nums)) :
for j in range(i,0,-1) :
if nums[j-1] >nums[j] :
nums[j - 1],nums[j] = nums[j],nums[j-1]
print(f'nums : {nums}')📁python 실습
❗강의 이해내용이 아닌 유튜브 이해내용을 토대로 풀이하여 올바른 답이 아닐 수 있음
1부터 1000까지 난수 100개를 생성하고, 다음요구사항을 만족하는 모듈을 만들어보자
- 생성된 난수들을 오름차순 또는 내림차순으로 정렬하는 알고리즘 구현
- 생성된 난수중 최솟값, 최댓값을 반환하는 함수구현
#insert 모듈
def sorted(list,asc = True, deepcopy = True) :
if deepcopy :
import copy
sort_list = copy.copy(list)
else :
sort_list = list
for i in range(1,len(list)) :
for j in range(i,0,-1) :
if asc :
if sort_list[j] < sort_list[j-1] :
sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]
else :
if sort_list[j] > sort_list[j-1] :
sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]
return sort_list
def search_max(list,max = True) :
if max :
result = sorted(list)[0]
else :
result = sorted(list)[len(list)-1]
return result#실행파일
import random
rnums = random.sample(range(1,1001),100)
print(f'rnums : {rnums}')
import insert
acs = insert.sorted(rnums)
desc = insert.sorted(rnums,False)
print(f'acs sorted rnums : {acs}')
print(f'desc sorted rnums : {desc}')
max = insert.search_max(rnums)
min = insert.search_max(rnums,False)
print(f'rnums max : {max}')
print(f'rnums min : {min}')3. 선택정렬
주어진 리스트 중에 최소값을 찾아
그 값을 맨앞에 위치한 값과 교체하는 방식으로 정렬
nums = [4,2,5,1,3]
for i in range(len(nums)-1):
mid_idx = i
for j in range(i+1,len(nums)):
if nums[j] < nums[mid_idx] :
mid_idx = j
# temp = nums[i]
# nums[i] = nums[mid_idx]
# nums[mid_idx] = temp
nums[i] , nums[mid_idx] = nums[mid_idx], nums[i]
print(f'nums : {nums}')📁python 실습
선택정렬 알고리즘을 이용해서
학생 20명의 시험점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자.
시험점수는 50부터 100까지로 한다.
#select모듈
def sorted (list, asc=True, deepcopy=True) :
if deepcopy :
import copy
sorted_list = copy.copy(list)
else :
sorted_list = list
for i in range(len(sorted_list)-1) :
temp_idx = i
for j in range(i+1, len(sorted_list)):
if asc :
if sorted_list[j] < sorted_list[temp_idx] :
temp_idx = j
else :
if sorted_list[j] > sorted_list[temp_idx] :
temp_idx = j
sorted_list[i] , sorted_list[temp_idx] = sorted_list[temp_idx], sorted_list[i]
return sorted_list
#실행파일
import random
scores = random.sample(range(50,101),20)
print(f'scores : {scores}')
print(f'scores length : {len(scores)}')
import select
acs = select.sorted(scores,True)
desc = select.sorted(scores,False)
print(f'result(ASC) : {acs}')
print(f'result(DESC) : {desc}')제로베이스 데이터취업스쿨
Daily Study Note
Study Log