Programings (23) 썸네일형 리스트형 RVector #include /************************************************** 장점 : 빠른 접근 단점 : 앞쪽으로 넣을 수록 데이터를 뒤로 보내는 작업이 발생함 주의 : 템플릿은 H파일과 C파일로 나누지 않는 것이 좋음 **************************************************/ template class RVector : public std::vector { private: typename std::vector::iterator it; void count(int i) { it = begin(); for(int k=0; k HTML 여러가지 속성 예제 메모 작성하기 이름 메일 비밀번호 내용 [Algorith] 병합 정렬 (Merge Sort) #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 void MakeRandomNumber(void); void MergeSort(int [], int, int); void DisPlayBuffer(void); int IsNumberExit(int, int); int Buf[MAX]; int temp[MAX]; void main() { printf("정렬할 데이터의 초기화\n"); MakeRandomNumber(); DisPlayBuffer(); printf("정렬 후 데이터\n"); MergeSort(Buf, 0, MAX -1); DisPlayBuffer(); printf("\n"); } void MakeRandomNumb.. [Algorith] 퀵 정렬 (Quick Sort) #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 void MakeRandomNumber(void); void QuickSort(int [], int, int); void DisPlayBuffer(void); int IsNumberExit(int, int); int Buf[MAX]; void main() { printf("정렬할 데이터의 초기화\n"); MakeRandomNumber(); DisPlayBuffer(); printf("정렬 후 데이터\n"); QuickSort(Buf, 0, MAX -1); DisPlayBuffer(); printf("\n"); } /* 정렬할 데이터의 초기화 */ void MakeRandom.. [Algorith] 쉘 정렬 (Shell Sort) Bing-O 표기법에 의한 O( N (logN)^2 ) 이다. 퀵 정렬에 가까운 성능을 보인다. #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 // 함수의 프로토타입 void MakeRandomNumber(void); void ShellSort(void); void DisplayBuffer(void); int IsNumberExit(int, int); int Buf[MAX]; void main() { printf("정렬할 데이터의 초기화\n"); MakeRandomNumber(); DisplayBuffer(); printf("정렬 후 데이터\n"); ShellSort(); DisplayBuffer(); printf("\.. [Algorith] 버블 정렬 (Bubble Sort) 정렬 전 3 7 9 1 2 1차 정렬 3 7 1 9 2 -> 3 7 1 2 9 1차 정렬 끝 2차 정렬 3 1 7 2 9 -> 3 1 2 7 9 2차 정렬 끝 3차 정렬 1 3 2 7 9 -> 1 2 3 7 9 3차 정렬 끝 정렬이 한번 끝날 때 마다 끝에 가장 큰 수가 정렬된다. 비교 횟수는 N^2/2가 된다. 만약 최악의 경우일 경우 비교와 이동 횟구 모두 N^2/2가 된다. Big-O 표기법의 의한 O(N^2)이 된다. #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 // 함수의 프로토타입 void MakeRandomNumber(void); void BubbleSort(void); void DisplayBuffer(.. [Algorith] 삽입 정렬 (Insertion Sort) 정렬 전 3 7 9 1 2 1차 정렬 3 7 9 1 2 2차 정렬 3 7 9 1 2 3차 정렬 1 3 7 9 2 4차 정렬 1 2 3 7 9 비교 횟수는 데이터 수와 같다. 최악의 경우엔 N(N-1)/2 의 계산이 필요하다. 또한 데이터의 이동 횟수도 N(N-1)/2의 계산이 나온다 따라서 정렬이 잘된 리스트를 가지고 삽입 정렬을 하면 선택 정렬에 비해 빠를 수 있다. 왜냐면 삽입 정렬의 비교가 비교적 선택 정렬보다 적을 수 있기 때문이다. 그래서 정렬이 잘 되어 있다면 O(N)에 가까운 계산이 나올 수 있다. 다만 정렬이 안된 상태라면 선택 정렬이 빠를 수 있다. Big-O 표기법의 의한 O(N^2)이다. #include #include #define MAX 100 #define TRUE 1 #defi.. [Algorith] 선택 정렬 (Selection sort) 정렬 전 3 7 9 1 2 1차 정렬 1 7 9 3 2 2차 정렬 1 2 9 3 7 3차 정렬 1 2 3 9 7 4차 정렬 1 2 3 7 9 정렬을 할때 위와 같이 첫 번째 원소의 값을 그 뒤의 나머지 원소들 중 가장 작은 값과 바꾼다. 두번째 원소의 값을 그 뒤의 원소들 가장 작은 값과 바꾼다. 위와 같이 반복하면 정렬이 끝난다. 선택 정렬은 비교 하는데 N^2/2회나 되지만 데이터 교환에는 N번의 횟수면 된다. 때문에 정렬 데이터가 큰 경우 다른 정렬 알고리즘에 비해 유용하다. Big-O 표기법의 의한 계산 O(N^2) (단순 계산으로는 for문이 중첩되는 경우므로 N*N=N^2이 나온다.) #include #include #define MAX 100 #define TRUE 1 #define FALS.. 이전 1 2 3 다음
