다시 또 월요일이 찾아왔다.
벌써 일주일이 지났다니 약간 실감이 잘 안난다.
(내 느낌으로는 한 10일 이상 보낸거 아직 7일밖에 지나지 않았다니… )
오늘은 어제 공부를 덜한 퀵소트 와 머지 소트에 대해서 공부를 하고
퀵소트를 좀 더 핵심적으로 공부하기 위해 혼자서 빈 종이에 코드를 다 적을 수 있을때까지 반복하기로 했다.
정글 커리큘럼상 알고리즘 주차에서는 매주 목요일마다 3문제씩 문제를 풀고 동료에게 피드백을 받도록 되어있다. 해당 내용 설명 과 연습을 위해 중간에 코치님들이 들어오셔서 설명을 해주셨다.
깃헙에서 브런치를 만들고 PR 하는 방법, 상대방의 코드를 approve 및 merge 하는 방법등을 알려주셨다.
나는 다행히도 그전에 깃을 조금 썻었고, 소스트리도 조금 다룰 줄 알다보니까 알던 내용을 복습할 수 있어서 좋았다.
저녁까지 정렬을 공부해서 일단 책에서 중요한 내용을 뽑아내고, 큰 개념들은 이해할 수 있었다.
그리고 나서는 나 혼자 빈 메모장에 코드를 쭉 써내려가는 연습을 했는데, 개념은 확실히 이해했는데 이걸 코드로 구현하려니까 잘 되지 않았다.
나는 분명 안다고 생각했던 부분들이 코드로 표현하려니 조금 다르게 느껴졌다.
버블 , 삽입 , 선택 정렬 까지는 어떻게 어떻게 구현을 하고 넘어갔다.
그래서 이제는 제일 중요하며 혼자서 수도코드 정도는 쓸 수 있어야 하는 퀵소트 부분이다.
빈 메모장을 열고 내가 이해한 대로 퀵 소트를 구현했다.
그리고 실행을 시켜보니 이상하게 정렬이 되거나 , 무한 재귀에 빠지는 경우가 발생했다.
여기서 나는 그 부분을 찾기 위해서 디버그 모드를 켜고 어떨때 문제가 발생하는지 쭉 추적을 했고
결국 어떤 부분이 문제가 되서 이런 이상한 경우가 생기는지 알 수 있었다.
이런 디버깅을 통해서 내가 빠트린 부분이 어디이며 왜 이런 일이 발생하는지 알 수 있어서 조금 더 공부가 확실히 되었다.
내가 처음에 구현한 quick sort
def quick_sort(list, start_cursor, end_cursor):
pl = start_cursor
pr = end_cursor
pivot_idx = (start_cursor + end_cursor) // 2
while pl <= pr:
while list[pl] < list[pivot_idx]:
pl += 1
while list[pr] > list[pivot_idx]:
pr -= 1
list[pl], list[pr] = list[pr], list[pl]
pl += 1
pr -= 1
quick_sort(list, start_cursor, pr)
quick_sort(list, pl, end_cursor)정답 코드
def quick_sort(list, start_cursor, end_cursor):
pl = start_cursor
pr = end_cursor
pivot_idx = (start_cursor + end_cursor) // 2
while pl <= pr:
while list[pl] < list[pivot_idx]:
pl += 1
while list[pr] > list[pivot_idx]:
pr -= 1
if pl <= pr: # 조건문 추가
list[pl], list[pr] = list[pr], list[pl]
pl += 1
pr -= 1
if start_cursor < pr: # 조건문 추가
quick_sort(list, start_cursor, pr)
if pl < end_cursor: # 조건문 추가
quick_sort(list, pl, end_cursor)💡 조건문이 들어가야 하는 이유
- 조건문이 없는 경우에는 교환을 하지 않아야 하는 상황에서도 교환을 하게 되어 정렬이 이상하게 된다.
- 재귀 종료조건이 설정되지 않아서 무한 재귀에 빠지게 된다.
