프로그래밍 자습서

퀵 정렬은 여러가지 방식으로 구현할 수 있다. 구현하는 방식도 여러가지인 만큼 여러 문서를 보면서 이해하는데 한참 걸렸다. 가장 도움이 컸던 것은 나동빈님의 퀵정렬 글이었다. 가장 구현하기 쉬운 것은 Pivot을 맨 왼쪽 혹은 오른쪽에 있는 것을 잡는 것. 그러나 이런 식으로 하면 이미 정렬되어 있는 배열을 정렬할 때 시간 복잡도가 O(n^2)이 되기에 선택정렬이나 버블정렬과 다를게 없다. 그래서 피벗을 랜덤으로 잡거나 중간지점을 잡으라는데. 나는 위 아래 둘다 해보고 시간이 얼마나 걸리는지 측정해봤다. 1. 피벗을 맨 왼쪽으로 잡는 퀵 정렬. void quickSort(int lo, int hi) { if (lo >= hi) { return; } else { int pi = lo; int i = lo ..

자습 2021. 1. 9. 19:58

linear linked list를 이용한 stack에 이어 두번째 algorithm 시간이다. 오늘은 heap tree와 heap sort를 구현했다. 재학시절 트리를 구현한 적이 있긴 있는데 2년이 넘도록 그에 관련한 알고리즘을 사용하지도 않고 보지도 않았으니 다 까먹었다. 그래서 heap tree를 이해하는데 한참이 걸렸다. 아무것도 모르는 사람이 heap tree 의 이미지를 보면 난해할것이다. 이미지만 보고서 구현을 할라면 무엇으로 구현을 해야하는지 착잡해지는데. 간단하다. heap tree는 1차원 배열로 구현되며, 0이 아닌 1로 시작한다는 가정 하에 부모 자식간의 상관은 자식/2가 부모를 가리킨다. #include #include #include void newKey(); void delK..

자습 2020. 12. 10. 15:35