Trang ChínhTrang Chính  CalendarCalendar  Trợ giúpTrợ giúp  Tìm kiếmTìm kiếm  Thành viênThành viên  NhómNhóm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Hãy sử dụng FireFox để web hiển thị tốt hơn!


Share | 
 

 bai tap thay nam

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
lemon
Vịt con
Vịt con
avatar

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

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;
}
Về Đầu Trang Go down
Xem lý lịch thành viên

 Similar topics

-
» -0936175427-Vệ sinh máy lạnh tại nhà quận 8,THẾ VINH UY TÍN call:0862786708,Thay thế block máy lạnh giá rẽ quận 8,Vệ sinh máy lạnh tại nhà quận 8,Vệ sinh máy lạnh tại nhà quận 8,Vệ sinh máy lạnh tại n
» -0936175427-Vệ sinh máy lạnh tại nhà quận 5,THẾ VINH UY TÍN call:0862786708,Thay thế block máy lạnh giá rẽ quận 5,Vệ sinh máy lạnh tại nhà quận 5,Vệ sinh máy lạnh tại nhà quận 5,Vệ sinh máy lạnh tại n
» Giấc mơ chung cư thay thế nỗi buồn nhà phố
» Giảm ngay 30% đèn LED tiết kiệm 70% điện
» Thông Báo Có Sự Thay Đổi Số Lượng Bài Dự Thi
Share this post on: diggdeliciousredditstumbleuponslashdotyahoogooglelive

bai tap thay nam :: Comments

No Comment.
 

bai tap thay nam

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 

Trang 1 trong tổng số 1 trang

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