Thursday, December 31, 2009

Các khái niệm lập trình hướng đối tượng OOP

Một đối tượng là gì?

Java được biết đến như một ngôn ngữ hướng đối tượng (OO - object-oriented), bạn có thể sử dụng ngôn ngữ này để lập trình hướng đối tượng. Điều này rất khác so với lập trình thủ tục, và có thể hơi lạ lùng đối với hầu hết các lập trình viên không hướng đối tượng. Bước đầu tiên bạn phải hiểu đối tượng là gì, vì đó là khái niệm cơ sở của OOP.

Một đối tượng là một bó mã lệnh tự thân trọn vẹn (self-contained), tự hiểu chính mình và có thể nói cho các đối tượng khác về chính mình nếu chúng đưa ra các yêu cầu mà nó hiểu được. Một đối tượng có các thành phần dữ liệu (các biến) và các phương thức, chính là những yêu cầu mà nó biết cách trả lời (dù chúng không được diễn đạt bằng lời như các câu hỏi). Tập các phương thức mà một đối tượng biết cách trả lời được gọi là giao diện của đối tượng. Một vài phương thức là mở công cộng, nghĩa là các đối tượng khác có thể gọi đến chúng. Tập các phương thức này được gọi là giao diện công cộng của đối tượng.

Khi một đối tượng gọi phương thức của một đối tượng khác, thì được gọi là gửi một thông điệp (sending a message hoặc message send). Cụm từ này là thuật ngữ của OO nhưng hầu hết trong giới Java mọi người hay nói, “gọi phương thức này” hơn là “gửi thông điệp này”. Trong phần tiếp theo, chúng ta sẽ xem xét một ví dụ minh họa khái niệm giúp bạn hiểu vấn đề này rõ ràng hơn.

Ví dụ minh họa khái niệm đối tượng

Giả sử chúng ta có đối tượng Person. Mỗi Person có tên, tuổi, chủng tộc và giới tính. Mỗi Person cũng biết nói và biết đi. Một Person có thể hỏi tuổi của một Person khác, hoặc yêu cầu một Person khác bắt đầu đi (hay dừng). Diễn đạt theo thuật ngữ lập trình, bạn có thể tạo một đối tượng Person và khai báo một số biến (như tên và tuổi). Nếu bạn tạo một đối tượng Person thứ hai, đối tượng này có thể hỏi tuổi của đối tượng thứ nhất hoặc yêu cầu đối tượng thứ nhất bắt đầu đi. Nó có thể thực hiện những điều ấy bằng cách gọi đến các phương thức của đối tượng Person đầu tiên. Khi chúng ta bắt đầu viết mã lệnh bằng ngôn ngữ Java, bạn sẽ hiểu ngôn ngữ này triển khai thực hiện khái niệm đối tượng ra sao.

Nói chung, khái niệm đối tượng là như nhau trong ngôn ngữ Java và các ngôn ngữ hướng đối tượng khác, mặc dù việc triển khai thực hiện là khác nhau giữa các ngôn ngữ. Các khái niệm là phổ quát. Vì sự thật này, lập trình viên hướng đối tượng, bất chấp họ lập trình bằng ngôn ngữ nào, có xu hướng phát biểu khác so với những lập trình viên thủ tục. Các lập trình viên thủ tục thường nói về các hàm và các mô đun. Lập trình viên hướng đối tượng lại nói về các đối tượng và họ thường nói về các đối tượng này bằng cách sử dụng các đại từ nhân xưng. Chẳng hề bất thường khi bạn nghe một lập trình viên hướng đối tượng nói với đồng nghiệp, “đối tượng Supervisor nói với đối tượng Employee, ‘cho tôi ID của cậu,’” vì anh ta cần những thứ này để gán nhiệm vụ cho Employee.

Lập trình viên hướng thủ tục có thể nghĩ cách nói chuyện này thật lạ lùng, nhưng nó lại hoàn toàn bình thường đối với lập trình viên hướng đối tượng. Trong thế giới lập trình của họ, mọi thứ đều là đối tượng (cũng có một vài ngoại lệ đáng chú ý trong ngôn ngữ Java) và các chương trình là chỉ là sự tương tác (hay nói chuyện) giữa các đối tượng với nhau.

Các nguyên tắc hướng đối tượng cơ bản

Khái niệm đối tượng là trọng yếu đối với lập trình hướng đối tượng, và dĩ nhiên, ý tưởng các đối tượng giao tiếp với nhau bằng các thông điệp cũng vậy. Nhưng có 3 nguyên tắc cơ bản mà bạn cần hiểu.

Bạn có thể nhớ 3 nguyên tắc hướng đối tượng cơ bản bằng cụm viết tắt PIE:

  • Đa hình ( Polymorphism)
  • Thừa kế ( Inheritance)
  • Bao gói ( Encapsulation)

