8월 31, 2008 – 11:28 오후
이 글은 599 번 읽혀 졌습니다.
오랜만이란 단어로 모든것에 대해서 용서가 되진 않겠지만 정말 프로그래밍 언어 만큼 지속적으로 공부하고 손에 잡고 있지 않으면 잊어버리게 되는것도 많지 않은것 같다. 암튼 옛날 기억도 되살리고 자료들도 보면서 다시 작성해본 정렬프로그래밍들 뭐 대부분 책에 있는 내용들이라서 암튼.^^
=======================================================
#include <stdio.h>
void print_Array(int list[], int n)
{
for (int i=0; i<n; i++)
printf(”%d\t”, list[i]);
printf(”%\n”);
}
void swap(int list[], int i, int j)
{
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
void selection_sort(int list[], int n)
{
int i, j, min;
for (i=0; i<n-1; i++) {
min = i;
for (j=i+1; j<n; j++)
if (list[j] < list[min])
min = j;
swap(list, min, i);
}
}
void insertion_sort(int list[], int n)
{
int i, j;
int next;
for (i=1; i<n; i++) {
next = list[i];
for (j=i-1; j>=0 && list[j] > next; j–)
list[j+1] = list[j];//앞에 있는거 뒤로 이동
list[j+1] = next;
}
}
void bubble_sort(int list[], int n)
{
int i, j;
for (i=n-2; i>=0; i–)
for (j=0; j<=i; j++)
if (list[j] > list[j+1])
swap(list, j, j+1);
}
void quick_sort(int list[], int left, int right)
{
int pivot, i, j;
if (left < right) {
i = left; j = right + 1;
pivot = list[left];
do {
do {
i++;
}while(list[i] < pivot);
do {
j–;
}while(list[j] > pivot);
if (i < j)
swap(list, i, j);
}while ( i < j);
swap(list, left, j);
quick_sort(list, left, j-1);
quick_sort(list, j+1, right);
}
}
void merge_sort_merge(int list[], int i, int m, int n)
{
int j, k, t, first;
j = m + 1;//두번째 리스트에 대한 인덱스
k = i;//정렬된 리스트에 대한 인덱스
first = i;//i의 초기값 기억
int sorted[5] = {0,0,0,0,0};
while (i <= m && j <= n) {
if (list[i] <= list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
if ( i > m ) //두번째 배열을 다 갖다 붙이자. left쪽은 다 썻으므로.
for (t =j; t<=n; t++)
sorted[k+t-j] = list[t];
else
for (t=i; t<=m; t++)
sorted[k+t-i] = list[t];
for(t=first; t<=n; t++)
list[t] = sorted[t];
}
void merge_sort(int list[], int left, int right)
{
int mid;
if (left < right) {
mid = (left + right)/2;
merge_sort(list, left, mid);
merge_sort(list, mid+1, right);
merge_sort_merge(list, left, mid, right);
}
}
void makeheap(int list[], int i, int n)
{
int child, root, temp;
temp = list[i];
root = list[i];
child = 2*i;
while (child <= n) {
if ((child < n) && (list[child] < list[child+1]))
child++;
if (root > list[child])
break;
else {
list[child/2] = list[child];
child = child * 2;
}
}
list[child/2] = temp;
}
void heap_sort(int list[], int n)
{
int i;
for (i= n/2; i>0; i–)
makeheap(list, i, n);
for (i=n-1; i>0; i–) {
swap(list, 1, i+1);
makeheap(list, 1 ,i);
}
}
void main()
{
int array[] = {0,75,100,80,85};
print_Array(array, 5);
//selection_sort(array, sizeof(array)/sizeof(array[0]));
//insertion_sort(array, sizeof(array)/sizeof(array[0]));
//bubble_sort(array, 5);
//quick_sort(array, 0, 4);
//merge_sort(array, 0, 4);
heap_sort(array, 4);
print_Array(array,5);
}
Posted in study | No Comments »
Tags:
c 
