When we control the event,we control your lives
 
IndexTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập
Tìm kiếm
 
 

Display results as :
 
Rechercher Advanced Search
Latest topics
» Tô màu theo vùng quét
Tue Aug 13, 2013 4:18 pm by minhlap

» authentischen Hermes Lindy Taschen
Wed Jan 23, 2013 11:15 am by cangliang

» Hermes Bag
Wed Jan 23, 2013 11:14 am by cangliang

» Hermes Evelyn pm
Wed Jan 23, 2013 11:13 am by cangliang

» Hermes Kelly bag billig
Mon Jan 21, 2013 8:57 am by cangliang

» Hermes Constance Bag
Mon Jan 21, 2013 8:56 am by cangliang

» Discout Hermes Belt
Mon Jan 21, 2013 8:55 am by cangliang

» Christian Louboutin Love Flats
Tue Jan 15, 2013 12:25 pm by cangliang

» Christian Louboutin Love Flats
Tue Jan 15, 2013 12:25 pm by cangliang

Navigation
 Portal
 Diễn Đàn
 Thành viên
 Lý lịch
 Trợ giúp
 Tìm kiếm
December 2016
MonTueWedThuFriSatSun
   1234
567891011
12131415161718
19202122232425
262728293031 
CalendarCalendar
Diễn Đàn
Affiliates
free forum


Share | 
 

 Quick Sort

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
symphonyenigmatic
Thành viên bậc 3
Thành viên bậc 3


Tổng số bài gửi : 61
Points : 104
Reputation : 6
Join date : 26/07/2009
Age : 28
Đến từ : http:://thienthancntt.tk

Bài gửiTiêu đề: Quick Sort   Wed Aug 12, 2009 11:13 pm

Xin lỗi nhen, vì đây là diễn đàn OOP mà tui post bài Phân tích thiết kế thuật giải. Có mấy bạn hỏi tui về bài Quick Qort không đệ quy. (Còn hàm đệ quy thì thầy Long hồi trước cài zòi tui không nói lại nha), và một số bài về thi 20% học kì 4 như sau:

Có thể cách chưa tối ưu lắm, nếu bạn có ý kiến khác, zui lòng post để mọi ng cùng tham khảo nhen.

Bài 1: Quick Sort không đệ qui (Cách thứ nhất)
Code:

#include<string.h>
typedef struct          //dinh nghia kieu elems cua stack
{
        int L;
        int R;
}elems;       
#include"stackp.cpp"    //su dung stack nhu da~ hoc or cai dat tren con tro
void swap(elem &a,elem &b)
{
        elem c;
        c=a;
        a=b;
        b=c;
}

void sort(elem a[],int l,int r,int(*comp)(elem,elem))
{
        stack s;createstack(s);        //khoi tao stack rong
        int i,j;             
        elem x;                        //data cua a[]
        elems t;                        //data trong stack
        t.L=l;t.R=r;                 
        push(s,t);                      //day dang xet tu 0->n-1,push l=0 va r=n-1 vao stack
        do
        {
                pop(s,t);l=t.L;r=t.R;  //pop l,r trong  stack ra khoi stack
                do                      //phan hoach day a[l]..a[r] thanh 2 day a[l]..a[j] va a[i]..a[r]
                {
                        i=l;
                        j=r;
                        x=a[(l+r)/2];
                        do
                        {
                                while(comp(a[i],x)<0)i++;
                                while(comp(a[j],x)>0)j--;
                                if(i<=j)
                                {
                                        swap(a[i],a[j]);
                                        i++;
                                        j--;
                                }
                        }while(i<=j);
                        if(i<r)        //neu (i<r) push 1 bo(i,r) vao stack de phan hoach sau       
                        {     
                                t.L=i;t.R=r;
                                push(s,t);
                        }
                        r=j;            //de quay lai phan hoach day a[l]..a[j]
                }while(l<r);            //neu (l<r) quay lai  vong lap de phan hoach a[l]..a[j]
        }while(!emptystack(s) );        //stack chua rong quay lai vong lap  phan hoach cac day o ben phai?
}
void qskodequi(elem a[],int n,int(*comp)(elem,elem))
{
        sort(a,0,n-1,comp);
}

Quick Sort khử đệ qui (Cách 2)
Code:

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define M 100

typedef int elem;
void swap (elem &a, elem &b){
        elem c;
        c=a; a=b; b=c;
}