Đó là những từ trừu tượng nhưng những khái niệm này thực sự không quá khó hiểu. Trong các phần tiếp theo, chúng ta sẽ bàn về từng khái niệm này ở mức độ chi tiết hơn, theo thứ tự ngược lại.


Bao gói

Hãy nhớ rằng, một đối tượng là tự thân trọn vẹn, chứa đựng các thành phần dữ liệu và hành động mà nó có thể thực hiện trên các thành phần dữ liệu ấy. Đây là việc triển khai thực hiện nguyên lý gọi là ẩn giấu thông tin. Ý tưởng của nó là một đối tượng tự nó hiểu mình. Nếu một đối tượng khác muốn điều gì từ đối tượng này thì nó phải hỏi. Theo thuật ngữ lập trình hướng đối tượng, phải gửi một thông điệp đến một đối tượng khác để hỏi về tuổi. Theo thuật ngữ Java, phải gọi một phương thức của đối tượng khác để nó trả lại kết quả là tuổi.

Sự bao gói đảm bảo rằng mỗi đối tượng là khác nhau và chương trình là một cuộc chuyện trò giữa các đối tượng. Ngôn ngữ Java cho phép các lập trình viên vi phạm nguyên lý này nhưng hầu như luôn là một ý tưởng tồi nếu làm như thế.

Thừa kế

Khi bạn được sinh ra, nói về khía cạnh sinh học, bạn là tổ hợp DNA của cha mẹ mình. Bạn không hoàn toàn giống ai trong số họ, mà bạn giống cả hai người. OO cũng có nguyên tắc tương tự đối với các đối tượng. Quay lại với đối tượng Person. Ta nhớ lại rằng mỗi người có một chủng tộc. Không phải tất cả các Person đều cùng chủng tộc, nhưng dù sao thì họ cũng có điểm tương tự như nhau chứ? Chắc chắn vậy! Họ chẳng phải ngựa, tinh tinh hay cá voi mà là người. Mọi con người đều có những điểm chung nhất định và điều này giúp phân biệt con người với các loài động vật khác. Nhưng giữa mọi người cũng có khác biệt với nhau. Một đứa trẻ có giống hệt một người trưởng thành không? Không. Đi lại và nói là khác nhau rồi. Nhưng một đứa trẻ thì vẫn chắc chắn là một con người.

Theo ngôn ngữ hướng đối tượng, Person và Baby là các lớp sự vật hiện tượng thuộc cùng một hệ thống phân bậc, và Baby thừa kế các đặc tính và hành vi từ lớp cha của nó. Chúng ta có thể nói rằng một Baby cụ thể là một kiểu Person hay Baby thừa kế từ Person. Nhưng không có chiều ngược lại – một Person không nhất thiết phải là một Baby. Mỗi đối tượng Baby là một cá thể của lớp Baby và khi chúng ta tạo một đối tượng Baby, chúng ta cá thể hóa lớp này. Hãy coi lớp như là khuôn mẫu chung cho các cá thể của lớp đó. Nói chung, đối tượng có thể làm những gì tùy thuộc vào kiểu của đối tượng đó là gì – hoặc nói theo cách khác, đối tượng đó là cá thể của lớp nào. Cả Baby và Adult đều thuộc kiểu Person, nhưng một đối tượng (Adult) có thể có một việc làm (job) còn đối tượng kia (Baby) thì không.

Theo thuật ngữ Java, Person là một lớp bậc trên (superclass) của Baby và Adult, và các lớp này là lớp con của Person. Một khái niệm có liên quan khác là ý tưởng về trừu tượng hóa. Person có mức trừu tượng hóa cao hơn Baby hay Adult. Cả hai đều là kiểu Person nhưng có những khác biệt nho nhỏ. Tất cả các đối tượng Person đều có những điểm chung (như tên và tuổi). Bạn có thể cá thể hóa một Person? Thực sự là không! Bạn hoặc có một Baby hoặc có một Adult. Trong Java, Person được gọi là lớp trừu tượng. Bạn không thể trực tiếp có một cá thể của lớp Person. Bạn sẽ có Baby hoặc Adult, cả hai đều là kiểu Person, nhưng là Person đã được thực tế hóa. Các lớp trừu tượng nằm ngoài phạm vi của tài liệu này, chúng tôi sẽ không nói thêm về chúng nữa.

Bây giờ, ta hãy suy nghĩ xem với một Baby, “nói” (speak) có nghĩa là gì. Chúng ta sẽ xét đến các hệ quả trong phần thảo luận tiếp theo.

Đa hình

Baby có “nói” như Adult không? Dĩ nhiên là không rồi. Một Baby có thể ê a, nhưng không nhất thiết nói ra những lời hiểu được như Adult. Do đó, nếu tôi cá thể hóa một đối tượng Baby (hay là “cá thể hóa một Baby” cũng có cùng ý nghhĩa – từ “đối tượng” được ngầm hiểu) và cho nó nói, thì nó chỉ có nghĩa là những tiếng ê a. Ta hy vọng rằng Adult “nói” thì mạch lạc hơn.

