언제나 휴일

[C언어 알고리즘] 2.5.3 삽입 정렬 알고리즘 소스 코드//삽입 정렬(Insertion Sort) #include #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 void InsertionSort(int *base, int n); int main(void) { int arr[10] = { 9,4,3,10,5,8,7,6,2,1 }; InsertionSort(arr, 10); return 0; } void ViewArr(int *arr, int n); void InsertionSort(int *base, int n) { int i, j; ViewArr(base, n);//현재 상태 출력 for (i = 1; i0; j--) { if (base[j - 1]>..

[C언어 알고리즘] 2.5.2 삽입 정렬 알고리즘 구현 삽입 정렬 알고리즘을 구현합시다. 삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(i:=1; i0 ; j:=j-1) 조건(compare (base [j-1], base [j]) < 0) temp: = base [j-1] base[j-1] = base [j] base[j] = temp 아니면 루프 탈출 //삽입 정렬(Insertion Sort) #include 먼저 두 개의 값을 교환하는 매크로 함수를 작성합니다. #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요. 원소 형식에 관계없이 정렬하는 방법은 디딤돌 정렬 ..

[C언어 알고리즘] 2.5.1 삽입 정렬 알고리즘 성능 분석 삽입 정렬 알고리즘 성능을 분석합시다. 삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(i:=1; i0 ; j:=j-1) 조건(compare (base [j-1], base [j]) < 0) temp: = base [j-1] base[j-1] = base [j] base[j] = temp 아니면 루프 탈출 n 개의 원소인 배열을 정렬할 때 비교에 걸리는 수행 시간을 T'(n)이라고 합시다. 삽입 정렬의 내부 반복문에서 비교에 걸리는 시간을 S(n)이라고 하면 S(n) = n-1입니다. T'(n)은 다음과 같습니다. T'(n) = S(2) + S(3) + ... + S(n) = 1 + 2 + 3 + ... +(n-1)..

[C언어 알고리즘] 2.5 삽입 정렬(Insertion Sort) 알고리즘이번에는 반복 알고리즘 중에 삽입 정렬 알고리즘을 알아봅시다. 삽입 정렬 알고리즘은 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘입니다. 이를 위해 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환합니다. 삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(i:=1; i0 ; j:=j-1) 조건(compare (base [j-1], base [j]) < 0) temp: = base [j-1] base[j-1] = base [j] base[j] = temp 아니면 루프 탈출 예: 정렬 전: 10 9 2 11 19 1.1회전: 9 1..

4.3 삽입 정렬 알고리즘 소스 코드 다음은 삽입 정렬 알고리즘과 이를 테스트 하는 소스 코드 내용입니다. //common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LEN 20 typedef struct _Book Book; struct _Book { char title[MAX_TIT_LEN+1]; char author[MAX_A..

4.2 삽입 정렬 알고리즘 구현 삽입 정렬 알고리즘을 구현합시다. 시뮬레이션 함수 등은 앞과 같으므로 설명을 생략할게요. void insertion_sort(Element *base, int n, Compare compare) { 두 개의 반복문에서 사용할 변수를 선언하고 교환에 사용할 임시 변수도 선언할게요. int i = 0, j=0; Element temp; 외부 반복문은 정렬할 범위를 넓혀나가는 것입니다. 따라서 i를 1부터 n까지 점진적으로 증가할게요. for(i=1; i0; j--) { 만약 j번째 원소가 앞의 원소보다 크면 자리를 교환합니다. if(compare(base[j-1],base[j])

4.1 삽입 정렬 알고리즘 성능 분석 삽입 정렬 알고리즘 성능을 분석합시다. n 개의 원소인 배열을 정렬할 때 비교에 걸리는 수행 시간을 T'(n)이라고 합시다. 삽입 정렬의 내부 반복문에서 비교에 걸리는 시간을 S(n)이라고 하면 S(n) = n-1입니다. T'(n)은 다음과 같습니다. T'(n) = S(2) + S(3) + ... + S(n) = 1 + 2 + 3 + ... +(n-1) 따라서 삽입 정렬의 비교에 걸리는 시간은 O(n^2)이라고 말할 수 있습니다.그리고 삽입 정렬에서 교환과 비교 횟수는 같습니다. 따라서 선택 정렬 알고리즘을 수행 시간은 O(n^2)이라고 말할 수 있습니다.

4. 삽입 정렬(Insertion Sort) 알고리즘 이번에는 반복 알고리즘 중에 삽입 정렬 알고리즘을 알아봅시다. 삽입 정렬 알고리즘은 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘입니다. 이를 위해 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환합니다. 삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(i:=1; i0 ; j:=j-1) 조건(compare (base [j-1], base [j]) < 0) temp: = base [j-1] base[j-1] = base [j] base[j] = temp 아니면 루프 탈출 예: 정렬 전: 10 9 2 11 19 1.1회전: 9 10 2 11 19 (..

삽입 정렬 (Insertion Sort)이번에는 반복 알고리즘 중에 삽입 정렬 알고리즘을 알아봅시다. 삽입 정렬 알고리즘은 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘입니다. 이를 위해 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환합니다. 삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(i:=1; i0 ; j:=j-1) 조건(compare (base [j-1], base [j]) < 0) temp: = base [j-1] base[j-1] = base [j] base[j] = temp 아니면 루프 탈출 삽입정렬 //삽입 정렬(Insertion Sort)#include #define SWAP(a..

2.4.2 삽입 정렬 알고리즘 구현 삽입 정렬 알고리즘을 구현합시다. 시뮬레이션 함수 등은 앞과 같으므로 설명을 생략할게요. void insertion_sort(Element *base, int n, Compare compare){ 두 개의 반복문에서 사용할 변수를 선언하고 교환에 사용할 임시 변수도 선언할게요. int i = 0, j=0; Element temp; 외부 반복문은 정렬할 범위를 넓혀나가는 것입니다. 따라서 i를 1부터 n까지 점진적으로 증가할게요. for(i=1; i0; j--) { 만약 j번째 원소가 앞의 원소보다 크면 자리를 교환합니다. if(compare(base[j-1],base[j])