câu 1 đề 1 CTDL nè | Diễn đàn sinh viên trường CĐ CNTT Hữu Nghị Việt Hàn

phuc113 · 16 Tháng sáu 2011

Câu I (2 điểm)
Cho dãy số: 26, 7, 22, 15, 1, 18, 11, 27. Hãy minh họa cách sắp xếp tăng dần dãy số trên theo thuật toán Merge sort(trộn), Heap sort(vun đống), Quick sort(Nhanh).

Câu 1 : merge soft
void Merge(int a[], int left, int mid, int right)
{
int i = left;
int j=mid +1;
int k=0;
int n=right- left+ 1;
int b[100];
while ((i<= mid) && (j<= right ))
{
if (a< a[j])
{
b[k]=a;
i++;
k++;
}
else
{
b[k]=a[j];
j++;
k++;
}
}
while (i<= mid)
{
b[k]=a;
i++;
k++;
}
while (j <= right)
{
b[k]=a[j];
j++;
k++;
}
i=left;
for (k=0; k<n; i++)
{
a=b[k];
i++;
}
}

void MergeSort(int a[],int left,int right)
{
if (left<right)
{
int mid=(left+right)/2;
MergeSort(a, left, mid);
MergeSort(a, mid+1, right);
Merge(a, left ,mid ,right);// gọi hàm merge
}
}

HeapSort
void Swap(int &a, int &b) // Hoan vi
{
int c = a;
a = b;
b = c;
}
void Shift (int a[], int left, int right){
int x, curr, joint;
curr = left; joint =2*curr+1;
x = a[curr];
while (joint <= right){
if (joint < right){
if (a[joint] < a[joint+1]){
joint = joint+1;
}
}
if (a[joint]<x){
break;
}
a[curr] = a[joint];
curr = joint;
joint = 2*curr+1;
}
a[curr] = x;
}
void CreateHeap(int a[], int n)
{
int l;
l = n/2;
while (l>=0)
{
Shift(a,l,n);
l = l-1;
}
}
void HeapSort(int *a, int &n )
{
int r;
CreateHeap(a,n);
r = n-1;
while (r > 0)
{
Swap(a[0],a[r]);
r = r-1;
Shift(a,0,r);
}
}

Quick sort
void QuickSort(data a[],int left,int right)
{
int i,j;
string x;
i=left;
j=right;
x=a[(left+right)/2].s;
while (i<j)
{
while (a.s<x)i++;
while (a[j].s>x)j--;
if (i<=j)
{
a.s.swap(a[j].s);
i++;
j--;
}
}
if (left<j)
QuickSort(a,left,j);
if (right>i)
QuickSort(a,i,right);
}

trikp · 16 Tháng sáu 2011

có học cái này đâu mà bảo viết....Mai ra bài kiểu này có nộp giấy trắng về cho khỏe..

Cat-IT · 16 Tháng sáu 2011

uầy. có fai ko đó mi, mai bày nha

knight9000 · 16 Tháng sáu 2011

phúc không đọc kĩ đề à... Minh họa chứ có bảo viết code đâu mà viết làm gì...

sino · 16 Tháng sáu 2011

Merge sort là cái j vậy P?

phuc113 · 16 Tháng sáu 2011

minh họa thì mình viết cái hàm ra thui. chứ chẳng lẻ vẻ hình ak. họ có kêu vẽ đâu.

sino said: ↑

Merge sort là cái j vậy P?

là sấp xếp Trộn dó bạn

lyvinhr00m · 16 Tháng sáu 2011

Các bạn chú ý phần con trỏ,sắp xếp, danh sách sinh viên, đề lần trước có ra 2 phần này.

phuc113 · 16 Tháng sáu 2011

tài liệu cho các bạn nào cần. bí mật nhé. hihhi
http://c3qtst.net/ctdl.doc

kimtan · 18 Tháng sáu 2011

cái này kimtan chưa học, chắt phải nhờ máy anh chỉ giáo thôi. ^^