선택정렬

힙 정정 (Heap Sort) - 힙 구조의 특성을 이용한 정렬 - 수행시간은 합병정렬과 동일한 O(nlon) - 삽입정렬과 동일한 제자리 정렬 (Sort in Place) 힙의 형태 (The chape of a heap) - 완전 이진 트리(Complete binary tree)에 가까운 형태 (트리는 부모노드와 자식 노드로 구성되어있는 그래프) - 이진트리(Binary tree)는 각 노드의 자식수가 2 이하인 경우 - 완전 이진트리는 Root노드부터 Leaf노드까지 빠짐없이 채워져 있는 트리 최대힙 특성 (Max-Heap Property) - 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같다. - 따라서 전체 트리의 Root 노드값이 가장크다. - 또한 각 하위 트리 구조의 Root 노드가 가..

정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명할 수 있다. 문제정의, 알고리즘 설명, 정확성 증명, 성능 분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3......... an) - 출력 (output) 입력된 숫자 위 배열이 오름차순 조건을 만족하도록 재 배열하는 것 합병 정렬(Merge Sort) - 합병을 이용한 정렬 알고리즘 - 두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병 - 각 배열의 가장 왼쪽에 있는 값을 비교해보면 가장 작은 수를 알 수 있다. 정렬을 하기에는 너무 큰 배열을 쪼개어 정렬한 후 합병한다. 이를 위해 합병 정렬을 필요한 것이다. A divide-and-conquer approach 크기가 커서 풀기 어려운 하나의..

정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명 할 수있다. 문제정의, 알고리즘 설명, 정확성증명, 성능분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3 ......... an) - 출력 (output) 입력된 숫자위 배열이 오름차순 조건을 만족하도록 재 배열하는것 선택정렬 알고리즘 선택정렬(Selection sort) - 선택하여 정렬하는 알고리즘 - 최소값 선택 정렬 (Min-Selection sort) 가장 작은 값을 선택(오름차순) - 최대값 선택 정렬 (Max-Selection sort) 가장 큰 값을 선택(내림차순) - 정확성 증명 수학적 귀납법을 이용 i번쨰 선택한 숫자가 i번째로 작은(혹은 큰) 숫자인지를 증명 - 성능분석 최선 최악의 경우 수행..

정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명 할 수있다. 문제정의, 알고리즘 설명, 정확성증명, 성능분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3 ......... an) - 출력 (output) 입력된 숫자위 배열이 오름차순 조건을 만족하도록 재 배열하는것 삽입정렬(Insertion sort) - 삽입을 이용한 정렬 알고리즘 Key 값과 정렬된 리스트가 주어졌을 때 , Key 값을 정렬된 리스트의 알맞는 위치에 삽입 Key가 3이고 정렬된 배열이 일때 키를 알맞은 위치에 삽입한 배열은 이다.

선택정렬 가장 작은 값은 찾는다. (첫 번째 값과 두 번째 값을 비교해서 작은 값을 찾고 그 값과 3번째 값과 또 비교하고 이렇게 차례차례 비교해서 가장 앞에 가장 작은 수를 넣는다.) 무조건 모든 것을 비교해 봐야 한다. 즉 최선과 최악의 경우의 수행 시간이 같음 따라서 선택 정렬은 전체의 배열에서 최솟값을 찾아 맨 앞에 위치시키고 인덱스를 하나씩 증가시켜 그다음 작은 값을 위치시킨다. - 최선 최악 경우 시간 : 무조건 n^2 삽입 정렬 - 삽입을 이용한 정렬 알고리즘 - Key 값과 정렬된 리스트가 주어졌을 때, Key값을 정렬된 리스트에 알맞은 위치에 삽입 key 값을 정렬된 배열에 넣으면서 정렬 배열을 하나씩 늘려가는 정렬 방식 최선과 최악의 경우가 다르다. for문 2개가 아닌 while 문을..