ソートアルゴリズムの実装


1.ソートの挿入
アルゴリズム導論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("
"); }