• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

[VB.NET] Các thuật toán sắp xếp mảng thông dụng

Các bài viết hướng dẫn về Visual Basic .NET và C#

Điều hành viên: tungcan5diop, QUANITGROBEST

Hình đại diện của người dùng
clarkkent
Mạnh Thường Quân
Mạnh Thường Quân
Bài viết: 1641
Ngày tham gia: T.Tư 16/04/2008 11:25 am
Đến từ: Chợ Lách - Bến Tre
Been thanked: 31 time
Liên hệ:

[VB.NET] Các thuật toán sắp xếp mảng thông dụng

Gửi bàigửi bởi clarkkent » T.Tư 03/06/2009 4:24 pm

Tên bài viết: [VB.NET] Các thuật toán sắp xếp mảng thông dụng
Tác giả: Sưu tầm 4rum cũ
Cấp độ bài viết: Chưa đánh giá
Tóm tắt: [VB.NET] Các thuật toán sắp xếp mảng thông dụng


Selection Sort - Sắp xếp kiểu chọn
Giải thuật:
Đây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau:

*

Đầu tiên chọn phần tử nhỏ nhất trong n phần tử từ danh sách D[1]…D[n] và hoán vị nó với phần tử D[1].
*

Chọn phần tử có khóa nhỏ nhất trong n-1phần tử từ danh sách D[2]… D[n] và hoán vị nó với D[2].
*

Tổng quát ở bước thứ i, chọn phần tử có khoá nhỏ nhất trong n-i+1 phần tử từ danh sách D(i)… D(n) và hoán vị nó với D(i).


Sau n-1 bước này thì mảng đã được sắp xếp.
Phương pháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp.

Mã: Chọn hết

  1. Sub SelectionSort(ByRef D() As Integer)
  2. Dim i, j, SmallPos, Smallest As Integer
  3. For i = 0 To D.Length - 2 'Chon phan tu Min trong danh sach con D(i)..D(n)
  4.    SmallPos = i
  5.    Smallest = D(i)
  6. For j = i + 1 To D.Length - 1
  7. If D(j) < Smallest Then
  8.    SmallPos = j
  9.    Smallest = D(SmallPos)
  10. End If
  11. Next
  12. 'Doi cho phan tu dau tien cua ds con voi Min
  13.    D(SmallPos) = D(i)
  14.    D(i) = SmallestNext
  15. End Sub


• Hôm bây: www.tinsoftware.com ^ ^
Cố gắng lên...

Hình đại diện của người dùng
clarkkent
Mạnh Thường Quân
Mạnh Thường Quân
Bài viết: 1641
Ngày tham gia: T.Tư 16/04/2008 11:25 am
Đến từ: Chợ Lách - Bến Tre
Been thanked: 31 time
Liên hệ:

Re: [VB.NET] Các thuật toán sắp xếp mảng thông dụng

Gửi bàigửi bởi clarkkent » T.Tư 03/06/2009 4:27 pm

Insertion Sort - Sắp xếp kiểu chèn

Vấn đề:

Sắp thứ tự các phần tử của một danh sách:
D1, D2,…, Dn
Sao cho (theo một trường khóa nào đó) chúng có thứ tự tăng dần:
D1 ≤ D2 ≤ … ≤ Dn
Hoặc có thứ tự giảm dần:
D1 ≥ D2 ≥ … ≥ Dn

Giải thuật :

* Bước 1, xen phần tử D[2] vào danh sách đã có thứ tự D[1] sao cho D[1], D[2] là một danh sách có thứ tự.
* Bước 2, xen phần tử D[3] vào danh sách đã có thứ tự D[1], D[2] sao cho D[1], D[2], D[3] là một danh sách có thứ tự.
*

Tổng quát, bước i, xen phần tử D[i+1] vào danh sách đã có thứ tự

D[1],D[2],..D[i]

