2.4.2 삽입 정렬 알고리즘 구현
삽입정렬 알고리즘.zip삽입 정렬 알고리즘을 구현합시다. 시뮬레이션 함수 등은 앞과 같으므로 설명을 생략할게요.
void insertion_sort(Element *base, int n, Compare compare)
{
두 개의 반복문에서 사용할 변수를 선언하고 교환에 사용할 임시 변수도 선언할게요.
int i = 0, j=0;
Element temp;
외부 반복문은 정렬할 범위를 넓혀나가는 것입니다. 따라서 i를 1부터 n까지 점진적으로 증가할게요.
for(i=1; i<n; i++)
{
내부 반복문은 새롭게 범위에 포함한 원소의 위치를 찾아야 합니다. 따라서 j를 i로 초기화하고 점진적으로 줄여나갑니다.
for(j=i; j>0; j--)
{
만약 j번째 원소가 앞의 원소보다 크면 자리를 교환합니다.
if(compare(base[j-1],base[j])<0)
{
temp = base [j-1];
base[j-1] = base [j];
base[j] = temp;
}
그렇지 않을 때는 반복문을 탈출합니다.
else{ break; }
}
}
}
다음은 삽입 정렬 알고리즘과 이를 테스트 하는 소스 코드 내용입니다.
#include "common.h"
#include "Book.h"
typedef void *Element;
typedef int (*Compare)(Element , Element);
void insertion_sort(Element *base, int n, Compare compare)//삽입 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
{
int i = 0, j=0;
Element temp;
for(i=1; i<n; i++)
{
for(j=i; j>0; j--)
{
if(compare(base[j-1],base[j])<0)
{
temp = base [j-1];
base[j-1] = base [j];
base[j] = temp;
}
else
{
break;
}
}
}
}
#define MAX_BOOK 10000
Book *books[MAX_BOOK]={0};
void SimulationInit()
{
char title[MAX_TIT_LEN+1]="";
char author[MAX_AUT_LEN+1]="";
int i = 0;
for(i=0; i<MAX_BOOK; ++i)
{
sprintf(title,"%010d",rand());
sprintf(author,"%010d",rand());
books[i] = New_Book(title,author,rand());
}
}
int CompareByTitle(Book *book1,Book *book2)
{
return Book_CompareTitle(book1,book2->title);
}
int CompareByNum(Book *book1,Book *book2)
{
return Book_CompareNum(book1,book2->num);
}
void ListBook(int n)
{
int i = 0;
for(i=0; i<n; ++i)
{
Book_View(books[i]);
}
}
void Simulation1()
{
insertion_sort(books,10,CompareByTitle);
printf("--------제목순-------\n");
ListBook(10);
insertion_sort(books,10,CompareByNum);
printf("--------번호순-------\n");
ListBook(10);
}
void Simulation2()
{
clock_t st,et;
st = clock();
insertion_sort(books,MAX_BOOK/10,CompareByTitle);
et=clock();
printf("%d개 정렬에 걸린 시간:%d\n",MAX_BOOK/10,et-st);
st = clock();
insertion_sort(books,MAX_BOOK,CompareByTitle);
et=clock();
printf("%d개 정렬에 걸린 시간:%d\n",MAX_BOOK,et-st);
}
void SimulationClear()
{
int i = 0;
for(i=0; i<MAX_BOOK; ++i)
{
Delete_Book(books[i]);
}
}
int main()
{
SimulationInit();
Simulation1();
Simulation2();
SimulationClear();
return 0;
}
'언어 자료구조 알고리즘 > [C]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| [디딤돌 자료구조와 알고리즘 with C] 3.4 이진 탐색 트리 (0) | 2016.04.10 |
|---|---|
| [디딤돌 자료구조와 알고리즘 with C] 3.3.2 퀵 정렬 알고리즘 구현 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 3.3 퀵 정렬 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 3.2 하노이 타워 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 3. 재귀 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 2.4 삽입 정렬 알고리즘 (2) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 2.3.2 선택 정렬 알고리즘 구현 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 2.3.1 선택 정렬 알고리즘 성능 분석 (0) | 2016.04.10 |
| [디딤돌 C언어 자료구조와 알고리즘] 2.3 선택 정렬 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 2.2.2 버블 정렬 알고리즘 구현 (0) | 2016.04.10 |