- PDF 無料ダウンロード

Size: px

Start display at page:

Download ""

しゅんすけだいほうじ
5 years ago
Views:

22 /* max-heap property */ void insert(int val, int heap[], int counter) { int i = counter + 1; while( (i!= 1) && (heap[i/2] < val) ) { heap[i] = heap[i/2]; i = i/2; heap[i] = val; def insert(val, heap, counter): i = counter while ((i!= 1) and (heap[i/2] < val)): heap[i] = heap[i/2] i = i / 2 heap[i] = val

27 public class LinearSearch { /** * */ public static int execute(int[] data, int target) { int notfound = -1; // for(int i = 0; i < data.length; i++) { if (data[i] == target) { return i; // return notfound; public static void main(string[] args) { int[] data = {1,2,3,4,5; // int result; // ``3'' result = LinearSearch.execute(data, 3); if (result!= -1) { System.out.println("Found: index key = " + result); else { System.out.println("Not found."); #include <stdio.h> #define ARRAY_SIZE (8) /* size of array */

28 int main(void) { int array[array_size] = {9, 7, 18, 20, 8, 39, 77, 35; int key; int i; puts("find value?"); scanf("%d", &key); for (i = 0; i < ARRAY_SITE; ++i) { if (array[i] == key) { puts("found!\n"); return 0; puts("not Found.\n"); return 0; def linear_search(alist, val): for x in alist: if x == val: return True return False if name == ' main ': from random import shuffle l = range(15) v = raw_input('find value? ') r = linear_search(l, int(v)) if r: print('found!') else: print('not Found!')

31 #include <stdio.h> #define ARRAY_SIZE 7 /* size of array */ int main(void) { int a[array_size] = {1,2,3,4,5,6,7; /* sorted array */ int left = 0; /* start key of index */ int right = ARRAY_SIZE; /* end key of index */ int mid; /* middle key of index */ int value; /* search value */ puts("find value?"); scanf("%d", &value); while(left <= right) { mid = (left + right) / 2; /* calc of middle key */ if (a[mid] == value) { puts("found!\n"); return 0; else if (a[mid] < value) { left = mid + 1; /* adjustment of left(start) key */ else { right = mid - 1; /* adjustment of right(end) key */ puts("not Found.\n"); return 0; def binary_search(l, value): low = 0 high = len(l) - 1 while low <= high: mid = (low + high) // 2 if l[mid] == value: print('found') return True elif l[mid] < value: low = mid + 1 else: high = mid - 1

32 print('not Found') return False # # main # if name == ' main ': import sys l = xrange(20) for num in l: assert binary_search(l, num) assert binary_search(l, -50) == False assert binary_search(l, -50) == False assert binary_search(l, 20) == False assert binary_search(l, 19) == True assert binary_search(l, 0) == True assert binary_search([1,2,4,12,67,90], 3) == False

36 void bubblesort(int numbers[], int array_size) { int i, j, temp; for (i = 0; i < (array_size - 1); i++) { for (j = (array_size - 1); j > i; j--) { if (numbers[j-1] > numbers[j]) { temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp; def bubblesort(l): for index in xrange(len(l)-1, 0, -1): for low in xrange(index): if l[low] > l[low+1]: tmp = l[low+1] l[low+1] = l[low] l[low] = tmp return l

37 if name == ' main ': from random import shuffle l = range(15) lcopy = l[:] shuffle(l) print('unsorted') print l assert l!= lcopy print ('Sorted') print bubblesort(l) assert l == lcopy

40 /* * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA USA * * This program demonstrates the use of the selection sort algorithm. For * more information about this and other sorting algorithms, see * * */ #include <stdlib.h> #include <stdio.h> #include <unistd.h> #define NUM_ITEMS 100 void selectionsort(int numbers[], int array_size); int numbers[num_items]; int main() { int i; // seed random number generator srand(getpid()); // fill array with random integers for (i = 0; i < NUM_ITEMS; i++) { numbers[i] = rand();

41 // perform selection sort on array selectionsort(numbers, NUM_ITEMS); printf("done with sort.\n"); for (i = 0; i < NUM_ITEMS; i++) { printf("%i\n", numbers[i]); return 0; void selectionsort(int numbers[], int array_size) { int i; // int j; // int min; // int temp; // for (i = 0; i < array_size-1; i++) { min = i; // for (j = i+1; j < array_size; j++) { // if (numbers[j] < numbers[min]) { min = j; // // temp = numbers[i]; numbers[i] = numbers[min]; numbers[min] = temp; def selectionsort(l): n = len(l) for index in xrange(n-1): least = index for x in xrange(index + 1, n): if l[x] < l[least]: least = x tmp = l[index]

42 l[index] = l[least] l[least] = tmp return l if name == ' main ': from random import shuffle l = range(15) lcopy = l[:] shuffle(l) print('unsorted') print l assert l!= lcopy print ('Sorted') print selectionsort(l) assert l == lcopy

45 void insertionsort(int numbers[], int array_size) { int i, j; for (i=1; i < array_size; i++) { // j = i; // // while ((j > 0) && (numbers[j-1] > numbers[j])) { // swap(&numbers[j-1], &numbers[j]); // j--; void swap(int *p_from, int *p_to) { int tmp; tmp = *p_from; *p_from = *p_to; *p_to = tmp;

46 def insertionsort_shift( alist ): for right in range( 1, len( alist ) ): key = alist[right] left = right while left > 0 and key < alist[left - 1]: alist[left] = alist[left - 1] left -= 1 alist[left] = key return alist def insertionsort_swap( alist ): for right in range( 1, len( alist ) ): left = right while left > 0 and alist[left] < alist[left - 1]: alist[left - 1], alist[left] = alist[left], alist[left - 1] left -= 1 return alist if name == ' main ': from random import shuffle l = range(15) lcopy = l[:] shuffle(l) print('unsorted') print l assert l!= lcopy print ('Sorted') print insertionsort_shift(l) assert l == lcopy

49 void shellsort(int numbers[], int array_size) { int i, j, increment, temp; increment = 4; while (increment > 0) { for (i=0; i < array_size; i++) { j = i; temp = numbers[i]; while ((j >= increment) && (numbers[j-increment] > temp)) { numbers[j] = numbers[j - increment]; j = j - increment; numbers[j] = temp; if (increment/2!= 0) increment = increment/2; else if (increment == 1) increment = 0; else increment = 1;

50 def shellsort_shift(alist): gap = len(alist) // 2 while gap > 0: for right in range(gap, len(alist)): key = alist[right] left = right while left >= gap and key < alist[left - gap]: alist[left] = alist[left - gap] left -= gap alist[left] = key gap //= 2 return alist def shellsort_swap( alist ): gap = len(alist) // 2 while gap > 0: for right in range(gap, len(alist)): left = right while left >=gap and alist[left] < alist[left - gap]: alist[left - gap], alist[left] = alist[left], alist[left - gap] left -= gap gap //= 2 return alist if name == ' main ': from random import shuffle l = range(15) lcopy = l[:] shuffle(l) print 'Unsorted' print l assert l!= lcopy print 'Sorted' print shellsort_shift(l) assert l == lcopy

53 def quicksort(seq): if len(seq) < 1: return seq pivot = seq[0] left = [] right = [] for x in range(1, len(seq)): if seq[x] <= pivot: left.append(seq[x]) else: right.append(seq[x]) left = quicksort(left) right = quicksort(right) foo = [pivot] return left + foo + right void q_sort(int numbers[], int left, int right) { int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = numbers[left]; while (left < right) { while ((numbers[right] >= pivot) && (left < right)) right--; if (left!= right) { numbers[left] = numbers[right]; left++; while ((numbers[left] <= pivot) && (left < right)) left++; if (left!= right) {

54 numbers[right] = numbers[left]; right--; numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot) q_sort(numbers, left, pivot-1); if (right > pivot) q_sort(numbers, pivot+1, right);

57 void mergesort(int numbers[], int temp[], int array_size) { m_sort(numbers, temp, 0, array_size - 1); void m_sort(int numbers[], int temp[], int left, int right) { int mid; if (right > left) { mid = (right + left) / 2; /* */ m_sort(numbers, temp, left, mid); m_sort(numbers, temp, mid+1, right); merge(numbers, temp, left, mid+1, right); void merge(int numbers[], int temp[], int left, int mid, int right) { int i, left_end, num_elements, tmp_pos; left_end = mid - 1; tmp_pos = left; num_elements = right - left + 1; /* */ /* 2 */ while ((left <= left_end) && (mid <= right)) { if (numbers[left] <= numbers[mid]) { temp[tmp_pos] = numbers[left]; tmp_pos = tmp_pos + 1; left = left +1; else {

58 temp[tmp_pos] = numbers[mid]; tmp_pos = tmp_pos + 1; mid = mid + 1; /* */ while (left <= left_end) { temp[tmp_pos] = numbers[left]; left = left + 1; tmp_pos = tmp_pos + 1; /* */ while (mid <= right) { temp[tmp_pos] = numbers[mid]; mid = mid + 1; tmp_pos = tmp_pos + 1; /* */ for (i=0; i <= num_elements; i++) { numbers[right] = temp[right]; right = right - 1; def merge_sort(alist): if len(alist) <= 1: return alist mid = len(alist) // 2 left = alist[:mid] right = alist[mid:] left = merge_sort(left) right = merge_sort(right) return list(merge(left, right))

59 def merge(left, right): sorted_list = [] left_index = 0 right_index = 0 while left_index < len(left) and right_index < len(right): if left[left_index] <= right[right_index]: sorted_list.append(left[left_index]) left_index += 1 else: sorted_list.append(right[right_index]) right_index += 1 if left: sorted_list.extend(left[left_index:]) if right: sorted_list.extend(right[right_index:]) return sorted_list if name == ' main ': from random import shuffle l = range(15) lcopy = l[:] shuffle(l) print('unsorted') print l assert l!= lcopy print ('Sorted') l = merge_sort(l) print l assert l == lcopy

62 /* * numbers array_size */ void heap_sort(int* numbers, int array_size) { int i, temp; // // // (n - 1) / 2 for (i = (array_size - 1) / 2; i >= 0; i--) { max_heap(numbers, i, array_size - 1); // // // // () // // for (i = array_size - 1; i > 0; i--) { temp = numbers[0]; numbers[0] = numbers[i]; numbers[i] = temp; max_heap(numbers, 0, i - 1); /* * Max-heap *

63 * * numbers root bottom */ void max_heap(int* numbers, int root, int bottom) { // int child = (2 * root) + 1; // int temp = numbers[root]; while (child <= bottom) { if (child < bottom && numbers[child + 1] > numbers[child]) { // child = child + 1; if (temp > numbers[child]) { // break; else if (temp <= numbers[child]) { // // numbers[(child - 1) / 2] = numbers[child]; // child = (2 * child) + 1; // numbers[(child - 1) / 2] = temp; return; /* * Max-heap * */ void max_heap_recursive(int* numbers, int root, int bottom) { //

64 // 0 // 2n + 1 2n + 2 int l_idx = (root * 2) + 1; int r_idx = (root * 2) + 2; // int maxchild; if (l_idx <= bottom && numbers[l_idx] > numbers[root]) { maxchild = l_idx; else { maxchild = root; if (r_idx <= bottom && numbers[r_idx] > numbers[maxchild]) { maxchild = r_idx; if (maxchild!= root) { int temp = numbers[root]; numbers[root] = numbers[maxchild]; numbers[maxchild] = temp; // max_heap_recursive(numbers, maxchild, bottom); def heapsort(alist): list_size = len(alist) - 1 for i in range((list_size / 2), -1, -1): sift_down(alist, i, list_size) for i in range(list_size, 0, -1): if alist[0] > alist[i]: temp = alist[0] alist[0] = alist[i] alist[i] = temp sift_down(alist, 0, i - 1) return alist # end def heapsort

65 def sift_down(alist, root, bottom): left = root * right = root * if left <= bottom and alist[left] > alist[root]: max_child = left else: max_child = root if right <= bottom and alist[right] > alist[max_child]: max_child = right if max_child!= root: alist[root], alist[max_child] = alist[max_child], alist[root] sift_down(alist, max_child, bottom) # end def sift_down if name == ' main ': from random import randint l = [randint(0,999) for i in range(7)] print('unsorted') print l print ('Sorted') print heapsort(l)

68 #define M 10 /* */ /** * numbers[] * number_of_item numbers */ void bucket_sort(int numbers[], int number_of_item) { int buckets[m]; int i; /* */ /* prepare buckets */ for (i = 0; i < M; i++) { buckets[i] = 0; /* putting in bucket */ for (i = 0; i < number_of_item; i++) { buckets[numbers[i]] = numbers[i]; /* back into the original array */ int j = 0; /* */ for (i = 0; i < M; i++) { if (0 < buckets[i]) { numbers[j++] = buckets[i];

69 MIN_BUCKET = 0 MAX_BUCKET = 15 def bucket_sort(alist): buckets = list() for i in range(min_bucket, MAX_BUCKET + 1): buckets.append(none) for i in alist: buckets[alist[i]] = alist[i] x = 0 for i in range(min_bucket, MAX_BUCKET + 1): if buckets[i] is not None: alist[x] = buckets[i] x += 1 return alist if name == ' main ': from random import shuffle l = range(15) lcopy = l[:] shuffle(l) print('unsorted') print l assert l!= lcopy print ('Sorted') l = bucket_sort(l) print l assert l == lcopy

73 /* 0M */ #define M 10 /* (N ) */ int work_data[n-1]; /* */ int count[m+1]; /* int int int n */ void counting_sort(int a[], int b[], int n) { int i; /* () */ for (i = 0; i <= M; i++) count[i] = 0; /* */ for (i = 0; i < n; i++) count[a[i]]++; /* */ for (i = 0; i < M; i++) { count[i+1] += count[i];

74 /* ab */ for (i = n - 1; i >= 0; i--) { b[--count[a[i]]] = a[i]; def counting_sort(array, maxval): m = maxval + 1 count = [0] * m for a in array: count[a] += 1 i = 0 for a in range(m): # # # for c in range(count[a]): # array[i] = a i += 1 return array if name == ' main ': from random import shuffle maxval = 15 l = [1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 8, 10, 10, 12, 14, 14, 15] lcopy = l[:] shuffle(l) print('unsorted') print l assert l!= lcopy print ('Sorted') print counting_sort(l, maxval) assert l == lcopy

PFS-Readme

PFS-Readme Cell Storage Service : Storage Service that has the high reliability and the high availability by Paxos consensus algorithm. CSS-Readme.txt : This manual describes the process to make the envirornments