Trong hệ thống phân bậc con người, chúng ta có Person nằm ở đỉnh với Baby và Adult nằm phía dưới nó, là các lớp con. Tất cả mọi người đều có thể nói, Baby và Adult cũng vậy, nhưng sẽ nói khác nhau. Baby chỉ ê a và phát những âm thanh đơn giản. Adult nói thành lời. Đó chính là sự đa hình: các đối tượng làm việc theo cách riêng của chúng.

Ngôn ngữ Java là (và không là) OO ở chỗ nào?

Như chúng ta sẽ thấy, ngôn ngữ Java cho phép bạn tạo các đối tượng hạng nhất (first-class), nhưng không phải bất cứ cái gì trong ngôn ngữ này đều là đối tượng. Một số ngôn ngữ OO như Smalltalk lại hoàn toàn khác. Smalltalk hoàn toàn là OO, có nghĩa là mọi thứ trong ngôn ngữ này đều là đối tượng. Java là ngôn ngữ lai tạp giữa đối tượng và phi đối tượng. Nó cho phép một đối tượng biết rõ các đối tượng khác, nếu với tư cách là một lập trình viên bạn cho phép điều đó xảy ra. Điều này vi phạm nguyên lý bao gói.

Tuy nhiên, ngôn ngữ Java cũng cung cấp cho tất cả các lập trình viên OO những công cụ cần thiết để tuân theo mọi quy tắc OO và viết mã lệnh OO rất chuẩn. Nhưng làm được như vậy cần phải tự có kỷ luật. Ngôn ngữ không ép bạn làm việc đúng đắn được.

Trong khi những người thuần túy chủ nghĩa hướng đối tượng tranh luận xem liệu Java là hướng đối tượng hay không, thực sự đây không phải là một lý lẽ mang lại ích lợi. Nền tảng Java sẽ giữ vững vị trí của nó. Hãy học cách lập trình hướng đối tượng tốt nhất có thể với mã lệnh Java và cứ để những lý lẽ thuần túy chủ nghĩa cho những người khác. Ngôn ngữ Java giúp bạn viết chương trình rõ ràng, khá ngắn gọn, dễ bảo trì, điều này là khá đủ trong cuốn sách của tôi đối với hầu hết các tình huống nghề nghiệp.

Wednesday, December 30, 2009

Tôi học ngành công nghiệp, nhưng mở công ty về du lịch

Chào Quý bạn đọc,

Tôi tìm thấy ở đây một sự tương đồng giữa các bạn trẻ.

Đầu tiên chúng ta phải có ước mơ, hoài bão cho riêng mình, chúng ta phải có trí tuệ, bản lĩnh, làm việc chăm chỉ và đam mê công việc mình đã lựa chọn. Và tất nhiên trên đường thành công không thể thiếu yếu tố may mắn:

ước mơ + trí tuệ + bản lĩnh + may mắn = thành công. (các chỉ số luôn đồng hành và tỉ lệ thuận với nhau ).

Tôi tốt nghiệp cao đẳng ngành Công Nghiệp nhưng hiện tại đang làm việc trong lĩnh vực dịch vụ du lịch. Ngay từ hồi niên thiếu tôi đã luôn ước mơ được làm việc trong ngành du lịch và thực sự ngay trong những năm ngồi trên ghế giảng đường tôi đã biết cách làm sao có thể kiếm tiền, xây dựng và phát triển một công ty du lịch.

Trong khi các bạn cùng khoá luôn chú tâm học các môn chính thì tôi lại đi theo một hướng hoàn toàn ngược lại, tôi chỉ nghiên cứu về tin học, tìm hiểu công nghệ Internet, nâng cao khả năng ngoại ngữ, đọc và nghiên cứu các lại sách, tài liệu về kinh doanh, quản lý, học kĩ năng đàm phán, giao tiếp và ứng xử trong kinh doanh....

Và hậu quả là tôi chỉ ra trường với tấm bằng trung bình với các điểm số cực kỳ kém nhưng thành quả lại rất lớn, ảnh hưởng tích cực đến sự thành công của tôi sau này.

Ra trường được hơn 1 tháng, tôi xin vào làm tại một công ty du lịch tư nhân, trải qua 1,5 năm với nhiều vị trí, chức vụ trong công ty, cuối năm 2002 tôi quyết định ra ngoài lập nghiệp ( vào thời đó tôi cho rằng mình đã đủ lông, đủ cánh và luôn tin rằng với đường lối kinh doanh mà mình đã vạch ra, tôi sẽ thành công.).

