컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c )
힙 정렬 힙 정렬이란? - 힙의 특성을 이용한 정렬 수행시간 : 합병정렬과 동일한 O(nlogn), 삽입정렬과 동일한 제자리 정렬 (Sort in Place) 힙이란 ? - 완전 이진 트리에 가까운 형태 이진 트리란? - 각 노드의 자식수가 2이하인 경우 완전 이진 트리란 ? - Root(맨 위)노드부터 Leaf(가장 아래)노드까지 빠짐없이 채워져 있는 트리 여기서 root의 어원은 트리를 뒤집었을 때 가장 첫번째 . 뿌리라고하여 root라고 부른다. 완전 이진 트리의 조건은 왼쪽부터 차례로 채워야함. 만약 ㅇ ㅇ ㅇ ㅇ ㅇ 이렇게 있으면 왼쪽아래가 비어있다. 즉 왼쪽부터 차례로 채우지 않았기 때문에 완전이진트리가 아니다. ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇㅇㅇ 이렇게 있으면 오른쪽아래는 비어있지만 왼쪽부터 채..
삽입정렬이란 삽입하여 정렬하는 것이다. 입력 : n개의 숫자 출력 : n개의 숫자가 점점 커지는 순서로 정렬 , 가장 큰 숫자가 가장 오른쪽으로 간다. ( 오름차순 ) 무엇을 삽입할 것인가? Key 값과 정렬된 리스트가 주어졌을 때, Key 값을 정렬된 리스트의 알맞은 위치에 삽입 Key가 3이고 정렬된 배열이 일 때 1과 2 사이에 3을 넣음으로써 으로 정렬함. 정렬을 시작할 때 처음 값 한개는 미리 넣어둔다. 두번째 숫자부터는 Key 값으로 생각을 하고 삽입한다. 즉 일 때 이렇게 들어간다고 생각하면 된다. 과정은 만약 삽입할 key가 가장크면 맨뒤에 남고, 아니면 그 앞자리와 자리를 바꿈. 이걸 앞자리보다 key가 클때까지 반복하면 자기자리에서 멈추게 된다. 수행시간을 분석해보면, 몇번 째 자리가 ..
정렬 문제 ( 오름차순 내림차순 ) 입력 - n개의 숫자들의 배열이다. 출력 - 입력된 숫자의 배열이 크기순을 조건으로 만족하도록 나열한 결과 선택정렬 알고리즘 선택정렬은 무엇인가? - 선택해서 정렬하는 알고리즘이다. 선택을 할때 무엇을 선택하는지가 중요한 핵심이 된다. 1. 최소값 선택 정렬 (결과 : 오름차순) 2. 최대값 선택 정렬 (결과 : 내림차순) 최소값 선택 정렬의 알고리즘 1. 정렬되지 않는 숫자 중 가장 작은 숫자 선택 ( 최소값 ) 2. 선택한 숫자를 정렬되지 않은 숫자들 중 첫 번째 숫자와 자리를 바꾸면 최소값이 가장 앞으로감 3. 첫번째를 제외하고 그 뒤에서부터 정렬되지 않은 숫자들 중 가장 작은 숫자 선택, 가장 앞 +1 로 보냄 4. 반복 ex) 5 , 4 , 2 , 1, 3 첫..