정렬 알고리즘 수행시간 비교
2020/03/10 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #2 ( 선택정렬 in c ) 2020/03/18 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #3 ( 삽입정렬 in c ) 2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #4 ( 합병정렬 in c ) 2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c ) 2020/05/13 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #6 ( 힙 정렬 in c ) 2 수행시간만 보면 효율적인 것은 nlgn을 가지는 정렬이다. mrege sort 는 nlgn이긴 하지만 추가 공간이 필요하다. heapsort 는 nlgn이긴 하지만 힙 구조를 만들고, 그 구조..
컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c )
힙 정렬 힙 정렬이란? - 힙의 특성을 이용한 정렬 수행시간 : 합병정렬과 동일한 O(nlogn), 삽입정렬과 동일한 제자리 정렬 (Sort in Place) 힙이란 ? - 완전 이진 트리에 가까운 형태 이진 트리란? - 각 노드의 자식수가 2이하인 경우 완전 이진 트리란 ? - Root(맨 위)노드부터 Leaf(가장 아래)노드까지 빠짐없이 채워져 있는 트리 여기서 root의 어원은 트리를 뒤집었을 때 가장 첫번째 . 뿌리라고하여 root라고 부른다. 완전 이진 트리의 조건은 왼쪽부터 차례로 채워야함. 만약 ㅇ ㅇ ㅇ ㅇ ㅇ 이렇게 있으면 왼쪽아래가 비어있다. 즉 왼쪽부터 차례로 채우지 않았기 때문에 완전이진트리가 아니다. ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇㅇㅇ 이렇게 있으면 오른쪽아래는 비어있지만 왼쪽부터 채..