Các bạn ạ, tôi đã thành công trong việc thuyết phục được 3 anh chị em khác, những người có chuyên môn rất tốt cùng hợp tác xây dựng công ty mới, mỗi thành viên chỉ đóng 10 triệu VNĐ, thuê 1 văn phòng nhỏ tại 1 con phố nhỏ với vẻn vẹn 1 chiếc máy tính, 2 chiếc điện thoại bàn, 1 máy in và 1 máy fax. Chúng tôi cũng tự thiết kế logo, slogan, tên công ty, điều lệ hoạt động và chiến lược kinh doanh.....

Như các bạn đã biết, 1 công ty mới thành lập luôn gặp khó khăn như thế nào trên thương trường. Trải qua hơn 1 năm đầy sóng gió, với sự hạn chế về vốn (trong ngành du lịch việc quảng cáo, quảng bá và thiết lập các mối quan hệ luôn rất quan trong), sự cạnh tranh quyết liệt từ rất nhiều các công ty lớn nhỏ... Chúng tôi thực sự gặp quá nhiều khó khăn, rất ít khách hàng, tiền vốn dần cạn kiệt, nhiều tháng chúng tôi không có lương...

Các bạn biết không, bản thân tôi một chàng trai tỉnh lẻ cách Hà Nội 60 km, bố mẹ đều là cán bộ CVN, đã rất rất nhiều lần phải ăn mì tôm cầm hơi, ngủ dưới nền đất, tắm nước lạnh giữa mùa đông, không có nổi 1.000 VNĐ để ăn sáng, nhiều đêm thức trắng và khóc cho sự nghèo khổ của mình.... Nản chí 2 người trong số 4 cổ đông đã ra đi tìm công việc khác, chỉ còn lại tôi và 1 anh nữa ở lại với số dư tài khoản là 7 triệu VNĐ.

Làm thế nào bây giờ ? tôi chỉ sợ rằng sẽ chỉ còn lại một mình tôi với 1 công ty đang bị suy dinh dưỡng trầm trọng. May thay, anh bạn kia cũng cùng chí hướng như tôi "to be or not to be". Anh lên làm GĐ còn tôi làm GĐKD (công ty không có nhân viên).

Thực tế, vào thời điểm đó, hơn lúc nào hết tôi có niềm tin mãnh liệt rằng mình đang đi đúng hướng, chiến lược và đường lối kinh doanh của mình đang áp dụng sắp cho trái ngọt, và quả đúng như vậy, chúng tôi vẫn nỗ lực làm việc với hơn 100% sức lực có thể, 3 tháng sau chúng tôi ký được hợp đồng với 02 công ty liên doanh tương đối lớn tại Hà Nội và 2 tháng sau nữa đã có được đoàn khách nước ngoài đầu tiên đến từ Singapore.

Sau 2 năm kinh doanh, ngày càng nhiều các hãng lữ hành trên Thế Giới đặt vấn đề hợp tác với chúng tôi, ngày càng nhiều hợp đồng được kí, danh sách đối tác ngày càng dài, các đối tác cung cấp dịch vụ trong nước như khách sạn, nhà hàng, vận chuyển...cũng đã biết đến chúng tôi. Chúng tôi tuyển nhân viên, thậm chí là cả nhân viên người nước ngoài, mở rộng chi nhánh trong nước và Đông Dương, chuyển đến văn phòng mới khang trang hơn, trình độ quản lý của được nâng cao...

Đến nay hai anh em chúng tôi đã có gia đình riêng, rất hạnh phúc và cũng đã tạm được gọi là thành đạt. Công ty đã có đủ lực để cạnh tranh sòng phẳng, tồn tại và phát triển trong lĩnh vực du lịch.

Trên đây là những tâm sự trải nghiệm của tôi, với một mong ước duy nhất là mang đến cho những bạn trẻ đang lập nghiệp sự động viên tinh thần. Các bạn hãy nỗ lực hết sức mình, luôn hoàn thiện mình, kiên trì hiện thực hoá ước mơ, hoài bão của mình, xác định cho mình lý tưởng sống, cộng thêm may mắn nữa, chắc chắn các bạn sẽ thành công.

Chúc các bạn luôn mạnh khoẻ, thành đạt và hạnh phúc.

Trần Hùng, ACT Travel
theo báo VNExpress

Tuesday, December 29, 2009

Tìm kiếm quick sort và heap sort

Quick Sort

Quick sort là phương pháp đổi chỗ từng phần (partition exchange), đây là phương pháp rất hiệu quả, rất thông dụng..
Nội dung của phương pháp này như sau:
Chọn một nút bất kỳ trong danh sách(Giả sử là nút đầu tiên) gọi là nút làm trục (pivot node), xác định vị trí hợp lệ của nút này trong danh sách (gọi là vị trí pivot).
Tiếp theo chúng ta phân hoạch các nút còn lại trong danh sách cần sắp xếp sao cho từ vị trí 0 đến vị trí pivot-1 đều có nội dung nhỏ hơn hoặc bằng nút làm trục, các nút từ vị trí pivot+1 đến n-1 đều có nội dung lớn hơn nút làm trục.
Quá trình lại tiếp tục như thế với hai danh sahs con từ trị trí 0 đến vị trí pivot-1 và từ vị trí pivot+1 đến vị trí n-1, ... Sau cùng chúng ta sẽ được danh sách có thứ tự.

