C言語の練習

Cはもうほとんど忘れてしまっているので、復習をかねて昔読んだアルゴリズムの本の問題をやってみようと思った。

• bubble sort

#include <stdio.h>

void swap( int *a, int *b);
void bubbleSort( int *a, int length );

void bubbleSort( int *a, int length ) {
	for(int i=length-1; i>0; i--) {
		for(int j=0; j<i; j++){
			if(a[j] > a[j+1]) swap(a+j, a+j+1);
		}
	}
}

inline void swap( int *a, int *b ){
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main(int *argv, int args) {
	int a[] = {5,4,3,2,1};
	bubbleSort( a, 5 );
	
	for(int i=0; i<5; i++) {
		printf("a[%d]: %d\n", i, a[i]);
	}
	
	return 0;
}

• selection sort

#include <stdio.h>

void swap( int *a, int *b);
void selectionSort( int *a, int length );

void selectionSort( int *a, int length ) {
	for(int i=0; i<length-1; i++) {
		int min_index=i;
		for(int j=i+1; j<length; j++){
			if(a[min_index]>a[j]) min_index=j;
		}
		swap( a+i, a+min_index );
	}
}

inline void swap( int *a, int *b ){
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main(int *argv, int args) {
	int a[] = {4,3,1,12, 15, 20, 2, 5};
	selectionSort( a, 5 );
	
	for(int i=0; i<5; i++) {
		printf("a[%d]: %d\n", i, a[i]);
	}
	
	return 0;
}

• selection sort

#include <stdio.h>

void swap( int *a, int *b);
void selectionSort( int a[], int length );
void shift( int a[], int start, int end );

void selectionSort( int a[], int length ) {
       for(int i=1; i<length; i++) {
               int tmp=a[i];
               for(int j=0; j<i; j++){
                       if( a[j] > tmp ) {
                               shift(a, j, i-1);
                               a[j] = tmp;
                               break;
                       }
               }
       }
}

void shift( int a[], int start, int end ){
       for( int i=end; start<=i; i-- ){
               a[i+1] = a[i];
       }
}

inline void swap( int *a, int *b ){
       int tmp = *a;
       *a = *b;
       *b = tmp;
}

int main(int *argv, int args) {
       int a[] = {4,3,1,12, 15, 20, 2, 5};
       selectionSort( a, 5 );

       for(int i=0; i<5; i++) {
               printf("a[%d]: %d\n", i, a[i]);
       }

       return 0;
}

• stack class

push, pop, peek

• queue class

insert, delete, peek

• circular queue class

• priority queue class

insert, delete, peek

• InToPost 関数

中値記法をReverse Polish Notation に変換する。