sao cho D[1], D[2],.. D[i+1] là một danh sách có thứ tự.
* Phần tử đang xét D[j] sẽ được xen vào vị trí thích hợp trong danh sách các phần tử đã được sắp trước đó D[1],D[2],..D[j-1] bằng cách so sánh khoá của D[j] với khoá của D[j-1] đứng ngay trước nó. Nếu khoá của D[j] nhỏ hơn khoá của D[j-1] thì hoán đổi D[j-1] và D[j] cho nhau và tiếp tục so sánh khoá của D[j-1] (lúc này D[j-1] chứa nội dung của D[j]) với khoá của D[j-2] đứng ngay trước nó...

Mã: Chọn hết

  1. Sub InsertionSort(ByRef D() As Integer)
  2.    Dim j As Integer
  3.    Dim NextElement As Integer
  4.    For i As Integer = 1 To D.Length - 1
  5.        NextElement = D(i)
  6.        j = i - 1
  7.    While j >= 0 And
  8.        Also NextElement < D(j)
  9.        D(j + 1) = D(j)j -= 1
  10.     End While
  11.    D(j + 1) = NextElement
  12.    Next
  13. End Sub
• Hôm bây: www.tinsoftware.com ^ ^
Cố gắng lên...

Hình đại diện của người dùng
clarkkent
Mạnh Thường Quân
Mạnh Thường Quân
Bài viết: 1641
Ngày tham gia: T.Tư 16/04/2008 11:25 am
Đến từ: Chợ Lách - Bến Tre
Been thanked: 31 time
Liên hệ:

Re: [VB.NET] Các thuật toán sắp xếp mảng thông dụng

Gửi bàigửi bởi clarkkent » T.Tư 03/06/2009 4:30 pm

Bubble Sort - Sắp xếp nổi bọt

Vấn đề:

Sắp thứ tự các phần tử của một danh sách:
D1, D2,…, Dn
Sao cho (theo một trường khóa nào đó) chúng có thứ tự tăng dần:
D1 ≤ D2 ≤ … ≤ Dn
Hoặc có thứ tự giảm dần:
D1 ≥ D2 ≥ … ≥ Dn

Sắp xếp kiểu Nổi bọt (bubble sort) là một giải thuật sắp xếp đơn giản. Nó lặp đi lặp lại quá trình duyệt danh sách cần sắp xếp, so sánh hai phần tử và đổi vị trí nếu chúng đứng sai vị trí.

Giải thuật như sau:

1.So sánh 2 phần tử cạnh nhau. Nếu phần tử trước lớn hơn phần tử sau thì đổi vị trí (swap) của chúng cho nhau.
2.Thực hiện việc đó với mỗi cặp phần tử., từ cặp đầu tiên tới cặp cuối cùng. Tới thời điểm này, phần tử cuối cùng sẽ là phần tử có giá trị lớn nhất.
3.Lặp lại các bước trên với các phần tử trừ phần tử cuối cùng. Cho tới khi không còn cặp nào cần so sánh.

Bubble Sort thực hiện tối đa (n-1) lần duyệt danh sách. Lần đầu tiên nó so sánh (n-1) cặp phần tử và kq là phần tử lớn nhất di chuyển về cuối danh sách. Lần thứ hai nó thực hiện (n-2) phép so sánh.
Do đó, trong trường hợp tồi nhất giải thuật thực hiện số lần là
(n-1)+(n-2) + . . . . . . . .+2+1 = n*(n-2)/2=O(n2)
Độ phức tạp của giải thuật là O(n2)

Mã: Chọn hết

  1. Sub BubbleSort(ByRef arr() As Integer)
  2.    Dim i, j As Integer
  3.    i = arr.Length
  4.     While i > 0
  5.        For j = 0 To i - 2
  6.           If arr(j) > arr(j + 1) Then
  7.              Swap(arr(j), arr(j + 1))
  8.           End If
  9.        Next
  10.        i -= 1
  11.     End While
  12. End Sub
  13.  
  14. 'This will swap a and b. We pass By Reference because we want to affect a and b.
  15.  
  16. Sub Swap(ByRef a As Integer, ByRef b As Integer)
  17. Dim temp As Integertemp = aa = bb = temp
  18. End Sub