Mô tả giải thuật Quick sort
Giai thuat: QuickSort(nodes[], low, up)
Mo Ta; Giair thuat QuickSort, dung phuong phap de qui sawp xep va cac nut trong danh sach giua hai vi tri
low va up
Du Lieu nhap:
- Danh sach cac nut chua sap xep (giua hai vi tri low va up)
- low va up
Du Lieu Xuat:
Danh sach cac nut (giua hai vi tri low va up) da duoc sap xep

Hanh dong
if(low >= up) // dieu kien dung
ket thuc giai thuat
if(low < up)
- Phan hoach: partition(nodes[], low, up, pivot)
+ partition phan danh sach thanh ba phan:
* nut lam truc: nodes[low] tro thanh nodes[pivot]
* danh sach con 1: nodes[i] <= nodes[pivot]
(voi i < pivot)
* danh sach con 2: nodes[i] > nodes[pivot]
(voi i > pivot)
- Goi de qui: QuickSort(nodes[], low, pivot-1)
- Goi de qui: QuickSort(nodes[], pivot+1, up)
Ket Thuc

Giải thuật Partion
vấn đề tiếp theo là giải thuật partition giúp phân danh sách làm ba phần:
  • Nút đầu (nút làm trục) đặt ở vị trí pivot
  • Danh sách con 1 từ vị trí low đến pivot-1 có nội dung nhỏ hơn hay bằng nút làm trục.
  • Danh sách con 2 từ vị trí low đến pivot+1 có nội dung lớn hơn hay bằng nút làm trục.
Người ta xử lý giải thuật partition theo mô tả như sau:
1. Chọn nodes[low] (nút đầu tiền) là nút làm trục.
2. Quét danh sách theo hai hướng để đổi chỗ các cặp nút "sai" vị trí, nơi gặp nhau của hai hướng quét chính là vị trí pivot:
Quét từ low lên: con trỏ l xuất phát từ vị trí low và tăng dần lên, dừng lại khi gặp nút có nội dung lớn hơn nút làm trục, ghi nhận vị trí l lúc này.
  • Quét từ up xuống: con trỏ u xuất phát từ vị trí up và giảm dần xuống, dừng lại khi gặp nút có nội dung nhỏ hơn hay bằng nút làm trục, ghi nhận vị trí u lúc này.
  • Đổi chỗ hai nút tại vi trí l và u.
  • Cứ tiếp tục quét theo hai hướng và đổi chỗ các cặp nút "sai" vị trí, quá trình này dừng lại khi l = u (hai hướng quét gặp nhau), nợi gặp nhau chính là vị trí pivot (pivot = u = l).
3. Đổi chỗ hai nút tại vị trí low (nút làm trục) và nút tại vị trí pivot.

Sau đây là giải thuật partition
Giai Thuat: partition(nodes[], low, up, pivot)
Mo Ta: Giai thuat partition, phan danh sach thanh 3 phan ...
Du Lieu Nhap:
Danh sach cac nut trong khoang vi tri tu low den up.
Du Lieu Xuat:
Dua nut lam truc ve vi tri pivot, doi cho cac nut trong danh sach
sao cho cac nut co noi dung nho hon hay bang nut lam truc duoc
bo tri truoc nut lam truc, cac nut co noi dung lon hon nut lam
truc duoc bo tri sau nut lam truc.
Hanh Dong
1. Chon nodes[low] la nut lam truc
Gan: l = low;
u = up;
2. while(l < u) // vong lap xu ly hai huong quet
{
Quet huong tu low len, dung lai khi gap nut lon hon nut lam truc,
ghi nhan vi tri l luc nay

Quet huong tu up xuong, dung lai khi gap nut nho hon hay bang
nut lam truc, ghi nhan vi tri u luc nay

Doi cho hai nut tai hai vi tri l va u
}

3. Doi cho hai nut tai hai vi tri low va u (luc nay pivot = u)
Ket Thuc

Cài đặt giải thuật QuickSort
Sau đây là hàm QuickSort() dùng phương pháp đệ qui, hàm này có gọi hàm partition() để phân hoạch danh sách con thành 3 phần.
Hàm QuickSort()
void QuickSort(int nodes[], int low, int up)
{
int pivot;
if(low >= up) // dieu kien dung
return;

if(low < up)
{
partition(nodes, low, up, &pivot);
QuickSort(nodes, low, pivot - 1);
QuickSort(nodes, pivot + 1, up);
}
}

