Bài giảng Cấu trúc dữ liệu - Chương 10: Thuật toán sắp xếp (Sort)

Khám phá chương 10 về sắp xếp trong cấu trúc dữ liệu và thuật toán, tìm hiểu các phương pháp và ứng dụng hiệu quả trong lập trình.

• Đề tài: Sort

Mục lục chi tiết

• MỤC TIÊU VÀ CHUẨN ĐẦU RA
• 10. CHƯƠNG 10: SẮP XẾP
• 10.1. Khái niệm sắp xếp
• 10.1.1. Tính ổn định của sắp xếp
• 10.1.2. Hiệu quả sắp xếp
• 10.2. Sắp xếp chèn
• 10.2.1. Sắp xếp chèn trực tiếp
• 10.2.2. Sắp xếp Shell
• 10.2.3. Hiệu quả của thuật toán sắp xếp chèn
• 10.3. Sắp xếp chọn
• 10.3.1. Sắp xếp chọn trực tiếp
• 10.3.2. Sắp xếp vun đống (Heap Sort)
• 10.3.3. Hiệu quả của thuật toán sắp xếp chọn
• 10.4. Sắp xếp đổi chỗ
• 10.4.1. Sắp xếp nổi bọt (Bubble Sort)
• 10.4.2. Hiệu quả của thuật toán sắp xếp đổi chỗ
• 10.5. Sắp xếp chia để trị (Divide-and-Conquer)

Tóm tắt

I. Tổng quan Cấu trúc dữ liệu và thuật toán Khái niệm Sắp xếp

Sắp xếp (Sorting) là một trong những khái niệm quan trọng và ứng dụng phổ biến nhất trong khoa học máy tính. Đây là nền tảng cho nhiều tác vụ xử lý dữ liệu phức tạp hơn, từ tìm kiếm thông tin trong cơ sở dữ liệu đến tối ưu hóa hiệu năng hệ thống. Trong cấu trúc dữ liệu và thuật toán, việc nắm vững các thuật toán sắp xếp là yêu cầu cơ bản. Mục tiêu chính của sắp xếp là sắp đặt lại một danh sách các phần tử theo một thứ tự nhất định, thường là tăng dần hoặc giảm dần. Để đánh giá một thuật toán, hai yếu tố cốt lõi cần được xem xét: tính ổn định và hiệu quả. Sort stability (tính ổn định của sắp xếp) đảm bảo rằng các phần tử có khóa bằng nhau sẽ duy trì thứ tự tương đối của chúng như trong dữ liệu đầu vào. Điều này cực kỳ quan trọng trong các ứng dụng thực tế, nơi dữ liệu phụ thuộc vào thứ tự ban đầu. Ví dụ, khi sắp xếp danh sách sinh viên theo điểm, nếu hai sinh viên có cùng điểm, một thuật toán ổn định sẽ giữ nguyên thứ tự của họ trong danh sách. Ngược lại, một thuật toán không ổn định có thể hoán đổi vị trí của họ một cách ngẫu nhiên. Yếu tố thứ hai là sort efficiency (hiệu quả sắp xếp), được đo lường bằng tổng số phép so sánh và số lần di chuyển phần tử. Một thuật toán hiệu quả sẽ giảm thiểu hai chỉ số này, đặc biệt khi làm việc với các tập dữ liệu lớn. Việc phân tích hiệu quả này thường được biểu diễn qua ký hiệu Big-O notation, giúp định lượng độ phức tạp thuật toán trong các trường hợp xấu nhất, tốt nhất và trung bình.

1.1. Tầm quan trọng của sắp xếp trong khoa học máy tính

