Cấu trúc dữ liệu và giải thuật - Trình bày thuật toán sắp xếp Radixsort

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