Hàm partition():
void partition(int nodes [], int low, int up, int *pivot)
{
int nuttruc, l, u, temp;
nuttruc = nodes[low]; // Chon nut dau lam nut truoc
l = low;
u = up;
while(l < u)
{
while(nodes[l] <= nuttruc && l < up)
l++;
while(nodes[u] > nuttruc)
u--;
if(l < u)
{
// doi cho cap nut sai vi tri
temp = nodes[l];
nodes[l] = nodes[u];
nodes[u] = temp;
}
}
// doi cho hia nut tai low va u (luc nay u la vi tri nut truc)
nodes[low] = nodes[u];
nodes[u] = nuttruc;
*pivot = u;
}

Nhận xét, so sánh
  • Quick Sort phức tạp hơn Bubble Sort nhưng hiệu quả hơn.
  • Quick Sort thích hợp cho danh sách ban đầu chưa có thứ tự.
  • Quick Sort kém hiệu quả khi danh sách ban đầu gần có thứ tự. Đặc biệt với danh sách dã có thứ tự (lớn dần hoặc nhở dần) lại là trường hợp xấu nhất của giải thuật Quick Sort.
Chương trình minh họa sắp xếp một mảng kiểu int

#include
#include
void partition(int nodes [], int low, int up, int *pivot);
void QuickSort(int nodes[], int low, int up)
{
int pivot;
if(low >= up) // dieu kien dung
return;
if(low < up)
{
partition(nodes, low, up, &pivot);
QuickSort(nodes, low, pivot - 1);
QuickSort(nodes, pivot + 1, up);
}
}

void partition(int nodes [], int low, int up, int *pivot)
{
int nuttruc, l, u, temp;
nuttruc = nodes[low]; // Chon nut dau lam nut truoc
l = low;
u = up;
while(l < u)
{
while(nodes[l] <= nuttruc && l < up)
l++;
while(nodes[u] > nuttruc)
u--;
if(l < u)
{
// doi cho cap nut sai vi tri
temp = nodes[l];
nodes[l] = nodes[u];
nodes[u] = temp;
}
}
// doi cho hia nut tai low va u (luc nay u la vi tri nut truc)
nodes[low] = nodes[u];
nodes[u] = nuttruc;
*pivot = u;
}


void main()
{
int mang[7];
for(int i = 0;i < 7;i++)
{
cout<<"Nhap vao phan tu thu "<<(i+1)<<": ";
cin>>mang[i];
}
cout<<endl;
for(int i = 0;i < 7;i++)
{
cout<<mang[i]<<" ";
}
QuickSort(mang, 0, 7);
cout<<endl<<endl<<"danh sach sau khi da sap xep: ";
for(int i = 0;i < 7;i++)
{
cout<<mang[i]<<" ";
}
getch();
}

Heap Sort

Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).
Xem thêm chi tiết tại đây.
http://www.uit.edu.vn/data/gtrinh/TH103/Htm/Bai04.htm

#include <>
#include <>
int heapSize = 10;
void print(int a[])
{
for (int i = 0; i <= 9; i++)
{
cout << a[i] << "-";
}
cout << endl;
}

int parent(int i)
{
if(i==1)
return 0;

if(i%2==0)
return ( (i / 2)-1);
else
return ( (i / 2));
}

int left(int i)
{
return (2 * i) + 1;
}

int right(int i)
{
return (2 * i) + 2;
}

void heapify(int a[], int i)
{
int l = left(i), great;
int r = right(i);
if ( (a[l] > a[i]) && (l < heapSize))
{
great = l;
}
else {
great = i;
}
if ( (a[r] > a[great]) && (r < heapSize))
{
great = r;
}
if (great != i)
{
int temp = a[i];
a[i] = a[great];
a[great] = temp;
heapify(a, great);
}
}

void BuildMaxHeap(int a[])
{
for (int i = (heapSize - 1) / 2; i >= 0; i--)
{
heapify(a, i);
print(a);
}
}

void HeapSort(int a[]) {
BuildMaxHeap(a);
for (int i = heapSize; i > 0; i--)
{
int temp = a[0];
a[0] = a[heapSize - 1];
a[heapSize - 1] = temp;
heapSize = heapSize - 1;
heapify(a, 0);
}

}

void main()
{
int arr[] = {2, 9, 3, 6, 1, 4, 5, 7, 0, 8};
HeapSort(arr);
print(arr);
}

Cấu trúc dữ liệu chương 2 c Sắp xếp

4. Các phương pháp sắp xếp nội

Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử
Sắp xếp dãy số a1 , a2 ,... ,aN là thực hiện việc bố trí lại các phần tử sao cho hình thành được dãy mới ak1 , ak2 ,... ,akN có thứ tự ( giả sử xét thứ tự tăng) nghĩa là aki £ aki-1. Mà để quyết định được những tình huống cần thay đổi vị trí các phần tử trong dãy, cần dựa vào kết quả của một loạt phép so sánh. Chính vì vậy, hai thao tác so sánh và gán là các thao tác cơ bản của hầu hết các thuật toán sắp xếp.

