6주차, 파이썬으로 sort 구현

def insertion_sort(some_list):

    for i in range(len(some_list)):

        key = some_list[i]

        j = i - 1

        while j>=0 and some_list[j] > key:

            some_list[j + 1] = some_list[j]

            j = j - 1

        some_list[j + 1] = key

some_list = [11, 7, 3, 25, 5, 1]

insertion_sort(some_list)

print(some_list)

// 1, 3, 5, 7, 11, 25

 

들어온 리스트의 수만큼 for문이 돈다. 첫 for문에선 j가 -1이므로 while문이 발동하지 않는다.

2번째 for문에선 j가 0과 같고, 리스트의[0]번째 요소인 11이 key값인 7보다 크니 whilea문이

발동한다. 리스트[1]번째 요소인 7에 [0]번째 요소인 11을 집어넣는다.

그리고 j는 -1이 되니 while문이 끝난다.

 

그리고 j+1 인 0에 key, 리스트[1]이었던 7을 집어넣는다.

지금 상태 : [7, 11, 3, 25, 5, 1]

 

다음 for문에서도(i=2, j=1) 리스트[j]의 값이 리스트[i]인 key값보다 크니 while문이 돌아간다.

리스트 2번째에 리스트 첫번째 값이 들어가고 j를 1 뺀다

 

그 후 key값과 현재 j인 0번째 값을 비교해보니 j의 값이 크니 j보다 1 큰 첫번째에 0번째 값을 넣어준다.

그리고 while문이 끝나고 0번째에 키값을 넣어준다.

 

이걸 반복하면 정렬된 리스트를 반환받는다.