void quicksortkdequi (int a[100], int n){
        struct elemstack{ //Dinh nghia kieu phan tu trong stack
                int q;
                int r;
        };

        elemstack stack[50]; //khoi tao stack co toi da 50 phan tu
        int sp = 0;
        int i, j, x, r,q;
        stack[0].q=0;        //chi so dau cua mang can sap
        stack[0].r=n-1;      //chi so cuoi cua mang can sap

        do{
                //lay 1 phan hoach ra tu stack
                q=stack[sp].q;
                r=stack[sp].r;
                sp--; //xoa 1 phan tu khoi stack
                do{
                            //phan hoach day con tu a[q] .. a[r]
                        i=q;
                        j=r;
                        x=a[(q+r)/2]; //lay phan tu giua cua day can sap xep thu tu
                                      //lam chot
                        do{
                                while (a[i]<x) i++;
                                //tim phan tu dau tien co tri lon hon hay bang x
                                while (a[j]>x) j--;
                                if (i<=j){
                                        swap(a[i],a[j]);
                                        i++;
                                        j--;
                                }
                        }while (i<=j);
                        if (i<r){ // phan tu thu 3 co tu 2 phan tu tro len
                                  // Dua vao Stack chi so dau va chi so
                                  // cuoi cua phan tu thu ba
                                sp++;
                                stack[sp].q=i;
                                stack[sp].r=r;
                        }
                        r=j; // Chuan bi vi tri de phan hoach phan co gia tri
                            // nho hon chot
                }while (q<r);//ket thuc khi Stack rong
        }while (sp!=-1);
}

void xuat (elem a[], int n){
        for (int i=0;i<n;i++)
                cout<<a[i]<<" ";
}

void nhap (elem a[], int &n){
        cout<<"Vui long nhap tong so phan tu: ";
        cin>>n;
        int i;

        srand((unsigned) time(NULL));
        for(i=0; i<n; i++)
              a[i]=rand()%10000;
}

void main(){
        elem a[M];
        int n;
        nhap(a,n);
        quicksortkdequi (a,n);
        cout<<"So phan tu sau khi sap xep la: \n";
        xuat(a,n);
}

Bài đầu tiên dùng stack động. Bài thứ 2 dùng Stack tĩnh


Bài 2: Đề thi nhóm 1,
file cài đặt:
Code:

typedef int elem;
typedef struct node
{
   elem data;
   node *next;
};
typedef node *list;
//tao danh sach
void makenull(list &l)
{
   l=new node;
   l->next=NULL
}
//them 1 phan tu vao ds,add vao cuoi
void dswrite(elem x,list &l)
{
   list temp,l1;
   if(isnull(l)&& comp(x,l->data)<0)
   {
      temp=new node;
      temp->data=x;
      temp->next=l->next;
      l->next=temp;
   }
   else
   {
      l1=l;
      while(l1->next!=NULL)
         l1=l1->next;
      temp=new node;
      temp->data=x;
      temp->next=l1->next;
      l1->next=temp;
   }
}
void xuat(list l)
{
   list temp;
   temp=l->next;
   while(temp!=NULL)
   {
      cout<<" "<<temp->data;
      temp=temp->next;
   }
}
list merge(list &l1, list &l2, list &l)
{
    list p = l = new node, c;
    while (l1 != NULL && l2 != NULL) {
      if (l1->data < l2->data) {
          l->next = l1;
          l1 = l1->next;
      } else {
          l->next = l2;
          l2 = l2->next;
      }
      l = l->next;
    }
    l->next = (l1 == NULL ? l2 : l1);
    l1 = l2 = NULL;
    while (l->next != NULL)
    l = l->next;
    c = l;
    l = p->next;
    delete p;
    return c;
}

File ứng dụng:
Code:

#include<stdlib.h>
#include<conio.h>
#include<iostream.h>
#include<time.h>
#define N 100
#include"list.cpp"
void taolisttang(list &l,int n);
void main()
{
   list l[4],k,k1,k2;
    int n;
    time_t t;
    srand( (unsigned) time (&t) );
   cout<<"\n chuong trinh tao 4list va sx";
   for(int i=0;i<4;++i)
   { 
      makenull(l[i]);
      cout<<"Nhap so pt list thu "<<i+1<<": ";
        cin>>n;
        taolisttang(l[i],n);
        xuat(k)
        cout<<endl;
    }
    merge(l[0],l[1],k1);
    merge(l[2],l[3],k2);
    merge(k1,k2,k);
    cout<<"Tron 4 list tren thanh 1 list tang:\n";
    xuat(k);

}
void taolisttang(list &l,int n)
{
   elem a[N];
   x=rand % 100;
   dswrite(x,l)
   for(int i=1;i<n;i++)
   {
      a[i]=rand % 100;
      if(a[i]-x<=5)
      {
         dswrite(a[i],l)
         x=a[i];
      }
   }
}

[Bài 2 là bản quyền của sư phụ Âu.]

Còn đề quick sort dùng 1 lần gọi đệ quy của nhóm 2 thì tui hog nhớ nữa. Bạn nào bít post giùm tui hen. Thank nhìu!!
Về Đầu Trang Go down
Xem lý lịch thành viên http://http:://thienthancntt.tk
 
Quick Sort
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Giày quick thể thao xuất khẩu Hà Lan 2014
» nuoc hoa quick rush, nuoc hoa quick, quick rush, quick rush poppers, quick, rush

Permissions in this forum:Bạn không có quyền trả lời bài viết
minhlap.allgoo.us :: Lập trình :: Lập Trình Hướng Đối Tượng,Đồ Họa OpenGL C, C++-
Chuyển đến