4.1 Các phương pháp sắp xếp có độ phức tạp N2
a Phương pháp chọn trực tiếp (SelectionSort)

Giải thuật
Ta thấy rằng, nếu mảng có thứ tự, phần tử ai luôn là min(ai, ai+1, ., an-1). Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế: chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành; sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có N phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện N-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy. Các bước tiến hành như sau :
Bước 1: i = 1;
Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N]
Bước 3 : Hoán vị a[min] và a[i]
Bước 4 : Nếu i £ N-1 thì i = i+1; Lặp lại Bước 2
Ngược lại
: Dừng. //N-1 phần tử đã nằm đúng vị trí.

Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15

Cài đặt
Cài đặt thuật toán sắp xếp chọn trực tiếp thành hàm SelectionSort
void SelectionSort(int a[],int N )
{ int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i<N-1 ; i++)
{
min = i;
for(int j = i+1; j <N ; j++)
if (a[j ] < a[min])
min = j; // ghi nhận vị trí phần tử hiện nhỏ nhất
Hoanvi(a[min], a[i]);
}
}

Ðánh giá giải thuật
Ðối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng phép so sánh này không phụ thuộc vào tình trạng của dãy số ban đầu, do vậy trong mọi trường hợp có thể kết luận :
Số lần so sánh =
Số lần hoán vị (một hoán vị bằng 3 phép gán) lại phụ thuộc vào tình trạng ban đầu của dãy số, ta chỉ có thể ước lược trong từng trường hợp như sau :
Trường hợp Số lần so sánh Số phép gán
Tốt nhất n(n-1)/2 0
Xấu nhất n(n-1)/2 3n(n-1)/2

b. Phương pháp Chèn trực tiếp (InsertionSort)

Giải thuật
Giả sử có một dãy a1 , a2 ,... ,an trong đó i phần tử đầu tiên a1 , a2 ,... ,ai-1 đã có thứ tự. Ý tưởng chính của giải thuật sắp xếp bằng phương pháp chèn trực tiếp là tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a1 , a2 ,... ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 £ ai < ak (1£k£i).
Cho dãy ban đầu a1 , a2 ,... ,an, ta có thể xem như đã có đoạn gồm một phần tử a1 đã được sắp, sau đó thêm a2 vào đoạn a1 sẽ có đoạn a1 a2 được sắp; tiếp tục thêm a3 vào đoạn a1 a2 để có đoạn a1 a2 a3 được sắp; tiếp tục cho đến khi thêm xong aN vào đoạn a1 a2 ...aN-1 sẽ có dãy a1 a2.... aN được sắp. Các bước tiến hành như sau :
Bước 1: i = 2; // giả sử có đoạn a[1] đã được sắp
Bước 2: x = a[i];
Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào
Bước 3
: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i]
Bước 4: a[pos] = x; // có đoạn a[1]..a[i] đã được sắp
Bước 5: i = i+1;
Nếu i £ n : Lặp lại Bước 2.
Ngược lại
: Dừng.


Cài đặt
Cài đặt thuật toán sắp xếp chèn trực tiếp thành hàm InsertionSort
void InsertionSort(int a[], int N )
{ int pos, i;
int x; //lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<N ; i++) //đoạn a[0] đã sắp
{
x = a[i]; pos = i-1;
// tìm vị trí chèn x
while((pos >= 0)&&(a[pos] > x))
{// kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x]; // chèn x vào dãy
}
}

Nhận xét
Khi tìm vị trí thích hợp để chèn a[i] vào đoạn a[0] đến a[i-1], do đoạn đã được sắp, nên có thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm vị trí pos, khi đó có giải thuật sắp xếp chèn nhị phân :
void BInsertionSort(int a[], int N )
{ int l,r,m,i;
int x; //lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<N ; i++)
{ x = a[i]; l = 1; r = i-1;
while(i<=r) // tìm vị trí chèn x
{ m = (l+r)/2; // tìm vị trí thích hợp m
if(x < a[m]) r = m-1;
else l = m+1;
}
for(int j = i-1 ; j >=l ; j--)
a[j+1] = a[j]; // dời các phần tử sẽ đứng sau x
a[l] = x; // chèn x vào dãy
}
}

Đánh giá giải thuật
Ðối với giải thuật chèn trực tiếp, các phép so sánh xảy ra trong mỗi vòng lặp while tìm vị trí thích hợp pos, và mỗi lần xác định vị trí đang xét không thích hợp, sẽ dời chỗ phần tử a[pos] tương ứng. Giải thuật thực hiện tất cả N-1 vòng lặp while , do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau :
Trường hợp Số phép so sánh Số phép gán
Tốt nhất
Xấu nhất

c. Phương pháp đổi chỗ trực tiếp (InterchangeSort)

Giải thuật
Bước 1 : i = 1;// bắt đầu từ đầu dãy
Bước 2 : j = i+1;//tìm các phần tử a[j] <>i
Bước 3 : Trong khi j £ N thực hiện
Nếu a
[j]<a[i]: a[i]«a[j]; //xét cặp a[i], a[j]
j = j+1;
Bước 4 : i = i+1;
Nếu i < n: Lặp lại Bước 2.
Ngược lại
: Dừng.


Cài đặt
Cài đặt thuật toán sắp xếp theo kiểu đổi chỗ trực tiếp thành hàm InterchangeSort:
void InterchangeSort(int a[], int N )
{ int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =i+1; j < N ; j++)
if(a[j ]< a[i]) // nếu có sự sai vị trí thì đổi chỗ
Hoanvi(a[i],a[j]);
}