Sắp xếp không chỉ là một bài toán học thuật mà còn là một công cụ thiết yếu trong các ứng dụng thực tiễn. Nó là bước tiền xử lý cho nhiều thuật toán khác. Ví dụ, các thuật toán tìm kiếm nhị phân (binary search) yêu cầu dữ liệu phải được sắp xếp trước để đạt được độ phức tạp thời gian O(log n). Trong quản lý cơ sở dữ liệu, việc sắp xếp các bản ghi theo một khóa cụ thể giúp tăng tốc độ truy vấn và tạo chỉ mục (indexing) hiệu quả. Hơn nữa, trong đồ họa máy tính, các thuật toán như 'painter's algorithm' sử dụng sắp xếp để xác định đối tượng nào được vẽ trước dựa trên khoảng cách của chúng. Việc hiểu rõ bản chất và cách hoạt động của các thuật toán sắp xếp khác nhau cho phép các nhà phát triển lựa chọn phương pháp tối ưu nhất cho từng bài toán cụ thể, cân bằng giữa tốc độ, bộ nhớ sử dụng và tính ổn định. Đây là kỹ năng cốt lõi trong bộ môn cấu trúc dữ liệu và thuật toán.

1.2. Các tiêu chí đánh giá hiệu quả một thuật toán sắp xếp

Hiệu quả của một thuật toán sắp xếp được đánh giá dựa trên nhiều tiêu chí. Tiêu chí quan trọng nhất là độ phức tạp về thời gian (time complexity), thường được biểu diễn bằng Big-O notation, mô tả tốc độ tăng trưởng thời gian thực thi khi kích thước đầu vào tăng lên. Tiêu chí thứ hai là độ phức tạp về không gian (space complexity), đo lường lượng bộ nhớ phụ mà thuật toán yêu cầu. Một số thuật toán, như Heap Sort, có thể sắp xếp tại chỗ (in-place) mà không cần nhiều bộ nhớ phụ. Ngoài ra, sort stability là một yếu tố quan trọng như đã đề cập, đặc biệt khi cần bảo toàn thứ tự của các phần tử trùng lặp. Cuối cùng, sort efficiency còn được tính bằng "tổng số phép so sánh và số lần di chuyển" (number of comparisons + number of moves), theo tài liệu của Dr. Duc Dung Nguyen. Một thuật toán có thể thực hiện ít phép so sánh nhưng lại tốn nhiều lần di chuyển dữ liệu, và ngược lại. Việc lựa chọn thuật toán phù hợp đòi hỏi phải cân nhắc tất cả các yếu tố này.

II. Hướng dẫn Sắp xếp Chèn Insertion Sort Đơn giản hiệu quả

Sắp xếp chèn (Insertion Sort) là một thuật toán sắp xếp đơn giản, hoạt động bằng cách chia danh sách thành hai phần: một phần đã được sắp xếp và một phần chưa được sắp xếp. Ở mỗi bước lặp, thuật toán lấy phần tử đầu tiên từ phần chưa sắp xếp và chèn nó vào đúng vị trí trong phần đã sắp xếp. Quá trình này được lặp lại cho đến khi không còn phần tử nào trong phần chưa sắp xếp. Phương pháp này trực quan và dễ cài đặt, tương tự như cách một người sắp xếp các lá bài trên tay. Straight Insertion Sort là biến thể cơ bản nhất. Nó hiệu quả với các tập dữ liệu nhỏ hoặc các danh sách gần như đã được sắp xếp. Tuy nhiên, độ phức tạp thuật toán trong trường hợp xấu nhất của nó là O(n²), khiến nó không phù hợp cho các tập dữ liệu lớn. Để khắc phục nhược điểm này, Shell Sort (hay còn gọi là sắp xếp theo khoảng giảm dần) được phát triển bởi Donald L. Shell. Shell Sort là một cải tiến của Insertion Sort, cho phép so sánh và hoán đổi các phần tử ở xa nhau. Thay vì chỉ so sánh các phần tử liền kề, nó sắp xếp các danh sách con được tạo thành từ các phần tử cách nhau một khoảng (increment). Khoảng này sẽ giảm dần sau mỗi lần lặp cho đến khi bằng 1, và ở bước cuối cùng, thuật toán thực chất là một Straight Insertion Sort trên toàn bộ danh sách, nhưng lúc này danh sách đã gần như được sắp xếp nên chạy rất nhanh.

2.1. Cách hoạt động của Straight Insertion Sort từng bước

