Demo entry 6645255

PJ1

   

Submitted by Inuyasha on Oct 09, 2017 at 16:16
Language: C. Code size: 3.2 kB.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define K 10000
#define SIZE 10000
clock_t start, stop;
double duration;
int array[SIZE];

int main()
{
    fillArray();

    int performanceType = 1;
    int i, n, judge, array_size;
    scanf("%d", &n);
    while(performanceType <= 4)
    {
        start = clock();
        switch(performanceType)
        {
            case 1: 
                printf("Binary Search (iterative version)\n");
                for(i = 1; i <= K; i++)
                    judge = iteBinary(array, SIZE, n);
                judge == -1 ? printf("No\n"): printf("Yes\n");
                break;
            case 2: 
                printf("Binary Search (recursive version)\n");
                for(i = 1; i <= K; i++)
                    judge = recBinary(array, 0, SIZE - 1, n);
                judge == -1 ? printf("No\n"): printf("Yes\n");
                break;         
            case 3: 
                printf("Sequential Search (iterative version)\n");
                for(i = 1; i <= K; i++)
                    judge = iteSequential(array, SIZE, n);
                    judge == -1 ? printf("No\n"): printf("Yes\n");
                break;
            case 4: 
                printf("Sequential Search (recursive version)\n");
                for(i = 1; i <= K; i++)
                    judge = recSequential(array, 0, SIZE - 1, n);
                    judge == -1 ? printf("No\n"): printf("Yes\n");
                break;
        }
        stop = clock();

        duration = ((double)(stop - start)) / CLK_TCK;
        printf("Iterations\t%d\n", K);
        printf("Ticks\t\t%d\n", stop - start);
        printf("Total Time\t%f\n", duration);
        printf("Duration\t%f\n\n", duration / K);
        performanceType++;
    }

    return 1;
}

int iteBinary(int *array, int array_size, int n)
{
    int low = 0, high = array_size - 1, mid;
    while(low <= high)
    {
        mid = low + (high - low) / 2;
        if(array[mid] == n)
            return mid;
        else if(array[mid] > n)
            high = mid - 1;
        else   
            low = mid + 1;
    }
    return -1;
}

int recBinary(int *array, int low, int high, int n)
{
    int mid;
    if(array == NULL || high < low)
        return -1;
    if(low <= high)
    {
        mid = low + (high - low) / 2;
        if(array[mid] == n)
            return mid;
        else if(array[mid] > n)
            return recBinary(array, low, mid - 1, n);
        else   
            return recBinary(array, mid + 1, high, n);
    }
    return -1;
}

int iteSequential(int *array, int array_size, int n)
{
	int i;
    for(i = 0; i < array_size; i++)
    {
        if(array[i] == n)
            return i;
    }
    return -1;
}

void recSequential(int *array, int low, int high, int n)
{
    if(array == NULL || high < low)
        return -1;
    if(low <= high)
    {
        if(array[low] == n)
            return low;
        else
            return recSequential(array, low + 1, high, n); 
    }
    return -1;
}

void fillArray()
{
	int i;
    for(i = 0; i < SIZE; i++)
        array[i] = i;
    return;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).