Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.



 
Trang ChínhTrang Chính  Tìm kiếmTìm kiếm  Latest imagesLatest images  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

 

 bai tap thay nam

Go down 
Tác giảThông điệp
lemon
Vịt con
Vịt con
lemon


Tổng số bài gửi : 2
Cảm ơn : 6
Danh vọng : 0
Join date : 01/03/2011

bai tap thay nam Empty
03072011
Bài gửibai tap thay nam

Code:
/* This file contains a collection of sorting routines */

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

void Swap(int *Lhs, int *Rhs)
{
    int Tmp = *Lhs;
    *Lhs = *Rhs;
    *Rhs = Tmp;
}

void InterchangeSort(int A[], int N)
{
    int i, j;

    for (i = 0; i < N-1; i++)
        for (j = i+1; j < N; j++)
        {
            if (A[i] > A[j])
                Swap(&A[i], &A[j]);
        }
}

void InsertionSort(int A[], int N)
{
    int j, P;
    int Tmp;

    for(P = 1; P < N; P++)
    {
        Tmp = A[P];
        for(j = P; j > 0 && A[j - 1] > Tmp; j--)
            A[j] = A[j - 1];
        A[j] = Tmp;
    }
}

void Shellsort(int A[], int N)
{
    int i, j, Increment;
    int Tmp;

    for(Increment = N / 2; Increment > 0; Increment /= 2)
        for(i = Increment; i < N; i++)
        {
            Tmp = A[i];
            for(j = i; j >= Increment; j -= Increment)
                if(Tmp < A[j - Increment])
                    A[j] = A[j - Increment];
                else
                    break;
            A[j] = Tmp;
        }
}

int Partition(int a[], int low, int high)
{
    int left, right;
    int pivot_item;
    pivot_item = a[low];
    left = low;
    right = high;
    while (left < right)
    {
        /* Move left while item < pivot */
        while(a <= pivot_item)
            left++;
        /* Move right while item > pivot */
        while(a[right] > pivot_item)
            right--;
        if (left < right)
            Swap(&a, &a[right]);
    }
    /* right is final position for the pivot */
    a[low] = a[right];
    a[right] = pivot_item;
    return right;
}

void Qsort(int a[], int low, int high)
{
    int pivot;
    /* Termination condition! */
    if (high > low)
    {
        pivot = Partition(a, low, high);
        Qsort(a, low, pivot-1);
        Qsort(a, pivot+1, high);
    }
}

void Quicksort(int A[], int N)
{
    Qsort(A, 0, N - 1);
}


void Permute(int A[], int N)
{
    int i;

    for(i = 0; i < N; i++)
        A[i] = i;
    for(i = 1; i < N; i++)
        Swap(&A[i], &A[rand() % (i + 1)]);
}

void Checksort(int A[], int N)
{
    int i;
    for(i = 0; i < N; i++)
        if(A[i] != i)
            printf("Sort fails: %d %d\n", i, A[i]);
    printf("Check completed\n");
}

void Copy(int Lhs[], const int Rhs[], int N)
{
    int i;
    for(i = 0; i < N; i++)
        Lhs[i] = Rhs[i];
}

/*
#define MaxSize 100000
int Arr1[MaxSize];
int Arr2[MaxSize];
*/

int* CreateArray(int n)
{
    int* pArray = new int[n];

    return pArray;
}

int BinarySearch(int* pArray, int n, int key)
{
    int lo = 0, hi = n-1;
    int mid;

    while (lo <= hi)
    {
        mid = (lo+hi)/2;
        if (pArray[mid] > key)
        {
            hi = mid-1;
        }
        else
        {
            if (pArray[mid] < key)
            {
                lo = mid+1;
            }
            else
            {
                return mid;
            }
        }
    }
    return -1;
}

void DestroyArray(int* pArray)
{
    if (pArray)
    {
        delete []pArray;
    }
}

main()
{
    clock_t s, e;
    int MaxSize = 1000000;

    int *Arr1, *Arr2;

    Arr1 = CreateArray(MaxSize);
    Arr2 = CreateArray(MaxSize);

    Permute(Arr2, MaxSize);
 /* 
    Copy(Arr1, Arr2, MaxSize);
    s = clock();
    InterchangeSort(Arr1, MaxSize);
    e = clock();
    Checksort(Arr1, MaxSize);
    printf("interchange sort: %lf\n", ((double)e-s)/CLK_TCK);
*/
    Copy(Arr1, Arr2, MaxSize);
    s = clock();
    InsertionSort(Arr1, MaxSize);
    e = clock();
    Checksort(Arr1, MaxSize);
    printf("insertion sort %lf\n", ((double)e-s)/CLK_TCK);

    Copy(Arr1, Arr2, MaxSize);
    s = clock();
    Shellsort(Arr1, MaxSize);
    e = clock();
    Checksort(Arr1, MaxSize);
    printf("shell sort: %lf\n", ((double)e-s)/CLK_TCK);
/*
    Copy(Arr1, Arr2, MaxSize);
    s = clock();
    Quicksort(Arr1, MaxSize);
    e = clock();
    Checksort(Arr1, MaxSize);
    printf("quick sort: %lf\n", ((double)e-s)/CLK_TCK);
*/
    getch();

    return 0;
}
bai tap thay nam 432691
Về Đầu Trang Go down
Share this post on: reddit

bai tap thay nam :: Comments

No Comment.
 

bai tap thay nam

Về Đầu Trang 

Trang 1 trong tổng số 1 trang

 Similar topics

-
» Bài Tâp t4 26/1 của thầy Đại[sr vì post trễ]

Permissions in this forum:Bạn không có quyền trả lời bài viết
 :: Cơ sở lập trình 2-
Chuyển đến