Trình bày thuật toán sắp xếp Radixsort
Với những kiến thức đã học, với sự giúp đỡ tận tình của các anh chị trên diễn đàn cộng đồng C việt, cùng giáo viên bộ môn em đã thu thập được những kinh nghiệm hết sức quý báu.
Kết hợp cùng với kiến thức đã được trang bị trên lớp em đã có một số suy nghĩ nhằm hoàn thiện đề tài đã giao.
Tuy nhiên với trình độ thực tiễn còn hạn chế và một số khó khăn gặp phải trong lúc thực hiện đề tài nên cũng không thể tránh khỏi những thiếu sót em rất mong nhận được sự ý kiến đóng góp từ thầy đề đề tài của em được hoàn thiện hơn.
21 trang |
Chia sẻ: lylyngoc | Lượt xem: 8072 | Lượt tải: 5
Bạn đang xem trước 20 trang tài liệu Trình bày thuật toán sắp xếp Radixsort, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG CAO ĐẲNG CN & KD VIỆT TIẾNKHOA MÁY TÍNH
Môn: Cấu trúc dữ liệu & giải thuật
ĐỀ TÀI: Trình bày thuật toán sắp xếp Radixsort
Giảng viên hướng dẫn : Trịnh Đức Tính Sinh viên thực hiện : Nguyễn Đình Hải Quân Lớp : C10T1MSSV : 100157
Giảng viên hướng dẫn : Trịnh Đức Tính
Sinh viên thực hiện : Nguyễn Đình Hải Quân
Lớp : C10T1
MSSV : 100157
Đà Nẵng, Ngày 25 tháng 1 năm 2013
MỤC LỤC
LỜI NÓI ĐẦU
Khái niệm sắp xếp dường như đã gắn liền với xã hội loài người từ thuở ban đầu của nền văn minh. Nó đơn giản thể hiện trong việc sắp hàng, trong việc phân công công việc,… Ngày nay, trong một thế giới mà khoa học công nghệ mỗi ngày phát triển như vũ bão và nhu cầu khai thác, tìm kiếm thông tin của con người ngày càng cao thì việc nâng cao tính hiệu quả của các giải thuật sắp xếp cũng ngày càng trở nên quan trọng.
Trong hầu hết các hệ lưu trữ, quản lý dữ liệu thao tác tìm kiếm là thao tác cơ bản để khai thác thông tin. Để việc tìm kiếm trở nên hiệu quả và nhanh chóng thì dữ liệu trong hệ thống cần được tổ chức theo một trật tự nào đó và điều này đòi hỏi chúng ta phải xây dựng những giải thuật sắp xếp thích hợp.
Bài báo cáo này nhằm mục đích giới thiệu về Radix Sort, một giải thuật sắp xếp đặc biệt vì nó gần giống cách sắp xếp theo lô của mà chúng ta vẫn hay làm trong cuộc sống hằng ngày.
Hy vọng nhận được những nhận xét và đánh giá chân thành từ thầy và các bạn.
PHẦN ILÝ THUYẾT & THUẬT TOÁN VỀ RADIX SORT
1.Giới thiệu về Radix Sort
Radix Sort là một thuật toán sắp xếp tiếp cận theo một hướng hoàn toàn khác so với các thuật toán khác. Nếu như trong các thuật toán khác, cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Nó không hề quan tâm đến việc so sánh giá trị của phần tử và bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử.
Ta biết rằng, để chuyển một khối lượng thư lớn đến tay người nhận ở nhiều địa phương khác nhau, bưư điện thường tổ chức một hệ thống phân loại thư phân cấp. Trước tiên, các thư đến cùng một tỉnh, thành phố sẽ được sắp chung vào một lô để gửi đến tỉnh thành tương ứng. Bưu điện các tỉnh thành này lại thực hiện công việc tương tự. Các thư đến cùng một quận, huyện sẽ được xếp vào chung một lô và gửi đến quận, huyện tương ứng. Cứ như vậy, các bức thư sẽ được trao đến tay người nhận một cách có hệ thông mà công việc sằp xếp thư không quá nặng nhọc.
2.Mô phỏng qui trình
- Trước tiên, ta có thể giả sử mỗi phần tử ai trong dãy a1, a2, …, an là một số nguyên có tối đa m chữ số.
- Ta phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, . tương tự việc phân loại thư theo tỉnh thành, quận huyện, phường xã, ..
3. Thuật toán sắp xếp Radix sort.
Có nhiều thuật toán sắp xếp Radix sort như Insertion Sort, Merge Sort, Counting sort.Trong bài chỉ thực hiện theo kiểu Counting Sort (Sắp xếp đếm phân phối). Vì nó thực hiện sắp xếp không dựa trên các thao tác so sánh
Trong bài báo cáo chỉ đề cập đến thuật toán Counting sort.
Các bước thực hiện thuật toán như sau:
Bước 1 : // k cho biết chữ số dùng để phân loại hiện hànhk = 0; // k = 0: hàng đơn vị; k = 1:hàng chục;
Bước 2 : //Tạo các lô chứa các loại phần tử khác nhauKhởi tạo 10 lô B0, B1, ., B9 rỗng;
Bước 3 :For i = 1 .. n doÐặt ai vào lô Bt với t = chữ số thứ k của ai;
Bước 4 : Nối B0, B1, ., B9 lại (theo đúng trình tự) thành a.
Bước 5 :k = k+1;Nếu k < m thì trở lại bước 2.Ngược lại: Dừng
Ví dụ:
Ta có mảng B gồm các phẩn tử như sau:
7013
8421
1239
428
1424
7009
4518
3252
9170
999
1725
701
Trong Radix Sort sẽ có một điều không thuận tiện là danh sách các số nguyên vì trong danh sách ấy có thể có các số nguyên có chiều dài không bằng nhau.
Để khắc phục điều này ta thêm chữ số 0 vào phía trước các chữ số ngắn để được mảng các phần tử có chùng chiều dài bằng nhau là 4.
Mảng B sau khi thêm các chữ số 0.
7013
8421
1239
0428
1424
7009
4518
3252
9170
0999
1725
0701
Phân lô theo hàng đơn vị:
0999
1725
4518
7009
9170
0701
3252
7013
1424
8425
0428
1239
0
1
2
3
4
5
6
7
8
9
Ta được mảng B như sau:
9170
0701
3252
7013
1424
8425
1725
0428
4518
1239
7009
0999
Phân lô theo hàng chục:
0428
1725
7009
4518
8425
0701
7013
1424
1239
3252
9170
0999
0
1
2
3
4
5
6
7
8
9
Ta được mảng B như sau:
0701
7009
7013
4518
1424
8425
1725
0428
1239
3252
9170
0999
Phân lô theo hàng trăm:
0428
7013
3252
8425
1725
7009
9170
1239
1424
4518
0701
0999
0
1
2
3
4
5
6
7
8
9
Ta được mảng B như sau:
7009
7013
9170
1239
3252
1424
8425
0428
4518
0701
1725
0999
Phân lô theo hàng nghìn:
0999
1725
0701
1424
7013
0428
1239
3252
4518
7009
8425
9170
0
1
2
3
4
5
6
7
8
9
Ta được mảng B đã sắp xếp hoàn thành như sau:
0428
0701
0999
1239
1424
1725
3252
4518
7009
7013
8425
9170
4.Kết luận
Giải thuật Radix Sort không dựa trên sự so sánh dữ liệu như các giải thuật sắp xếp khác. Với mỗi số nguyên từ dữ liệu sẽ có hai hành động được thực thi. + Thực hiện phép chia lấy nguyên cho 1 hệ số để lấy phần chữ số d và các chữ số trước nó (bỏ các chữ số sau nó).
+ Thực hiện phép chia lấy dư cho 10 để lấy ra chữ số d (bỏ các chữ số trước d).
5. Ðánh giá độ phức tạp giải thuật
Với một dãy n số, mỗi số có tối đa m chữ số, thuật toán thực hiện m lần các thao tác phân lô và ghép lô. Trong thao tác phân lô, mỗi phần tử chỉ được xét đúng một lần, khi ghép cũng vậy.
Sau lần phân phối thứ k các phần tử của A vào các lô B0, B1, ., B9, và lấy ngược trở ra, nếu chỉ xét đến k+1 chữ số của các phần tử trong B, ta sẽ có một mảng tăng dần nhờ trình tự lấy ra từ 0 -> 9. Nhận xét này bảo đảm tính đúng đắn của thuật toán
Thuật toán có độ phức tạp tuyến tính nên hiệu quả khi sắp dãy có rất nhiều phần tử, nhất là khi khóa sắp xếp không quá dài so với số lượng phần tử (điều này thường gặp trong thực tế).
Thuật toán cài đặt thuận tiện với các mảng với khóa sắp xếp là chuỗi (ký tự hay số) hơn là khóa số như trong ví dụ.
PHẦN II
CHƯƠNG TRÌNH MINH HOẠ TRỰC QUAN RADIX SORT
Trong bài báo cáo có sử dụng 2 chương trình minh hoạ được viết bằng 2 ngôn ngữ là: VB.Net và C++
1.Giới thiệu chương trình trên nền VB.Net
Tìm hiểu chương trình:
Chương trình được hình thành dựa trên ý tưởng là cho 1 tập các số, sau đó sắp xếp các dãy số đó theo thứ tự từ bé đến lớn, với các chức năng lưu mở file
Thiết kế chương trình:
Các thuộc tính thay đổi nhau sau:
-5 textbox: thuộc tính name là tb1, tb2, tb3, tb4, tb5- Nút ngẫu nhiên: Thuộc tính name là btnn- Nút sắp xếp: Thuộc tính name là nutbaocao- Menu: Thuộc tính name là f_menu- Listbox: Thuộc tính name là cacgiatri
a.Viết mã
Phần này chỉ đề cập đến các hàm chính trong chương trình.
Khởi tạo hàm sắp xếp Radixsort: hàm này dùng tính chất đệ qui. Trong đó ThisList là nguồn cần sắp xếp, Depth là số lần đệ qui
Public Function RecursiveRadixSort(ByRef ThisList As ICollection(Of Integer), _ ByVal Depth As Integer) As ICollection(Of Integer)
If Depth < 0 Then Return ThisList
Dim Bin(1) As ICollection(Of Integer)
Bin(0) = New List(Of Integer) : Bin(1) = New List(Of Integer)
For Each e As Integer In ThisList
Bin(Math.Abs(CInt((e And (&H1 > Depth))).Add(e)
Next
Dim r As New List(Of Integer)
If Depth = 31 Then
If Bin(1).Count > 0 Then r.AddRange(RecursiveRadixSort(Bin(1), Depth - 1))
If Bin(0).Count > 0 Then r.AddRange(RecursiveRadixSort(Bin(0), Depth - 1))
Else
If Bin(0).Count > 0 Then r.AddRange(RecursiveRadixSort(Bin(0), Depth - 1))
If Bin(1).Count > 0 Then r.AddRange(RecursiveRadixSort(Bin(1), Depth - 1))
End If
Return r
End Function
Khởi tạo hàm Run(): hàm này có tác gán các giá trị vào mảng A sau đó gọi hàm sắp xếp, trong đó n0,n1,n2,n3,n4 là các giá trị được truyền từ ô textbox ngoài form chính
Public Sub Run()
Dim A() As Integer = {n0, n1, n2, n3, n4}
Dim B As ICollection(Of Integer)
For i As Integer = 0 To 4
Console.Write(A(i) & " - ")
Next
Console.WriteLine()
B = RecursiveRadixSort(A, 31)
B.CopyTo(C, 0)
For i As Integer = 0 To 5
Console.Write(C(i) & " - ")
Next
End Sub
Sự kiện form load ta tạo các giá trị sau:
Private Sub f_main_Load(ByVal sender As System.Object, ByVal e As _System.EventArgs) Handles MyBase.Load
tb1.Text = Nothing
tb2.Text = Nothing
tb3.Text = Nothing
tb4.Text = Nothing
tb5.Text = Nothing
luufile.Enabled = False
End SubTạo chức năng mở filePrivate Sub MởFileToolStripMenuItem_Click(ByVal sender As System.Object,_ ByVal e As System.EventArgs) Handles mofile.Click
Dim i As Integer
luu.Items.Clear()
lbkq.Text = Nothing
Dim line, all As String
OpenFileDialog1.Filter = "Text (*.txt)| *.txt"
OpenFileDialog1.ShowDialog()
If OpenFileDialog1.FileName "" Then
Try
FileOpen(1, OpenFileDialog1.FileName, OpenMode.Input)
Do Until EOF(1)
line = LineInput(1)
all = all & line & vbCrLf
Loop
TextBox1.Text = all
TextBox1.Select(1, 0)
TextBox1.Enabled = True
Catch ex As Exception
MsgBox("Lổi mở file!")
Exit Sub
Finally
FileClose(1)
End Try
Dim d = 0
d = TextBox1.Lines(0) 'd chứa các giá trị trong textbox1
For i = 2 To d + 2 ' i=2 vi gia tri 0 với 1 không phải là giá trị trong listbox mà là: ‘số 0 kết quả và số 1 là phần tử trong listbox
luu.Items.Add(TextBox1.Lines(i)) 'listbox1 sẽ add từ vị trí thứ i tức thứ 2 trong ‘text
tb1.Text = TextBox1.Lines(10) ' lay gia tri add len
tb2.Text = TextBox1.Lines(11) ' lay gia tri add len
tb3.Text = TextBox1.Lines(12) ' lay gia tri add len
tb4.Text = TextBox1.Lines(13) ' lay gia tri add len
tb5.Text = TextBox1.Lines(14) ' lay gia tri add len
lbkq.Text = TextBox1.Lines(2) 'label kết quả chứ hàng thứ 1 trong file lưu
Next
chuthich.Visible = True
End If
End Sub
Tạo chức năng cho menu lưu file:
Private Sub LưuFileToolStripMenuItem_Click(ByVal sender As System.Object,_ ByVal e As System.EventArgs) Handles luufile.Click
Dim j As Integer
SaveFileDialog1.Filter = "Text File (*.txt) | *.txt"
SaveFileDialog1.ShowDialog()
If SaveFileDialog1.FileName "" Then
Try
FileOpen(1, SaveFileDialog1.FileName, OpenMode.Output)
PrintLine(1, 4) 'in ra dong so 1 trong file txt để: kiem tra so phan tu co trong listbox
PrintLine(1, "In ra ket qua sau khi sap xep")
PrintLine(1, lbkq.Text) 'in ra dong so 2 trong file txt để: kiem tra ket qua de xuat ra label khi load file
PrintLine(1, "Thu tu da sap xep de dua vao tung o textbox")
For j = 0 To 4
PrintLine(1, luu.Items(j)) 'xuat gia tri ra file txt từ listbox danh sach
Next
PrintLine(1, "cac gia tri ban dau")
For j = 0 To 4
PrintLine(1, cacgiatri.Items(j)) 'xuat gia tri ra file txt từ listbox danh sach
Next
Catch ex As Exception
MsgBox("Loi khi ghi!")
Finally
FileClose(1)
End Try
End If
End Sub
2. Chương trình minh hoạ bằng C++
Ý tưởng: Chương trình được viết trên ý tưởng cho dãy các thẻ sau đó sắp xếp các thẻ này theo thứ tự tăng dầna.Viết mã
Tạo hàm radixsort
void RadixSort(int *a,int n)
{ int i,b[MAX],m=0,exp=1;
for(i=0;i<n;i++)
{ if(a[i]>m)
m=a[i]; }
while(m/exp>0)
{
int bucket[10]={0};
for(i=0;i<n;i++)
bucket[a[i]/exp%10]++;
for(i=1;i<10;i++)
bucket[i]+=bucket[i-1];
for(i=n-1;i>=0;i--)
b[--bucket[a[i]/exp%10]]=a[i];
for(i=0;i<n;i++)
a[i]=b[i];
exp*=10;
#ifdef SHOWPASS
cout<<"\nSap xep: ";
print(a,n);
#endif
}
}
Trong hàm main ta tạo các giá trị để sử dụng hàm như sau:int main()
{int k;
do {
int arr[MAX];
cout<<"\n..::Nhan 1 de nhap the, nhan 2 de nhap ngau nhien, nhan 0 de thoat: \n";
cin>>k;
if (k==1){
int i,n;
printf("Nhap so luong the can sap xep max 5 the: (n < %d) : ",MAX);
scanf("%d",&n);
printf("Nhap the sau do an enter de sang the moi:\n",n);
for(i=0;i<n;i++)
cin>>arr[i];
printf("\nMang vua nhap la : ");
print(&arr[0],n);
RadixSort(&arr[0],n);
printf("\nKet qua sau khi sap xep : ");
print(&arr[0],n);
printf("\n");
}
if (k==2){
int i;
srand ( time(NULL) ); //dung de tao ham random
for(i=0;i<5;i++)
{ arr[i]=rand();}
printf("\nMang vua tao ngau nhien la : ");
for(i=0;i<5;i++)
cout<<arr[i]<<" ";
cout<<"\n";
RadixSort(&arr[0],5);
cout<<"\n";
printf("\nKet qua sau khi sap xep : ");
print(&arr[0],5);
printf("\n\n");
}
} while(k>0);
return 0;
}
III. Kết Luận Với những kiến thức đã học, với sự giúp đỡ tận tình của các anh chị trên diễn đàn cộng đồng C việt, cùng giáo viên bộ môn em đã thu thập được những kinh nghiệm hết sức quý báu.
Kết hợp cùng với kiến thức đã được trang bị trên lớp em đã có một số suy nghĩ nhằm hoàn thiện đề tài đã giao.
Tuy nhiên với trình độ thực tiễn còn hạn chế và một số khó khăn gặp phải trong lúc thực hiện đề tài nên cũng không thể tránh khỏi những thiếu sót em rất mong nhận được sự ý kiến đóng góp từ thầy đề đề tài của em được hoàn thiện hơn.
Em xin chân thành cảm ơn thầy Trịnh Đức Tính đã hướng dẫn cho em hoàn thành đồ án này. Kính chúc thầy sức khoẻ dồi dào và đạt được nhiều thành tích trong công việc.
Đà Nẵng, ngày 29 tháng 12 năm 2012.
Sinh viên thực hiện Nguyễn Đình Hải Quân
Đánh giá và nhận xét của giáo viên bộ môn
Thông Tin Khác
Trong bài làm có sử dụng nguồn từ nhiều nguồn khác nhau cụ thể:
Tuyển tập đồ án tốt nghiệp sinh viên Thanh Hóa
Edison – Blog Archive » Sắp xếp dựa trên cơ số -Radix sort
Recursive Radix Sort - VB.NET | DreamInCode.net
Radix Sort – C++ | DreamInCode.net
Câu lạc bộ Visual Basic .NET và C# (VB.NET & C#)
Dự án & Source code VC++ - Cộng đồng C Việt
Các file đính kèm theo tài liệu này:
- baocao_do_an_radixsort_svth_quan_id100157_1516.doc