본문 바로가기

전체 글

균형 이진 탐색 트리 균형 이진 탐색 트리 맵은 이진 탐색 트리로도 구현할 수 있다. 이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조로 탐색에 걸리는 시간도 로 동일하다. 그렇다면 이들의 차이는 무엇일까? 답은 자료의 삽입과 삭제의 용이성에 있다. 이진 탐색에서 자료는 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉, 맵에 자료를 삽입하거나 삭제할 때 불필요한 항목들의 많은 이동이 필요하다. 반면에 맵을 이진 탐색 트리로 구현하면 시간에 삽입과 삭제가 가능하다. 따라서 삽입과 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용하여야 한다. 이진 탐색 트리는 만약 균형 트리이면 의 탐색 연산 시간 복잡도를 갖는다. 그러나 삽입과 삭제 연산이 이진 탐색 트리를 유지시키기는 하지만 균형 트리를.. 더보기
Search.h : 다양한 탐색 함수를 포함함 헤더 색인 순차 탐색색인 순차 탐색(indexed sequential search) 방법은 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다. 인덱스 테이블은 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 인덱스 테이블에 m개의 항목이 있고, 주 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 주 자료 리스트의 각 n/m 번째 데이터를 가지고 있다. 이 때 주 자료 리스트와 인덱스 테이블은 모두 정려되어 있어야 한다. 색인 순차 탐색 알고리즘은 우선 인덱스 테이블에서 index[i] 더보기
Sorting.h : 다양한 정렬을 포함한 헤더 | 정렬 방법의 성능 비교 알고리즘 최선 평균 최선 삽입 정렬 선택 정렬 버블 정렬 셸 정렬 퀵 정렬 힙 정렬 합병 정렬 기수 정렬 | 정렬 알고리즘별 실험 결과 ( 정수 : 60,000개 ) 알고리즘 실행 시간( 단위 : sec) 삽입 정렬 7.348 선택 정렬 10.842 버블 정렬 22.894 셸 정렬 0.056 힙 정렬 0.034 합병 정렬 0.026 퀵 정렬 0.014 #pragma once#ifndef ___Sorting#define ___Sorting// Sorting.h : 다양한 정렬을 포함한 헤더#include "cstdio"#include "cstdlib"#include "CircularQueue.h" #define MAX_SIZE 1024#define BUCKETS 10#define.. 더보기
기수 정렬 프로그램 기수 정렬 다른 정렬방법들은 모두 레코드들을 비교하여 정렬한다. 기수 정렬(radix sort)은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 기법이다. 다른 방법들이 이라는 정렬의 이론적인 하한선을 깰 수 없는데비해 기수 정렬은 이 하한선을 깰 수 있는 유일한 기법이다. 사실 기수 정렬은 의 시간 복잡도를 가지는데 대부분 k 더보기
퀵 정렬 라이브러리 함수의 사용 함수의 원형void qsort(void* base,size_t num,size_t width,int (*compare)(const void *, const void *)); 함수의 파라미터 설명base : 배열의 시작 주소 num : 배열 요소의 개수width : 배열 요소 하나의 크기(바이트 단위)compare : 비교 함수. 포인터를 통하여 두개의 요소를 비교하여 비교 결과를 정수로 반환한다. 사용자가 제공하여야 됨. #include #include #include // 두 수를 비교해 오름차순으로 정렬되도록 하는 함수int compareAs(const void *arg1, const void *arg2) {return (*(double *)arg1 > *(double *)arg2) ? 1 :(*(d.. 더보기
퀵 정렬 알고리즘을 이용해 오름차순으로 정렬하는 함수 퀵 정렬 퀵 정렬(quick sort)은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 합병 정렬과 같이 분할-정복법(divide and conquer)을 사용한다. 그러나 합병 정렬과는 달리 리스트를 균등하지 않게 분할한다. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피벗으로 하자. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고, 오른쪽은 피벅보다 큰 요소들로 구성된다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다. 퀵 정렬의 평균적인 경우의 시.. 더보기
합병 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 합병 정렬 합병 정렬(merge sort) 은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트트를 만드는 방법이다. 이것은 분할 정복(divide and conquer) 기업에 바탕을 두고 있는데, 하나의 문제를 작은 2개의 문제로 분리하고 각가을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분리된 문제가 아직도 해결하기 어렵다면, 즉 충분히 작지 않다면 분할 정복 방법을 연속하여 다시 적용한다. 분할 정복 기법은 대개 순환 호출을 이용하여 구현된다. 1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할 한다. 2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충.. 더보기
셸 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 | 셸 정렬의 분석 셸 정렬의 2가지 장점 연속적이지 않은 부분 파일에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한 번에 한 칸씩만 이동된다. 따라서 교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다. 부분 리스트가 하나가 되면 셸 정렬은 전체 리스트를 정렬해야 한다. 그러나 삽입 정렬이 거의 정렬된 리스트에 대해 매우 효율적이므로 이 과정도 빠르게 수행된다. 실험적인 연구를 통하여 셀 정렬의 시간 복잡도는 최악의 경우에는 이지만 평균적인 경우에는 인 것으로 알려져 있다. // gap 만큼 떨어진 요소들을 삽입 정렬. 정렬의 범위는 first 에서 laststatic void sortGapInsertion(int A[], int first, .. 더보기

티스토리툴바