• Hôm bây: www.tinsoftware.com ^ ^
Cố gắng lên...

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [VB.NET] Các thuật toán sắp xếp mảng thông dụng

Gửi bàigửi bởi vo_minhdat2007 » T.Tư 03/06/2009 4:47 pm

Thế mặc định thằng Array.Sort nó dùng thuật toán nào mà nhanh dữ vậy anh?

LIKIA
Thành viên chính thức
Thành viên chính thức
Bài viết: 12
Ngày tham gia: T.Ba 03/06/2008 6:24 pm

Re: [VB.NET] Các thuật toán sắp xếp mảng thông dụng

Gửi bàigửi bởi LIKIA » T.Sáu 28/08/2009 8:47 pm

Array.Sort() dùng Quicksort, 1 trong những thuật toán hiệu quả nhất để sắp xếp mảng (nhanh hơn nhiều các thuật toán đã trình bày ở trên). Tư tưởng của nó như sau:
- tại mỗi bước ta cần sắp xếp mảng có các phần từ có chỉ số từ l đến r
- chọn phần tử chốt và đưa hết các phần tử lớn hơn nó sang 1 bên, các phần từ bé hơn nó sang một bên
- như vậy, sau bước trên, đoạn mảng cần sắp xếp chia thành 3 phần: gồm các phần tử bé hơn, bằng và lớn hơn phần tử chốt. Với các phần 1 và 3, ta tiếp tục lặp lại 3 bước trên cho đến khi các phần đó đã đc xếp (đây gọi là đệ quy)
Chi tiết cài đặt như sau (mình quen viết C# rồi, quên hết Syntax VB, có sai sót gì mod sửa hộ mình nhé :D):

Mã: Chọn hết

  1. Sub QuickSort(ByRef arr() As Integer, ByVal l, r As Integer)
  2.    Dim i, j, k As Integer
  3.    k = arr((l + r) \ 2) ' chọn phần tử chốt, có thể có nhiều trò chọn khác: l, r hoặc random(l -> r)
  4.    i = l
  5.    j = r
  6.    While (i <= j)
  7.       While (arr(i) < k) i += 1
  8.       While (arr(j) > k) j -= 1
  9.       if (i <= j) Then
  10.          Swap(arr(i), arr(j))
  11.          i += 1
  12.          j -= 1
  13.       End If
  14.    End While
  15.    if (i < r) Then QuickSort(arr, i, r)
  16.    if (j > l) Then QuickSort(arr, l, j)
  17. End Sub
  18.  
  19. 'This will swap a and b. We pass By Reference because we want to affect a and b.
  20.  
  21. Sub Swap(ByRef a As Integer, ByRef b As Integer)
  22.    Dim temp As Integer
  23.    temp = aa = bb = temp
  24. End Sub


Bây giờ muốn sắp xếp mảng arr() có n phần tử từ 0 -> n - 1 thì gọi QuickSort(arr, 0, n - 1) ^^. Khởi tạo n khoảng tầm 8-| 10000 và so sánh với các thuật toán trên, thấy rõ sự khác biệt :D

P/S: hì hì, mượn tạm code Swap của bài trên, tại thấy nó 8-| ngắn quá ^^.

VietDreamerz
Bài viết: 6
Ngày tham gia: T.Tư 14/04/2010 3:14 pm

Re: [VB.NET] Các thuật toán sắp xếp mảng thông dụng

Gửi bàigửi bởi VietDreamerz » T.Năm 15/04/2010 6:45 pm

Vẫn thiếu Merge sort . . .
Đi 1 vòng 4rum . . . thấy post đi post lại mấy cái này nhưng vẫn thiếu Merge
Ko lẽ gà thế ^^!


Quay về “[.NET] Bài viết hướng dẫn”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.1 khách