Straight Insertion Sort bắt đầu với giả định rằng phần tử đầu tiên của danh sách đã được sắp xếp. Sau đó, nó duyệt qua từng phần tử còn lại. Với mỗi phần tử hiện tại, nó so sánh ngược với các phần tử trong phần đã sắp xếp. Nếu phần tử hiện tại nhỏ hơn phần tử đang được so sánh, phần tử trong vùng đã sắp xếp sẽ được dịch sang phải một vị trí. Quá trình này tiếp tục cho đến khi tìm thấy vị trí đúng (một phần tử nhỏ hơn hoặc bằng phần tử hiện tại, hoặc đến đầu danh sách). Tại đó, phần tử hiện tại sẽ được chèn vào. Thuật toán này được mô tả trong tài liệu gốc: "In each pass, the first element of the unsorted sublist is inserted into the sorted sublist". Mặc dù đơn giản, độ phức tạp của nó là O(n²) vì trong trường hợp xấu nhất (danh sách sắp xếp ngược), mỗi lần chèn có thể yêu cầu duyệt qua toàn bộ phần đã sắp xếp.

2.2. Cải tiến với Shell Sort Thuật toán sắp xếp theo khoảng giảm dần

Shell Sort là một phương pháp cải tiến đáng kể từ Insertion Sort. Ý tưởng cốt lõi là chia danh sách ban đầu thành nhiều danh sách con, với các phần tử được chọn theo một khoảng cách (increment k). Sau đó, áp dụng Insertion Sort trên từng danh sách con này. Quá trình này được lặp lại với các giá trị khoảng k giảm dần. Một điểm quan trọng là chuỗi các giá trị khoảng không nên là bội số của nhau để tránh việc so sánh lặp lại các phần tử giống nhau ở các bước khác nhau. Cuối cùng, khi khoảng k bằng 1, thuật toán thực hiện một lần Insertion Sort trên toàn bộ danh sách, nhưng lúc này dữ liệu đã được sắp xếp một phần, giúp giảm đáng kể số lần di chuyển. Nhờ chiến lược này, độ phức tạp của Shell Sort được cải thiện đáng kể. Các nghiên cứu thực nghiệm cho thấy độ phức tạp của nó vào khoảng O(n¹·²⁵), nhanh hơn nhiều so với O(n²) của Insertion Sort.

III. Bí quyết Sắp xếp Chọn Selection Sort và Heap Sort hiệu năng cao

Sắp xếp chọn (Selection Sort) là một nhóm các thuật toán sắp xếp dựa trên nguyên tắc lặp đi lặp lại việc tìm phần tử nhỏ nhất (hoặc lớn nhất) từ phần chưa được sắp xếp của danh sách và đặt nó vào đầu phần đã được sắp xếp. Giống như Insertion Sort, nó cũng chia danh sách thành hai phần. Straight Selection Sort là đại diện tiêu biểu cho phương pháp này. Trong mỗi lượt, nó quét qua toàn bộ phần chưa sắp xếp để tìm phần tử nhỏ nhất, sau đó hoán đổi phần tử đó với phần tử đầu tiên của phần chưa sắp xếp. Mặc dù ý tưởng đơn giản, số lượng phép so sánh của nó luôn là O(n²), bất kể tình trạng ban đầu của danh sách. Điều này làm cho nó không hiệu quả trên các tập dữ liệu lớn. Tuy nhiên, một ưu điểm của nó là số lần hoán đổi (swap) rất ít, tối đa là n-1 lần. Để cải thiện hiệu suất, Heap Sort (Sắp xếp vun đống) được ra đời. Heap Sort cũng là một dạng của selection sort nhưng thông minh hơn. Nó sử dụng một cấu trúc dữ liệu đặc biệt gọi là heap (đống) để tìm phần tử lớn nhất một cách hiệu quả. Đầu tiên, nó xây dựng một max-heap từ danh sách đầu vào. Sau đó, nó liên tục lấy phần tử lớn nhất (nằm ở gốc của heap), hoán đổi với phần tử cuối cùng của heap, giảm kích thước heap đi một, và tái cấu trúc lại heap. Quá trình này đảm bảo rằng phần tử lớn nhất luôn ở gốc và có thể được truy cập nhanh chóng.

