21110327 algorithm design

Algorithm Page Created By Tata201201

Source Code Based on C++

Divide and Conquer

Interesting Problems

• คู่ตัวเลขเด่น (pair)

Merge Sort

• ตั้งแต่สมัยเข้าค่าย สอวน. ค่าย 2

#include<stdio.h>
#include<stdlib.h>
int n,seq[100000],tm[100000];
void merge(int lb,int ub){
    if(lb>=ub) return;
    int mid=(ub+lb)/2,i,j;
    merge(lb,mid);
    merge(mid+1,ub);
    int runa=lb,runb=lb,runc=mid+1;
    while(runb<=mid&&runc<=ub){
        if(seq[runb]<=seq[runc]){
            tm[runa]=seq[runb];
            runb++;
        }else{
            tm[runa]=seq[runc];
            runc++;
        }
        runa++;
    }
    while(runb<=mid){
        tm[runa]=seq[runb];
        runa++;
        runb++;
    }
    while(runc<=ub){
        tm[runa]=seq[runc];
        runa++;
        runc++;
    }
    for(i=lb;i<=ub;i++){
        seq[i]=tm[i];
    }
}
int main(){
    printf("Enter numbers of input : ");
    scanf("%d",&n);
    int i;
    printf("Enter %d numbers : ",n);
    for(i=0;i<n;i++){
        scanf("%d",&seq[i]);
    }
    merge(0,n-1);
    printf("\nSorted sequence is : ");
    for(i=0;i<n;i++){
        printf("%d ",seq[i]);
    }
    
    
    
    scanf(" ");
    return 0;
}

Quick Sort

• ตั้งแต่สมัยเข้าค่าย สอวน. ค่าย 2

#include<stdio.h>
int n,seq[100000];
void swap(int x,int y){
    int temp=seq[x];
    seq[x]=seq[y];
    seq[y]=temp;
}
void quick(int lb,int ub){
    if(lb>=ub) return;
    int piv=seq[lb],back=lb,i;
    for(i=lb+1;i<=ub;i++){
        if(seq[i]<piv){
            back++;
            swap(back,i);
        }
    }
    swap(back,lb);
    quick(lb,back-1);
    quick(back+1,ub);
}
int main(){
    printf("Enter numbers of input : ");
    scanf("%d",&n);
    int i;
    printf("Enter %d numbers : ",n);
    for(i=0;i<n;i++){
        scanf("%d",&seq[i]);
    }
    quick(0,n-1);
    printf("\nSorted sequence is : ");
    for(i=0;i<n;i++){
        printf("%d ",seq[i]);
    }
    scanf(" ");
    return 0;
}