def bubbleSort(iter):
for i in range(len(iter)-1): # 끝까지 안돌고 마지막 전 까지만
for j in range(len(iter)-1):
if iter[j] > iter[j+1]:
iter[j], iter[j+1] = iter[j+1], iter[j]
return iter
- 인자로 받은 배열의 첫번째 원소를 minum value로 설정
- 두번째 원소부터 배열의 끝 까지 반복문을 순회하며 minum value와 크기 비교
- 만약 minus value보다 원소의 크기가 작다면 minum value를 해당 원소로 교체
- 배열의 끝까지 순회한 뒤 첫번째 원소와 minum value가 다르다면 두 원소를 서로 교체
- 두번째 원소부터 배열의 마지막 원소 전 까지 1,2,3,4 과정 반복
def selectionSort(iter):
for i in range(len(iter) - 1):
idx_min = i
j = i + 1
while j < len(iter):
if(iter[j] < iter[idx_min]):
idx_min = j
j = j + 1
if idx_min is not i:
iter[idx_min], iter[i] = iter[i], iter[idx_min]
return iter
- 배열의 첫번째 원소를 정렬된 배열에 넣음
- 배열의 두번째 원소를 정렬된 배열의 끝에 있는 원소 ( 현재는 정렬된 배열의 길이는 1 ) 와 비교
- 만약 두번째 원소가 크다면 그대로 두번째 원소를 정렬된 배열의 끝에 삽입
- 만약 두번째 원소가 작다면 정렬된 배열의 첫번째 자리에 삽입
- 세번째 원소도 같은 방법으로 정렬된 배열과 비교하여 자신이 있어야할 위치에 삽입
def insertion_sort(iter):
for idx, valueToInsert in enumerate(iter):
p = idx # 원소가 삽입 되어야할 위치
while p > 0 and iter[p-1] > valueToInsert:
iter[p - 1], iter[p] = iter[p], iter[p-1] # 배열을 뒤로 밀어(?) 느낌을 이렇게
p = p - 1
return iter
- 배열을 반절로 재귀적으로 분리 ( 분리된 각 원소가 1개 남을 떄 까지 )
- 재귀적인 함수 호출로 인해 쌓인 스택 순서대로 왼쪽 배열과 오른쪽 배열의 값을 비교하면서 합침
def mergeSort(iter):
print("Splitting ",iter)
if len(iter)>1:
mid = len(iter)//2 # //는 몫
lefthalf = iter[:mid]
righthalf = iter[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0 # leftHalf index
j=0 # rightHalf index
k=0 # iter index
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
iter[k]=lefthalf[i]
i=i+1
else:
iter[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf): # 왼쪽 배열만 남으면 그대로 iter에 붙여줘
iter[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf): # 오른쪽 배열만 남으면 그대로 iter에 붙여줘
iter[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",iter)
# 반절 나눌 때
mid = len(list) // 2
leftHalf = list[:mid]
rightHalf = list[mid:]
# reculsive
def mergeSort(iter):
...
leftHalf = iter[:mid]
print('leftHalf id', id(leftHalf))
mergeSort(leftHalf)
def mergeSort(iter): #mergetSort(leftHalf)에 의해 호출된 함수
print('iterId', id(iter))
...
lefthalf = iter[:mid]
mergeSort(leftHalf)
객체 참조에 의해 두 프린트문 에서 출력된 id 값은 같다. 따라서 안에서 호출된 재귀함수로 값을 수정하면 외부 함수의 값이 변경된다!