Ðánh giá giải thuật
Ðối với giải thuật đổi chỗ trực tiếp, số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết qủa so sánh, có thể ước lược trong từng trường hợp như sau :
Trường hợp Số lần so sánh Số lần hoán vị
Tốt nhất
Xấu nhất

d. Phương pháp nổi bọt (Bubble sort)

Giải thuật
Ý tưởng chính của giải thuật là xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i . Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. Các bước tiến hành như sau :
Bước 1 : i = 1; // lần xử lý đầu tiên
Bước 2 : j = N; //Duyệt từ cuối dãy ngược về vị trí i
Trong khi (j < i) thực hiện:
Nếu a[j]<a[j-1]: a[j]«a[j-1]; //xét cặp phần tử kế cận
j = j-1;
Bước 3 : i = i+1; // lần xử lý kế tiếp
Nếu i >N-1: Hết dãy. Dừng
Ngược lại
: Lặp lại Bước 2.


Cài đặt
Cài đặt thuật toán sắp xếp theo kiểu nổi bọt thành hàm BubbleSort:
void BubleSort(int a[], int N )
{ int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =N-1; j >i ; j --)
if(a[j]< a[j-1]) // nếu sai vị trí thì đổi chỗ
Hoanvi(a[j],a[j-1]);
}

Ðánh giá giải thuật
Ðối với giải thuật nổi bọt, số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết qủa so sánh, có thể ước lược trong từng trường hợp như sau :
Trường hợp Số lần so sánh Số lần hoán vị
Tốt nhất
Xấu nhất

Nhận xét
BubbleSort có các khuyết điểm sau: không nhận diện được tình trạng dãy đã có thứ tự hay có thứ tự từng phần. Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm.

d. Phương pháp nổi bọt cải tiến (Shake sort)

Giải thuật
Giải thuật sắp xếp ShakerSort cũng dựa trên nguyên tắc đổi chỗ trực tiếp, nhưng tìm cách khắc phục các nhược điểm của BubleSort với những ý tưởng cải tiến chính như sau :
Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phiá khác nhau :
  • Lượt đi: đẩy phần tử nhỏ về đầu mảng
  • Lượt về: đẩy phần tử lớn về cuối mảng
Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.
Các bước tiến hành như sau :
Ý tưởng chính của giải thuật là xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i . Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. Các bước tiến hành như sau :
Bước 1 :
l = 1; r = n; //từ l đến r là đoạn cần được sắp xếp
k = n; // ghi nhận vị trí k xảy ra hoán vị sau cùng
// để làm cơ sở thu hẹp đoạn l đến r
Bước 2 :
Bước 2a :
j = r ; // đẩy phần tử nhỏ về đầu mảng
Trong khi (j > l) :
Nếu a[j]<a[j-1]: a[j] « a[j-1];
k = j; //lưu lại nơi xảy ra hoán vị
j = j - 1;
l = k; //loại các phần tử đã có thứ tự ở đầu dãy
Bước 2b :
j = l ; // đẩy phần tử lớn về cuối mảng
Trong khi (j < r) :
Nếu a[j]>a[j+1]:a[j] « a[j+1];
k = j; //lưu lại nơi xảy ra hoán vị
j = j+1;
r = k; //loại các phần tử đã có thứ tự ở cuối dãy
Bước 3 : Nếu l < r: Lặp lại Bước 2.


Cài đặt
Cài đặt thuật toán sắp xếp theo kiểu nổi bọt cải tiến thành hàm ShakeSort:
void ShakeSort(int a[], int N )
{ int i, j;
int left, right, k;
left = 0; right = n-1; k = n-1;
while (left < right)
{
for (j = right; j > left; j --)
{
if ( a[j]< a[j-1]) // sai vị trí thì đổi chỗ
{ Hoanvi(a[j],a[j-1]);
k = j;
}
}
left = k;
for (j = left; j < right; j ++)
{
if (a[j]> a[j+1]) // sai vị trí thì đổi chỗ
{ Hoanvi(a[j],a[j-1]);
k = j;
}
}
right = k;
}
}