I. 선택 정렬 (Selection Sort)의 개요가. 선택 정렬의 정의정렬이 안된 숫자들 중에서 최소 값을 선택하여 배열의 첫 번째 요소와 교환하는 정렬 기법 나. 삽입 정렬의 특징수행시간 복잡도 : O(n2)안정성을 만족하지 않음.  Ⅱ. 선택 정렬의 단계 및 사례가. 선택 정렬의 단계 (Pseudo Code)  나. 선택 정렬의 사례 public static int[] doSelectionSort(int[] arr){for (int i = 0; i {int index = i;for (int j = i + 1; j if (arr[j] index = j;int smallerNumber = arr[index];arr[index] = arr[i];arr[i] = smallerNumber;}return a..

I. 신장트리 (Spanning Tree)의 개요가. 신장 트리의 정의모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프 최소신장트리의 정의정점 간 가중치(cost)의 합이 최소인 신장 트리 Ⅱ. 최소신장트리 알고리즘가. Prim의 알고리즘 * 시작점 기반 최소 가중치* 정점마다 edge 검사* 우선순위 큐 기반 구현임의의 vertex를 선택, 신장 트리의 루트 노드로 삽입선택된 vertex와 인접 vertex들 사이의 edge 가중치 검사최소 가중치를 가지는 edge를 선택해당 edge로 두 정점을 연결했을 때, cycle이 발생하면 버리고, 그렇지 않으면 신장트리에 삽입선택된 edge는 edge리스트에서 제거edge리스트에 더 이상의 edge가 없을 때까지 2~5번 반복voi..

I. 기수 정렬 (Radix Sort)의 개요가. 기수 정렬의 정의레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법 나. 기수 정렬의 특징O (n log2 n) 이라는 이론적인 하한선을 깰 수 있는 유일한 방법시간 복잡도 : O(kn) k : 버킷 수정렬 레코드 타입 제한 Ⅱ. 기수 정렬의 개념 및 사례가. 기수 정렬의 개념  나. 기수 정렬 사례 (Sorting a sequence of 4-bit integers) 코드 구현 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public void Radix_Sort(int[] data){int maxsize = getMaxlength(data..

I. 퀵 정렬 (Quick Sort)의 개요가. 퀵 정렬의 정의Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘 나. 퀵 정렬의 특징분할과 정복 기반재귀호출 구조정렬을 위한 별도의 스택이 필요수행시간 복잡도: O(n·log2n) Ⅱ. 퀵 정렬의 단계 및 사례가. 퀵 정렬의 단계 정렬할 원소들의 집합에서 Pivot 값을 설정Pivot보다 큰 값은 오른쪽, 작은 값은 왼쪽분할된 집합의 크기가 1이 될 때까지 반복 나. 퀵 정렬의 사례 void quicksort(element list[], int left, int right) {int pivot, i, j; element temp;if(left i = left; j = right + 1;pivot = list[..

I. 버블 정렬 (Bubble Sort)의 개요가. 버블 정렬의 정의여러 개의 자료 중에서 서로 이웃하는 키 값을 두 개씩 비교하여 순서를 결정하는 정렬 방법 나. 버블 정렬의 특징간단하지만 느린 속도의 알고리즘flag를 통해 속도 개선 가능수행시간 복잡도: O(n2) Ⅱ. 버블 정렬의 단계 및 사례가. 버블 정렬의 단계 인접한 두 개의 키 값을 비교함.앞의 키 값이 뒤의 키 값보다 크면 교환더 이상 비교할 대상이 없을 때까지 처음부터 반복 나. 버블 정렬의 사례 /* list에 대한 기본 버블정렬 알고리즘 */void bubble_sort(element list[], int n) {int i, j;element next;for(i = n-1; i > 0; i--){for(j = 0; j if(list[..

I. 해시 탐색 (Hash Search)의 개요가. 해시 탐색 (Hash Search)의 정의해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘해시테이블(hash table) : 키 값을 저장하는 테이블버킷(bucket) : 해시될 키 값의 범위, 테이블의 크기슬롯(slot) : 한 개의 버킷에 저장될 키 값의 개수 나. 해시 탐색 (Hash Search)의 특징고정길이, One WayO(1)의 탐색 속도충돌처리 매커니즘 필요 Ⅱ. 해시 함수의 기법가. 해시 함수의 기법 구 분내 용mid-square식별자의 제곱 값의 가운데 값을 취함.division나머지 연산자(modulus, %)을 이용함.- 버킷 주소의 범위 : 0 ~ m-1- m값의 선택이 중요함. m을 소수(prime..

I. 합병 정렬 (Merge Sort)의 개요가. 합병 정렬의 정의리스트를 두 개로 나누어, 각각을 정렬한 다음, 다시 하나로 합치는 정렬 방법 나. 합병 정렬의 특징분할과 정복 : 분할(Divide) -> 정복(Conquer) -> 결합(Combine) 과정 수행재귀적 수행 : 분할을 마친 후 분할된 부분의 반복적 수행정렬을 위한 별도의 공간이 필요수행시간 복잡도: O(n·log2n) Ⅱ. 합병 정렬의 단계 및 사례가. 합병 정렬의 단계  나. 합병 정렬 개념 void mergeSort(int arr[], int l, int r){if (l {int m = l+(r-l)/2; //Same as (l+r)/2, but avoids overflow for large l and hmergeSort(arr, ..

I. 이진 탐색 (Binary Search)의 개요가. 이진 탐색의 정의정렬된 데이터 집합에서 탐색 범위를 1/2씩 줄여 나가면서 수행하는 방식 나. 이진 탐색의 특징분할과 정복 기반정렬된 데이터 집합에서 사용고속 탐색 Ⅱ. 이진 탐색 단계 및 사례가. 이진 탐색 단계 및 사례- 데이터 집합의 가운데 있는 기준값과 찾는 키 값 비교(1) 찾는 키 값 > 기준 값 : 오른쪽 부분 검색(2) 찾는 키 값 - 키 값을 찾을 때까지 이진 검색을 순환적으로 반복 /*searchnum 에 대해 list [0]찾으면 그 위치를 반환하고 못 찾으면 –1을 반환한다.*/int binsearch(int list[],int searchnum, int left,int right){int middle;while(left mid..

I. 삽입 정렬 (Insert Sort)의 개요가. 삽입 정렬의 정의첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법 나. 삽입 정렬의 특징간단하지만 레코드의 이동이 많은 알고리즘비교적 크기가 작은 데이터 집합 정렬에 유리함.수행시간 복잡도: O(n2) Ⅱ. 삽입 정렬의 단계 및 사례가. 삽입 정렬의 단계  삽입 대상 위치를 2번째부터 마지막까지 지정비교 대상을 처음부터 바로 전까지 지정정렬 대상의 값들과 뽑아낸 요소와 비교삽입할 값보다 큰 값을 가진 모든 요소들을 한 자리씩 오른쪽으로 이동새로 생긴 빈 자리에 해당 요소를 삽입전체 데이터 집합의 정렬이 완료될 때까지 반복 나. 삽입 정렬의 사례  void insertion_sort(element list[], in..