3.1. Tìm hiểu Straight Selection Sort Chọn và hoán đổi phần tử

Cơ chế của Straight Selection Sort rất rõ ràng. Nó duyệt qua danh sách từ đầu đến gần cuối. Ở vòng lặp thứ i, nó tìm kiếm phần tử nhỏ nhất trong đoạn từ vị trí i đến cuối danh sách. Sau khi tìm thấy, nó sẽ hoán đổi phần tử nhỏ nhất đó với phần tử tại vị trí i. Vòng lặp tiếp theo sẽ bắt đầu từ vị trí i+1. Quá trình này được mô tả trong tài liệu gốc: "In each pass, in the unsorted sublist, the smallest element is selected and exchanged with the first element". Thuật toán này luôn thực hiện n(n-1)/2 phép so sánh, dẫn đến độ phức tạp thời gian là O(n²). Nó không phải là một thuật toán ổn định (sort stability) vì việc hoán đổi có thể làm thay đổi thứ tự tương đối của các phần tử bằng nhau.

3.2. Tối ưu hóa với Heap Sort Sắp xếp vun đống và độ phức tạp O n log n

Heap Sort là một thuật toán sắp xếp dựa trên so sánh, mang lại hiệu suất vượt trội so với các thuật toán O(n²). Nó tận dụng cấu trúc dữ liệu heap. Quá trình gồm hai giai đoạn chính: 1) Xây dựng heap: Chuyển mảng đầu vào thành một max-heap, nơi mỗi nút cha lớn hơn hoặc bằng các nút con của nó. 2) Sắp xếp: Lặp lại n-1 lần, hoán đổi phần tử gốc (lớn nhất) với phần tử cuối cùng của heap, sau đó giảm kích thước heap và gọi thủ tục ReheapDown (hoặc heapify) để duy trì thuộc tính của max-heap. Nhờ cấu trúc heap, việc tìm phần tử lớn nhất chỉ mất O(1), và việc tái cấu trúc heap sau mỗi lần hoán đổi mất O(log n). Do đó, độ phức tạp thuật toán tổng thể của Heap Sort là O(n log n) trong mọi trường hợp (xấu nhất, trung bình và tốt nhất). Đây là một thuật toán sắp xếp tại chỗ (in-place) hiệu quả.

IV. Phân tích phương pháp Sắp xếp trao đổi Exchange Sort Bubble Sort

Sắp xếp trao đổi (Exchange Sort) là một nhóm các thuật toán sắp xếp hoạt động bằng cách liên tục so sánh và hoán đổi các cặp phần tử bị sai thứ tự cho đến khi toàn bộ danh sách được sắp xếp. Bubble Sort (Sắp xếp nổi bọt) là thuật toán nổi tiếng và đơn giản nhất trong nhóm này. Tên gọi "nổi bọt" xuất phát từ cách các phần tử nhỏ hơn (hoặc lớn hơn) dần dần "nổi" lên vị trí đúng của chúng trong danh sách, giống như bọt khí trong nước. Cơ chế của Bubble Sort là duyệt qua danh sách nhiều lần. Trong mỗi lần duyệt, nó so sánh các cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự. Sau mỗi lần duyệt, phần tử lớn nhất sẽ được đẩy về cuối danh sách. Do đó, ở lần duyệt tiếp theo, phạm vi duyệt có thể giảm đi một phần tử. Thuật toán sẽ kết thúc khi một lần duyệt hoàn tất mà không có bất kỳ sự hoán đổi nào xảy ra, điều này cho thấy danh sách đã được sắp xếp. Mặc dù dễ hiểu và cài đặt, Bubble Sort cực kỳ không hiệu quả cho các tập dữ liệu lớn. Độ phức tạp thuật toán của nó trong trường hợp trung bình và xấu nhất là O(n²), tương tự như Insertion Sort và Selection Sort. Nó chỉ hiệu quả trong các trường hợp rất đặc biệt, chẳng hạn như kiểm tra xem một danh sách nhỏ đã được sắp xếp hay chưa.

4.1. Cơ chế nổi bọt của thuật toán Bubble Sort trong thực thi

Hoạt động của Bubble Sort dựa trên nguyên tắc cơ bản là so sánh và hoán đổi. Thuật toán bắt đầu từ đầu danh sách, so sánh data[0] và data[1], hoán đổi nếu data[0] > data[1]. Sau đó, nó chuyển sang cặp tiếp theo, data[1] và data[2], và lặp lại quá trình. Quá trình này tiếp tục cho đến cuối danh sách. Kết thúc lần duyệt đầu tiên, phần tử lớn nhất chắc chắn sẽ nằm ở vị trí cuối cùng. Lần duyệt thứ hai sẽ lặp lại quy trình tương tự nhưng chỉ cần duyệt đến phần tử áp chót, vì phần tử cuối cùng đã đúng vị trí. Theo tài liệu, "In each pass, the smallest element is bubbled from the unsorted sublist and moved to the sorted sublist" (mô tả này có thể áp dụng cho việc đưa phần tử nhỏ nhất lên đầu hoặc lớn nhất xuống cuối). Một phiên bản cải tiến có thể thêm một cờ (flag) để kiểm tra xem có bất kỳ hoán đổi nào xảy ra trong một lượt duyệt hay không. Nếu không, thuật toán có thể dừng sớm.

4.2. Đánh giá hiệu suất thực tế của Bubble Sort Độ phức tạp O n²

Về mặt hiệu suất, Bubble Sort là một trong những thuật toán sắp xếp chậm nhất. Số lượng phép so sánh của nó luôn là (n-1) + (n-2) + ... + 1, dẫn đến độ phức tạp là O(n²). Trong trường hợp xấu nhất (danh sách được sắp xếp ngược), số lần hoán đổi cũng là O(n²). Ngay cả trong trường hợp tốt nhất (danh sách đã được sắp xếp), phiên bản cải tiến có thể dừng sau một lần duyệt, cho độ phức tạp O(n), nhưng đây là trường hợp hiếm. Do hiệu suất kém, Bubble Sort hầu như không được sử dụng trong các ứng dụng thực tế mà chỉ dùng cho mục đích giảng dạy để giới thiệu về khái niệm thuật toán sắp xếp. Các thuật toán như Heap Sort hay các thuật toán dựa trên Divide-and-Conquer như Merge Sort, Quick Sort luôn là lựa chọn tốt hơn cho các bài toán sắp xếp thông thường.

V. Tổng kết Cấu trúc dữ liệu và thuật toán Lựa chọn thuật toán

Chương 10 về Sắp xếp trong môn cấu trúc dữ liệu và thuật toán đã giới thiệu một loạt các phương pháp cơ bản, từ các thuật toán đơn giản như Insertion Sort, Selection Sort, Bubble Sort đến các thuật toán phức tạp và hiệu quả hơn như Shell Sort và Heap Sort. Mỗi thuật toán đều có những ưu và nhược điểm riêng, và không có một thuật toán nào là tốt nhất cho mọi tình huống. Các thuật toán có độ phức tạp O(n²) (Insertion, Selection, Bubble) thường dễ cài đặt và phù hợp với các tập dữ liệu nhỏ hoặc gần như đã được sắp xếp. Trong khi đó, các thuật toán có độ phức tạp O(n log n) (Heap Sort) thể hiện hiệu năng vượt trội khi xử lý các tập dữ liệu lớn. Việc lựa chọn thuật toán sắp xếp phù hợp phụ thuộc vào việc phân tích các yếu tố của bài toán: kích thước dữ liệu, yêu cầu về bộ nhớ, yêu cầu về tính ổn định (sort stability), và trạng thái ban đầu của dữ liệu. Hiểu rõ bản chất của từng thuật toán là chìa khóa để xây dựng các ứng dụng hiệu quả và tối ưu. Bài học này cũng đặt nền móng cho việc tìm hiểu các kỹ thuật sắp xếp nâng cao hơn, đặc biệt là những thuật toán dựa trên chiến lược Divide-and-Conquer (Chia để trị).

5.1. So sánh tổng quan hiệu năng các thuật toán sắp xếp đã học

Tóm tắt hiệu năng các thuật toán: Straight Insertion Sort có độ phức tạp O(n²) nhưng hiệu quả với dữ liệu gần sắp xếp. Shell Sort cải tiến từ Insertion Sort, đạt độ phức tạp trung bình O(n¹·²⁵). Straight Selection Sort luôn có độ phức tạp O(n²) nhưng số lần hoán đổi ít. Heap Sort nổi bật với độ phức tạp O(n log n) trong mọi trường hợp và không cần thêm bộ nhớ phụ. Bubble Sort cũng có độ phức tạp O(n²) và thường là thuật toán chậm nhất. Bảng so sánh này giúp nhà phát triển nhanh chóng đưa ra quyết định dựa trên yêu cầu cụ thể của bài toán, cân bằng giữa tốc độ thực thi và chi phí cài đặt.

5.2. Giới thiệu chiến lược Chia để trị Divide and Conquer trong sắp xếp

Chiến lược Divide-and-Conquer (Chia để trị) là một phương pháp thiết kế thuật toán mạnh mẽ được đề cập trong tài liệu. Nó giải quyết một bài toán lớn bằng cách: 1) Chia (Divide) bài toán thành các bài toán con nhỏ hơn. 2) Trị (Conquer): Giải các bài toán con một cách đệ quy. 3) Tổng hợp (Combine): Kết hợp kết quả của các bài toán con để có được lời giải cho bài toán ban đầu. Nhiều thuật toán sắp xếp hiệu quả nhất, như Merge Sort và Quick Sort, đều được xây dựng dựa trên nguyên tắc này. Hiểu về Divide-and-Conquer sẽ mở ra một hướng tiếp cận mới để giải quyết không chỉ bài toán sắp xếp mà còn nhiều vấn đề phức tạp khác trong lĩnh vực cấu trúc dữ liệu và thuật toán.

Trích đoạn nội dung tài liệu

Data Structure and Algorithms [CO2003] Chapter 10 - Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Faculty of Computer Science and Engineering Hochiminh city University of Technology Contents 1. Divide-and-Conquer Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 1 / 57 Outcomes • L.1 - Depict the working steps of sorting algorithms step-by-steps.2 - Describe sorting algorithms by using pseudocode.3 - Implement sorting algorithms using C/C++ .4 - Analyze the complexity and develop experiment (program) to evaluate sorting algorithms.5 - Use sorting algorithms for problems in real-life.4 - Develop recursive implementations for methods supplied for the following structures: list, tree, heap, searching, and graphs.2 - Analyze algorithms and use Big-O notation to characterize the computational complexity of algorithms composed by using the following control structures: sequence, branching, and iteration (not recursion).

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 2 / 57 Sorting concepts Sorting One of the most important concepts and common applications in computing. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 3 / 57 Sorting Sort stability: data with equal keys maintain their relative input order in the output.

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 4 / 57 Sorting Sort efficiency: a measure of the relative efficiency of a sort = number of comparisons + number of moves. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 5 / 57 Sorting Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 6 / 57 Insertion Sort Straight Insertion Sort • The list is divided into two parts: sorted and unsorted. • In each pass, the first element of the unsorted sublist is inserted into the sorted sublist. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 7 / 57 Straight Insertion Sort Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 8 / 57 Straight Insertion Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 9 / 57 Straight Insertion Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 10 / 57 Straight Insertion Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 11 / 57 Straight Insertion Sort Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 12 / 57 Straight Insertion Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 13 / 57 Straight Insertion Sort Algorithm InsertionSort() Sorts the contiguous list using straight insertion sort. if count > 1 then current = 1 while current < count do temp = data[current] walker = current - 1 while walker >= 0 AND temp.key do data[walker+1] = data[walker] walker = walker - 1 end data[walker+1] = temp current = current + 1 end end Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 14 / 57 Shell Sort • Named after its creator Donald L.

• Given a list of N elements, the list is divided into K segments (K is called the increment). • Each segment contains N/K or more elements. • Segments are dispersed throughout the list. • Also is called diminishing-increment sort.

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 15 / 57 Shell Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 16 / 57 Shell Sort • For the value of K in each iteration, sort the K segments. • After each iteration, K is reduced until it is 1 in the final iteration.

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 17 / 57 Example of Shell Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 18 / 57 Example of Shell Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 19 / 57 Choosing incremental values • From more of the comparisons, it is better when we can receive more new information.

• Incremental values should not be multiples of each other, other wise, the same keys compared on one pass would be compared again at the next. • The final incremental value must be 1. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 20 / 57 Choosing incremental values • Incremental values may be: 1, 4, 13, 40, 121,.

kt = 1 ki−1 = 3 ∗ ki + 1 t = | log3 n| − 1 • or: 1, 3, 7, 15, 31,. kt = 1 ki−1 = 2 ∗ ki + 1 t = | log2 n| − 1 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 21 / 57 Shell Sort Algorithm ShellSort() Sorts the contiguous list using Shell sort. k = first_incremental_value while k >= 1 do segment = 1 while segment <= k do SortSegment(segment) segment = segment + 1 end k = next_incremental_value end End ShellSort Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 22 / 57 Shell Sort Algorithm SortSegment(val segment <int>, val k <int>) Sorts the segment beginning at segment using insertion sort, step between elements in the segment is k. current = segment + k while current < count do temp = data[current] walker = current - k while walker >=0 AND temp.key do data[walker + k] = data[walker] walker = walker - k end data[walker + k] = temp current = current + k end End SortSegment Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 23 / 57 Insertion Sort Efficiency • Straight insertion sort: f (n) = n(n + 1)/2 = O(n2 ) • Shell sort: O(n1.25 ) (Empirical study) Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 24 / 57 Selection Sort Selection Sort In each pass, the smallest/largest item is selected and placed in a sorted list.

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 25 / 57 Straight Selection Sort • The list is divided into two parts: sorted and unsorted. • In each pass, in the unsorted sublist, the smallest element is selected and exchanged with the first element. Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 26 / 57 Straight Selection Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 27 / 57 Straight Selection Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 28 / 57 Straight Selection Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 29 / 57 Straight Selection Sort Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 30 / 57 Straight Selection Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 31 / 57 Straight Selection Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 32 / 57 Straight Selection Sort Algorithm SelectionSort() Sorts the contiguous list using straight selection sort. current = 0 while current < count - 1 do smallest = current walker = current + 1 while walker < count do if data [walker].key then smallest = walker end walker = walker + 1 end swap(current, smallest) current = current + 1 end Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 33 / 57 Heap Sort • The unsorted sublist is organized into a heap. • In each pass, in the unsorted sublist, the largest element is selected and exchanged with the last element. • The the heap is reheaped. Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 34 / 57 Heap Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 35 / 57 Heap Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 36 / 57 Heap Sort Algorithm HeapSort() Sorts the contiguous list using heap sort. position = count/2 - 1 while position >= 0 do ReheapDown(position, count - 1) position = position - 1 end last = count - 1 while last > 0 do swap(0, last) last = last - 1 ReheapDown(0, last - 1) end End HeapSort Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 37 / 57 Selection Sort Efficiency • Straight selection sort: O(n2 ) • Heap sort: O(nlog2 n) Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 38 / 57 Exchange Sort Exchange Sort • In each pass, elements that are out of order are exchanged, until the entire list is sorted. • Exchange is extensively used. Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 39 / 57 Bubble Sort • The list is divided into two parts: sorted and unsorted. • In each pass, the smallest element is bubbled from the unsorted sublist and moved to the sorted sublist. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 40 / 57 Bubble Sort Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 41 / 57 Bubble Sort Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 42 / 57 Bubble Sort Algorithm BubbleSort() Sorts the contiguous list using bubble sort. current = 0, flag = False while current < count AND flag = False do walker = count - 1 flag = True while walker > current do if data [walker].key then flag = False swap(walker, walker - 1) end walker = walker - 1 end current = current + 1 end Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 43 / 57 Exchange Sort Efficiency • Bubble sort: f (n) = n(n + 1)/2 = O(n2 ) Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 44 / 57 Divide-and-Conquer