• 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#

Moderators: tungcan5diop, QUANITGROBEST

User avatar
clarkkent
Mạnh Thường Quân
Mạnh Thường Quân
Posts: 1641
Joined: Wed 16/04/2008 11:25 am
Location: Chợ Lách - Bến Tre
Been thanked: 31 times
Contact:

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

Postby clarkkent » Wed 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.

Code: Select all

  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...

User avatar
clarkkent
Mạnh Thường Quân
Mạnh Thường Quân
Posts: 1641
Joined: Wed 16/04/2008 11:25 am
Location: Chợ Lách - Bến Tre
Been thanked: 31 times
Contact:

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

Postby clarkkent » Wed 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ó...

Code: Select all

  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...

User avatar
clarkkent
Mạnh Thường Quân
Mạnh Thường Quân
Posts: 1641
Joined: Wed 16/04/2008 11:25 am
Location: Chợ Lách - Bến Tre
Been thanked: 31 times
Contact:

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

Postby clarkkent » Wed 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)

Code: Select all

  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...

User avatar
vo_minhdat2007
Quản trị
Quản trị
Posts: 2227
Joined: Sun 17/07/2005 1:40 am
Has thanked: 13 times
Been thanked: 87 times
Contact:

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

Postby vo_minhdat2007 » Wed 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
Posts: 12
Joined: Tue 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

Postby LIKIA » Fri 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):

Code: Select all

  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
Posts: 6
Joined: Wed 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

Postby VietDreamerz » Thu 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ế ^^!


Return to “[.NET] Bài viết hướng dẫn”

Who is online

Users browsing this forum: No registered users and 0 guests