ソートアルゴリズムの実装
1.ソートの挿入
アルゴリズム導論P 3
2.クイックソート(再帰的に実現)
アルゴリズム導論バージョン:p 85
3.泡立ちソート
4.ソートの選択
アルゴリズム導論P 3
/*
* InsertSort.cpp
*
* Created on: 2012-7-9
* Author: sangerhoo
*/
#include <iostream>
using namespace std;
void InsertSort(int *Array,int n)
{
int i,j,key;
for(j=1;j<n;j++)
{
key=*(Array+j);
i=j-1;
while(i>=0 && *(Array+i)>key)
{
*(Array+i+1)=*(Array+i);
i--;
}
*(Array+i+1)=key;
}
}
void ArrayPrint(int *Array,int n)
{
int i;
for(i=0;i<n;i++)
{
cout<<*(Array+i)<<"\t";
}
cout<<endl;
}
int main()
{
int i;
int Array[]={25,3,56,7,83,4,5,65,9,10};
int length=sizeof(Array)/sizeof(int);
cout<<" "<<endl;
ArrayPrint(Array,length);
InsertSort(Array,length);;
cout<<" "<<endl;
ArrayPrint(Array,length);
return 0;
}
2.クイックソート(再帰的に実現)
/*
* QuickSort.c
*
* Created on: 2012-3-17
* Author: sangerhoo
*/
#include<stdio.h>
#include<stdlib.h>
int Partition(int *array ,int i,int j)
{
int t = *(array+i);
while(i<j)
{
while(i<j && *(array+j)>=t)
j--;
if(i<j)
{
*(array+i)=*(array+j);
i++;
}
while(i<j && *(array+i)<=t)
i++;
if(i<j)
{
*(array+j)=*(array+i);
j--;
}
}
*(array+i)=t;
return i;
}
void QuickSort(int *array,int low,int high)
{
int mid;
if(low<high)
{
mid=Partition(array,low,high);
QuickSort(array,low,mid-1);
QuickSort(array,mid+1,high);
}
}
void main()
{
int array[]={12,34,67,8,23,90};
int i;
int n= sizeof(array)/sizeof(int);
printf("n=%d",n);
printf("
");
for(i=0;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
QuickSort(array,0,n-1);
printf("
");
printf("n=%d
",n);
for(i=0;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
}
アルゴリズム導論バージョン:p 85
/*
* Quicksort.cpp
*
* Created on: 2012-7-23
* Author: sangerhoo
*/
#include<iostream>
using namespace std;
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int Partion(int *array, int p, int r)
{
int temp = *(array + r);
int i = p ;
for (int j = p; j <= r ;++j)
{
if (*(array + j) < temp)
{
swap(array + i,array + j);
i++;
}
}
swap(array + i, array + r);
return i;
}
void Quicksort(int *array, int p, int r)
{
if (p < r)
{
int i = Partion(array, p, r);
Quicksort(array, p, i - 1);
Quicksort(array, i + 1, r);
}
}
void ArrayPrint(int *Array,int n)
{
int i;
for (i = 0; i < n; i++) {
cout << *(Array + i) << "\t";
}
cout << endl;
}
int main()
{
int Array[] = { 25, 3, 56, 7, 83, 4, 5, 65, 9, 10 };
int length = sizeof(Array) / sizeof(int);
cout << " " << endl;
ArrayPrint(Array, length);
Quicksort(Array, 0, length - 1);
cout << " " << endl;
ArrayPrint(Array, length);
return 0;
}
3.泡立ちソート
/*
* bubblesort.c
*
* Created on: 2012-3-16
* Author: sangerhoo
*/
#include<stdio.h>
#include<stdlib.h>
void bubblesort(int *arry,int n)
{
int a,i,j;
for (i=n-1;i>0;i--)
{
for(j=0;j<i;j++)
{
if(*(arry+j)>*(arry+j+1))
{
a=*(arry+j);
*(arry+j)=*(arry+j+1);
*(arry+j+1) =a;
}
}
}
}
void main()
{
int arry[8]={5,9,4,1,7,6,3,2};
int i;
printf("
");
for(i=0;i<8;i++)
{
printf("%d",*(arry+i));
}
printf("
");
bubblesort(arry,8);
printf("
");
for(i=0;i<8;i++)
{
printf("%d",*(arry+i));
}
printf("
");
}
4.ソートの選択
/*
* SelectSort.c
*
* Created on: 2012-3-17
* Author: sangerhoo
*/
#include<stdio.h>
#include<stdlib.h>
void SelectSort(int *array,int n)
{
int i,j,m,a;
for(i=0;i<n-1;i++)
{
m=i;
for(j=i+1;j<n;j++){
if(*(array+j) < *(array+m))
m=j;
}
if(m!=i)
{
a=*(array+m);
*(array+m)=*(array+i);
*(array+i)=a;
}
}
}
void main()
{
int array[]={12,34,67,8,23,90};
int i;
int n= sizeof(array)/sizeof(int);
printf("n=%d",n);
printf("
");
for(i=0;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
SelectSort(array,n);
printf("
");
printf("n=%d
",n);
for(i=0;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
}
5.
/*
* InsertSort.c
*
* Created on: 2012-3-17
* Author: sangerhoo
*/
#include<stdio.h>
#include<stdlib.h>
void InsertSort(int *array,int n)
{
int i,j,tmp;
for(i=0;i<n;i++)
{
j=i+1;
tmp=*(array+j);
while(j!=0 && tmp>*(array+j-1))
{
*(array+j)=*(array+j-1);
j--;
}
*(array+j)=tmp;
}
}
void main()
{
int array[]={12,34,67,8,23,90,10};
int i;
int n= sizeof(array)/sizeof(int);
printf("n=%d",n);
printf("
");
for(i=0;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
InsertSort(array,n);
printf("
");
printf("n=%d
",n);
for(i=0;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
}
6.Shellソート/*
* ShellSort.c
*
* Created on: 2012-3-17
* Author: sangerhoo
*/
#include<stdio.h>
#include<stdlib.h>
void ShellInsert(int *array, int step, int n) {
int i, j, key;
for (i = step; i <n; i++) {
if (*(array + i) < *(array + i - step)) {
key = *(array + i);
j = i - step;
do {
*(array + j + step) = *(array + j);
j -= step;
} while (j > 0 && key<*(array + j));
*(array + j + step) = key;
}
}
}
void ShellSort(int *array, int n) {
int addtion = n;
do {
addtion = addtion / 3 + 1;
ShellInsert(array, addtion, n);
} while (addtion > 1);
}
void main() {
int array[] = { 12, 34, 67, 8, 23, 90, 10 };
int i;
int n = sizeof(array) / sizeof(int);
printf("n=%d", n);
printf("
");
for (i = 0; i < n; i++) {
printf("%d \t", array[i]);
}
printf("
");
ShellSort(array, n);
/*ShellInsert(array,3, n);*/
printf("
");
printf("n=%d
", n);
for (i = 0; i < n; i++) {
printf("%d \t", array[i]);
}
printf("
");
}
7.
/*
* HeapSort.c
*
* Created on: 2012-3-17
* Author: sangerhoo
*/
#include<stdio.h>
#include<stdlib.h>
int count =1;
void Restore(int *array,int i,int n)
{
int j,k,r;
int done=0;
k=r=*(array+i);
j=2*i;
while((j<n) && (done == 0))
{
if(j<n)
{
if(*(array+j)<*(array+j+1))
{
j++;
}
}
if(k>=*(array+j))
{
done=1;
}
else
{
*(array+j/2)=*(array+j);
j*=2;
}
}
*(array+j/2)=r;
}
void HeapSort(int *array,int n)
{
int i,j,t;
for(i=n/2;i>0;i--)
Restore(array,i,n);
for(i=n-1;i>0;i--)
{
t=*(array+i+1);
*(array+i+1)=*(array+1);
*(array+1)=t;
Restore(array,1,i);
}
}
void main()
{
int array[]={0,12,34,67,8,23,90,10};//array[0]
int i;
int n= sizeof(array)/sizeof(int);
printf("n=%d",n);
printf("
");
for(i=1;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
HeapSort(array,n-1);
printf("
");
printf("n=%d
",n);
for(i=1;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
}
8.
/*
* MergerSort.c
*
* Created on: 2012-3-17
* Author: sangerhoo
*/
#include<stdlib.h>
#include<stdio.h>
void merger(int *array,int l,int m,int r)
{
int na=m-l+1;
int nb=r-m;
int array_a[na];
int array_b[nb];
int i,j=0,k=0;
for(i=0;i<na;i++)
{
*(array_a+i)=*(array+l+i);
}
for(i=0;i<nb;i++)
{
*(array_b+i)=*(array+m+1+i);
}
for(i=0;i<r;i++)
{
//*(array+l+i)=(*(array_a+j)>*(array_b+k) ? *(array_a+j++) : *(array_b+k++) );
if(*(array_a+j)>*(array_b+k))
{
*(array+l+i)=*(array_a+j);
j++;
}
else
{
*(array+l+i)=*(array_b+k);
k++;
}
if(j>=na)
{
i++;
break;
}
if(k>=nb)
{
i++;
break;
}
}
while(j<na)
{
*(array+l+i)=*(array_a+j);
i++;
j++;
}
while(k<nb)
{
*(array+l+i)=*(array_b+k);
i++;
k++;
}
}
void mergersort(int *array,int l,int r)
{
int mid=0;
if(l<r)
{
mid=(l+r)/2;
mergersort(array,l,mid);
mergersort(array,mid+1,r);
merger(array,l,mid,r);
}
}
void main()
{
int array[]={12,34,67,8,23,90,10,3};
int i;
int n= sizeof(array)/sizeof(int);
printf("n=%d",n);
printf("
");
for(i=0;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
mergersort(array,0,n-1);
printf("
");
printf("n=%d
",n);
for(i=0;i<n;i++)
{
printf("%d \t",array[i]);
}
printf("
");
}