Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Thuật Toán Interchange Sort

Share

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 27
Đến từ : Bến Tre

Thuật Toán Interchange Sort

Bài gửi  ztanzzthanhz on Wed Jan 20, 2010 12:55 pm

Code Interchange Sort (sắp xếp bằng đổi chỗ trực tiếp).
Code:

#include <stdio.h>
#include <conio.h>
#define max 100
void NhapMang(int A[], int &n)
{
   printf("Nhap n = ");
   scanf("%d",&n);
   for(int i = 0; i<n ; i++)
   {
      printf("Phan tu %d =",i);
      scanf("%d", &A[i]);
   }
}
void XuatMang(int A[], int n)
{
   printf("Mang sau khi sap xep la:");
   for(int i = 0; i<n ; i++)
      printf("%d ",A[i]);
}
void InterchangeSort(int A[], int n)
{
   for (int i=0; i<n-1; i++)
      for (int j=i+1; j<n; j++)
         if (A[i]>A[j])
         {
            int temp=A[i];
            A[i]=A[j];
            A[j]=temp;
         }
}
void main()
{
   int A[max],n;
   NhapMang(A,n);
   InterchangeSort(A,n);
   XuatMang(A,n);
   getch();
}

Demo thuật toán: mediafire.com ?nhygfymjzyz
Chương trình Demo này chạy từng bước của thuật toán, các bạn nhập khoảng 10 ~~> 20 phần tử rồi ngồi xem nó chạy nhé!
Nếu không hiểu, xem vài lần sẽ hiểu! Very Happy
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Re: Thuật Toán Interchange Sort

Bài gửi  admin on Wed Apr 14, 2010 8:48 am

Thanks! Đây cũng là kỹ thuật sắp xếp khá hay. Bạn hãy đánh giá độ phức tạp của thuật toán này nhé.

tna20141
Nhập môn
Nhập môn

Tổng số bài gửi : 1
Points : 1
Join date : 18/11/2010

Re: Thuật Toán Interchange Sort

Bài gửi  tna20141 on Thu Nov 18, 2010 3:52 pm

Thuật toán gồm n-1 bước, ở bước thứ i có n-i phép so sánh
=> có tổng cộng 1+2+...+n-1=n(n-1)/2 phép so sánh.
Vậy độ phức tạp của thuật toán này là O(n2).

Sponsored content

Re: Thuật Toán Interchange Sort

Bài gửi  Sponsored content


    Hôm nay: Wed Jan 17, 2018 10:12 am