Last active
April 4, 2016 03:23
-
-
Save akkijp/2743d3ecc687c4fd399e to your computer and use it in GitHub Desktop.
挿入ソート、バブルソート、クイックソートの各種アルゴリズムソースコード(計測用main関数も付属)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <time.h> | |
void swap(int *p_from, int *p_to) { | |
int tmp; | |
tmp = *p_from; | |
*p_from = *p_to; | |
*p_to = tmp; | |
} | |
// 挿入ソート | |
void insertionSort(int arr[], int data_size){ | |
int i, j, tmp; | |
for(i=0; i<data_size; i++){ | |
j = i; | |
while( (j>0) && (arr[j-1]>arr[j]) ){ | |
swap(&arr[j-1], &arr[j]); | |
j--; | |
} | |
} | |
} | |
//バブルソート | |
void bubbleSort(int arr[], int data_size){ | |
int i, j, tmp; | |
for(i=0; i<(data_size-1); i++){ | |
for(j=(data_size-1); j>i; j--){ | |
if(arr[j-1]>arr[j]){ | |
swap(&arr[j-1], &arr[j]); | |
} | |
} | |
} | |
} | |
// クイックソート | |
void q_main(int arr[], int left, int right){ | |
int pivot; | |
int left_hold; | |
int right_hold; | |
int tmp; | |
pivot = arr[left]; | |
if(left < right){ | |
left_hold = left; | |
right_hold = right; | |
while(-1){ | |
while(arr[left_hold] < pivot) left_hold++; | |
while(pivot < arr[right_hold]) right_hold--; | |
if(left_hold >= right_hold) break; | |
swap(&arr[left_hold], &arr[right_hold]); | |
left_hold++; | |
right_hold--; | |
} | |
q_main(arr, left, left_hold - 1); | |
q_main(arr, right_hold + 1, right); | |
} | |
} | |
void quickSort(int arr[], int data_size){ | |
q_main(arr, 0, data_size-1); | |
} | |
// 確認用出力関数 | |
void printArray(int arr[], int data_size){ | |
int k; | |
for(k=0; k<data_size; k++){ | |
printf("%d\n", arr[k]); | |
} | |
} | |
int main(){ | |
int i; | |
int data[10000]; | |
int data_size; | |
int start, end; | |
int count; | |
printf("データサイズを入力>>> "); | |
scanf("%d", &data_size); | |
start = clock(); | |
for(count=1; count <= 10000; count++){ | |
srand((unsigned)time(NULL)); | |
for(i=0; i<data_size; i++){ | |
data[i] = rand(); | |
} | |
insertionSort(data, data_size); | |
// bubbleSort(data, data_size); | |
// quickSort(data, data_size); | |
} | |
end = clock(); | |
printf("処理に要した時間は[%f秒]\n", (end-start)/ (double)CLOCKS_PER_SEC); | |
// printArray(data, data_size); | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment