Chào ace, bài này chúng ta sẽ tìm hiểu về QuickSort trên danh sách liên kết kép – Doubly Linked List trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Dưới đây là một đoạn code cài đặt thuật toán QuickSort theo kiểu đệ quy dành cho mảng một chiều, trong đó sử dụng phần tử cuối cùng của mảng làm pivot – phần tử chốt.
ĐOẠN CODE VÍ DỤ CÀI ĐẶT QUICKSORT THEO KIỂU ĐỆ QUY CHO MẢNG MỘT CHIỀU
/* A typical recursive implementation of Quicksort for array*/
/* This function takes last element as pivot, places the pivot element at its
correct position in sorted array, and places all smaller (smaller than
pivot) to left of pivot and all greater elements to right of pivot */
int partition (int arr[], int l, int h)
{
int x = arr[h];
int i = (l - 1);
for (int j = l; j <= h- 1; j++)
{
if (arr[j] <= x)
{
i++;
swap (&arr[i], &arr[j]);
}
}
swap (&arr[i + 1], &arr[h]);
return (i + 1);
}
/* A[] --> Array to be sorted, l --> Starting index, h --> Ending index */
void quickSort(int A[], int l, int h)
{
if (l < h)
{
int p = partition(A, l, h); /* Partitioning index */
quickSort(A, l, p - 1);
quickSort(A, p + 1, h);
}
}
Nội dung chính
1. Chúng ta có thể áp dụng thuật toán trên cho Linked List không?
Sau đây là phần code cài đặt bằng ngôn ngữ C++ dành cho danh sách liên kết kép – Doubly Linked List – DLL. Ý tưởng ở đây khá đơn giản, đầu tiên chúng ta sẽ tìm ra con trỏ trỏ đến node cuối cùng của danh sách liên kết kép. Một khi đã tìm được con trỏ trỏ đến phần tử cuối cùng của DLL, chúng ta có thể sắp xếp một cách đệ quy cái DLL này bằng cách sử dụng các con trỏ trỏ đến node đầu tiên và node cuối cùng của DLL, tương tự như hàm đệ quy trong ví dụ QuickSort dành cho mảng một chiều ở trên, khi đó chúng ta đã truyền vào cho hàm đó các indexes (chỉ số phần tử mảng) của phần tử đầu tiên và phần tử cuối cùng của mảng. Hàm partition (hàm thực hiện quá trình phân đoạn của thuật toán QuickSort) dành cho linked list cũng tương tự như hàm partition dành cho mảng một chiều. Nhưng, thay vì trả về index của phần tử pivot, thì nó sẽ trả về một con trỏ trỏ đến phần tử pivot. Trong đoạn code cài đặt bên dưới đây, hàm quickSort() chỉ đóng vai trò là một hàm đóng gói, hàm đệ quy chính ở đây là hàm _quickSort(), tương tự với hàm quickSort() trong ví dụ dành cho mảng một chiều ở trên.
Tiếp theo, chúng ta sẽ cùng tham khảo các đoạn code ví dụ cài đặt thuật toán QuickSort cho danh sách liên kết kép – Doubly Linked List được viết bằng các ngôn ngữ lập trình khác nhau:
CÁC ĐOẠN CODE VÍ DỤ CÀI ĐẶT QUICKSORT BẰNG C++ C Java C#
C
// C program to sort a linked list using Quicksort
#include <stdio.h>
#include <stdlib.h>
/* a node of the doubly linked list */
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
/* A utility function to swap two elements */
void swap ( int* a, int* b )
{ int t = *a; *a = *b; *b = t; }
// A utility function to find last node of linked list
struct Node *lastNode(struct Node *root)
{
while (root && root->next)
root = root->next;
return root;
}
/* Considers last element as pivot, places the
pivot element at its correct position in sorted array,
and places all smaller (smaller than pivot) to left
of pivot and all greater elements to right of pivot */
struct Node* partition(struct Node *l, struct Node *h)
{
// set pivot as h element
int x = h->data;
// similar to i = l-1 for array implementation
struct Node *i = l->prev;
// Similar to "for (int j = l; j <= h- 1; j++)"
for (struct Node *j = l; j != h; j = j->next)
{
if (j->data <= x)
{
// Similar to i++ for array
i = (i == NULL) ? l : i->next;
swap(&(i->data), &(j->data));
}
}
i = (i == NULL) ? l : i->next; // Similar to i++
swap(&(i->data), &(h->data));
return i;
}
/* A recursive implementation of quicksort for linked list */
void _quickSort(struct Node* l, struct Node *h)
{
if (h != NULL && l != h && l != h->next)
{
struct Node *p = partition(l, h);
_quickSort(l, p->prev);
_quickSort(p->next, h);
}
}
// The main function to sort a linked list.
// It mainly calls _quickSort()
void quickSort(struct Node *head)
{
// Find last node
struct Node *h = lastNode(head);
// Call the recursive QuickSort
_quickSort(head, h);
}
// A utility function to print contents of arr
void printList(struct Node *head)
{
while (head)
{
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
/* Function to insert a node at the
beginning of the Doubly Linked List */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)
malloc(sizeof(struct Node)); /* allocate node */
new_node->data = new_data;
/* since we are adding at the beginning,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if ((*head_ref) != NULL) (*head_ref)->prev = new_node ;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Driver Code
int main(int argc, char **argv)
{
struct Node *a = NULL;
push(&a, 5);
push(&a, 20);
push(&a, 4);
push(&a, 3);
push(&a, 30);
printf("Linked List before sorting \n");
printList(a);
quickSort(a);
printf("Linked List after sorting \n");
printList(a);
return 0;
}
C++
// A C++ program to sort a linked list using Quicksort
#include <bits/stdc++.h>
using namespace std;
/* a node of the doubly linked list */
class Node
{
public:
int data;
Node *next;
Node *prev;
};
/* A utility function to swap two elements */
void swap ( int* a, int* b )
{ int t = *a; *a = *b; *b = t; }
// A utility function to find
// last node of linked list
Node *lastNode(Node *root)
{
while (root && root->next)
root = root->next;
return root;
}
/* Considers last element as pivot,
places the pivot element at its
correct position in sorted array,
and places all smaller (smaller than
pivot) to left of pivot and all greater
elements to right of pivot */
Node* partition(Node *l, Node *h)
{
// set pivot as h element
int x = h->data;
// similar to i = l-1 for array implementation
Node *i = l->prev;
// Similar to "for (int j = l; j <= h- 1; j++)"
for (Node *j = l; j != h; j = j->next)
{
if (j->data <= x)
{
// Similar to i++ for array
i = (i == NULL)? l : i->next;
swap(&(i->data), &(j->data));
}
}
i = (i == NULL)? l : i->next; // Similar to i++
swap(&(i->data), &(h->data));
return i;
}
/* A recursive implementation
of quicksort for linked list */
void _quickSort(Node* l, Node *h)
{
if (h != NULL && l != h && l != h->next)
{
Node *p = partition(l, h);
_quickSort(l, p->prev);
_quickSort(p->next, h);
}
}
// The main function to sort a linked list.
// It mainly calls _quickSort()
void quickSort(Node *head)
{
// Find last node
Node *h = lastNode(head);
// Call the recursive QuickSort
_quickSort(head, h);
}
// A utility function to print contents of arr
void printList(Node *head)
{
while (head)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
/* Function to insert a node at the
beginging of the Doubly Linked List */
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node; /* allocate node */
new_node->data = new_data;
/* since we are adding at the
beginning, prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if ((*head_ref) != NULL) (*head_ref)->prev = new_node ;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Driver code */
int main()
{
Node *a = NULL;
push(&a, 5);
push(&a, 20);
push(&a, 4);
push(&a, 3);
push(&a, 30);
cout << "Linked List before sorting \n";
printList(a);
quickSort(a);
cout << "Linked List after sorting \n";
printList(a);
return 0;
} Java
// A Java program to sort a linked list using Quicksort
class QuickSort_using_Doubly_LinkedList{
Node head;
/* a node of the doubly linked list */
static class Node{
private int data;
private Node next;
private Node prev;
Node(int d){
data = d;
next = null;
prev = null;
}
}
// A utility function to find last node of linked list
Node lastNode(Node node){
while(node.next!=null)
node = node.next;
return node;
}
/* Considers last element as pivot, places the pivot element at its
correct position in sorted array, and places all smaller (smaller than
pivot) to left of pivot and all greater elements to right of pivot */
Node partition(Node l,Node h)
{
// set pivot as h element
int x = h.data;
// similar to i = l-1 for array implementation
Node i = l.prev;
// Similar to "for (int j = l; j <= h- 1; j++)"
for(Node j=l; j!=h; j=j.next)
{
if(j.data <= x)
{
// Similar to i++ for array
i = (i==null) ? l : i.next;
int temp = i.data;
i.data = j.data;
j.data = temp;
}
}
i = (i==null) ? l : i.next; // Similar to i++
int temp = i.data;
i.data = h.data;
h.data = temp;
return i;
}
/* A recursive implementation of quicksort for linked list */
void _quickSort(Node l,Node h)
{
if(h!=null && l!=h && l!=h.next){
Node temp = partition(l,h);
_quickSort(l,temp.prev);
_quickSort(temp.next,h);
}
}
// The main function to sort a linked list. It mainly calls _quickSort()
public void quickSort(Node node)
{
// Find last node
Node head = lastNode(node);
// Call the recursive QuickSort
_quickSort(node,head);
}
// A utility function to print contents of arr
public void printList(Node head)
{
while(head!=null){
System.out.print(head.data+" ");
head = head.next;
}
}
/* Function to insert a node at the beginning of the Doubly Linked List */
void push(int new_Data)
{
Node new_Node = new Node(new_Data); /* allocate node */
// if head is null, head = new_Node
if(head==null){
head = new_Node;
return;
}
/* link the old list off the new node */
new_Node.next = head;
/* change prev of head node to new node */
head.prev = new_Node;
/* since we are adding at the beginning, prev is always NULL */
new_Node.prev = null;
/* move the head to point to the new node */
head = new_Node;
}
/* Driver program to test above function */
public static void main(String[] args){
QuickSort_using_Doubly_LinkedList list = new QuickSort_using_Doubly_LinkedList();
list.push(5);
list.push(20);
list.push(4);
list.push(3);
list.push(30);
System.out.println("Linked List before sorting ");
list.printList(list.head);
System.out.println("\nLinked List after sorting");
list.quickSort(list.head);
list.printList(list.head);
}
} C#
// A C# program to sort a linked list using Quicksort
using System;
public class QuickSort_using_Doubly_LinkedList
{
Node head;
/* a node of the doubly linked list */
public class Node{
public int data;
public Node next;
public Node prev;
public Node(int d){
data = d;
next = null;
prev = null;
}
}
// A utility function to find the last node of linked list
Node lastNode(Node node)
{
while(node.next!=null)
node = node.next;
return node;
}
/* Considers last element as pivot,
places the pivot element at its
correct position in a sorted array,
and places all smaller (smaller than
pivot) to left of pivot and all
greater elements to right of pivot */
Node partition(Node l,Node h)
{
// set pivot as h element
int x = h.data;
// similar to i = l-1 for array implementation
Node i = l.prev;
int temp;
// Similar to "for (int j = l; j <= h- 1; j++)"
for(Node j=l; j!=h; j=j.next)
{
if(j.data <= x)
{
// Similar to i++ for array
i = (i==null) ? l : i.next;
temp = i.data;
i.data = j.data;
j.data = temp;
}
}
i = (i == null) ? l : i.next; // Similar to i++
temp = i.data;
i.data = h.data;
h.data = temp;
return i;
}
/* A recursive implementation of
quicksort for linked list */
void _quickSort(Node l,Node h)
{
if(h!=null && l!=h && l!=h.next){
Node temp = partition(l,h);
_quickSort(l,temp.prev);
_quickSort(temp.next,h);
}
}
// The main function to sort a linked list.
// It mainly calls _quickSort()
public void quickSort(Node node)
{
// Find last node
Node head = lastNode(node);
// Call the recursive QuickSort
_quickSort(node,head);
}
// A utility function to print contents of arr
public void printList(Node head)
{
while(head!=null){
Console.Write(head.data+" ");
head = head.next;
}
}
/* Function to insert a node at the
beginging of the Doubly Linked List */
void push(int new_Data)
{
Node new_Node = new Node(new_Data); /* allocate node */
// if head is null, head = new_Node
if(head==null)
{
head = new_Node;
return;
}
/* link the old list off the new node */
new_Node.next = head;
/* change prev of head node to new node */
head.prev = new_Node;
/* since we are adding at the
beginning, prev is always NULL */
new_Node.prev = null;
/* move the head to point to the new node */
head = new_Node;
}
/* Driver code */
public static void Main(String[] args){
QuickSort_using_Doubly_LinkedList list = new QuickSort_using_Doubly_LinkedList();
list.push(5);
list.push(20);
list.push(4);
list.push(3);
list.push(30);
Console.WriteLine("Linked List before sorting ");
list.printList(list.head);
Console.WriteLine("\nLinked List after sorting");
list.quickSort(list.head);
list.printList(list.head);
}
} Kết quả in ra là:
Linked List before sorting
Linked List before sorting
30 3 4 20 5
Linked List after sorting
3 4 5 20 30Độ phức tạp về thời gian: Độ phức tạp về thời gian của các đoạn code ví dụ cài đặt thuật toán QuickSort cho danh sách liên kết kép ở trên thì giống với độ phức tạp về thời gian của hàm QuickSort() dành cho mảng một chiều. Mất O(n^2) thời gian trong trường hợp xấu nhất và O(nLogn) trong trường hợp trung bình và trường hợp tốt nhất. Trường hợp xấu nhất xảy ra khi danh sách liên kết kép hay danh sách liên kết nói chung đã được sắp xếp rồi.
2. Có thể cài đặt quicksort ngẫu nhiên cho Linked List không?
QuickSort có thể được cài đặt cho Linked List nói chung khi và chỉ khi chúng ta có thể chọn được một điểm cố định làm pivot – phần tử chốt (giống như phần tử cuối cùng trong ví dụ trên). Không thể cài đặt QuickSort ngẫu nhiên một cách hiệu quả cho Linked List bằng cách chọn phần tử pivot ngẫu nhiên.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật){kind=link}