Insertion Sort trong danh sách liên kết đơn

Sắp xếp chèn là một giải thuật sắp xếp dựa trên so sánh in-place. Ở đây, một danh sách con luôn luôn được duy trì dưới dạng đã qua sắp xếp. Sắp xếp chèn là chèn thêm một phần tử vào danh sách con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự.

Với cấu trúc dữ liệu mảng, chúng ta tưởng tượng là: mảng gồm hai phần: một danh sách con đã được sắp xếp và phần khác là các phần tử không có thứ tự. Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh sách con (của cùng mảng đó).

Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.

Cách giải thuật sắp xếp chèn thực hiện?

Ví dụ chúng ta có một mảng gồm các phần tử không có thứ tự:

Giải thuật sắp xếp chèn so sánh hai phần tử đầu tiên:

Giải thuật tìm ra rằng cả 14 và 33 đều đã trong thứ tự tăng dần. Bây giờ, 14 là trong danh sách con đã qua sắp xếp.

Giải thuật sắp xếp chèn tiếp tục di chuyển tới phần tử kế tiếp và so sánh 33 và 27.

Và thấy rằng 33 không nằm ở vị trí đúng.

Quảng cáo

Giải thuật sắp xếp chèn tráo đổi vị trí của 33 và 27. Đồng thời cũng kiểm tra tất cả phần tử trong danh sách con đã sắp xếp. Tại đây, chúng ta thấy rằng trong danh sách con này chỉ có một phần tử 14 và 27 là lớn hơn 14. Do vậy danh sách con vẫn giữ nguyên sau khi đã tráo đổi.

Bây giờ trong danh sách con chúng ta có hai giá trị 14 và 27. Tiếp tục so sánh 33 với 10.

Hai giá trị này không theo thứ tự.

Vì thế chúng ta tráo đổi chúng.

Việc tráo đổi dẫn đến 27 và 10 không theo thứ tự.

Vì thế chúng ta cũng tráo đổi chúng.

Chúng ta lại thấy rằng 14 và 10 không theo thứ tự.

Và chúng ta tiếp tục tráo đổi hai số này. Cuối cùng, sau vòng lặp thứ 3 chúng ta có 4 phần tử.

Tiến trình trên sẽ tiếp tục diễn ra cho tới khi tất cả giá trị chưa được sắp xếp được sắp xếp hết vào trong danh sách con đã qua sắp xếp.

Tiếp theo chúng ta cùng tìm hiểu khía cạnh lập trình của giải thuật sắp xếp chèn.

Giải thuật sắp xếp chèn (Insertion Sort)

Từ minh họa trên chúng ta đã có bức tranh tổng quát về giải thuật sắp xếp chèn, từ đó chúng ta sẽ có các bước cơ bản trong giải thuật như sau:

Bước 1: Kiểm tra nếu phần tử đầu tiên đã được sắp xếp. trả về 1 Bước 2: Lấy phần tử kế tiếp Bước 3: So sánh với tất cả phần tử trong danh sách con đã qua sắp xếp Bước 4: Dịch chuyển tất cả phần tử trong danh sách con mà lớn hơn giá trị để được sắp xếp Bước 5: Chèn giá trị đó Bước 6: Lặp lại cho tới khi danh sách được sắp xếp

Giải thuật mẫu cho sắp xếp nổi bọt

Quảng cáo

Bắt đầu hàm insertionSort( A : mảng phần tử ) int holePosition int valueToInsert for i = 1 tới length(A) thực hiện: /* chọn một giá trị để chèn */ valueToInsert = A[i] holePosition = i /*xác định vị trí cho phần tử được chèn */ while holePosition > 0 và A[holePosition-1] > valueToInsert thực hiện: A[holePosition] = A[holePosition-1] holePosition = holePosition -1 kết thúc while /* chèn giá trị tại vị trí trên */ A[holePosition] = valueToInsert kết thúc for Kết thúc hàm

Để theo dõi code đầy đủ của giải thuật sắp xếp chèn trong ngôn ngữ C, mời bạn click chuột vào chương: Sắp xếp chèn (Insertion Sort) trong C.

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm và sắp xếp trong danh sách liên kết đơn.

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Chúng ta sẽ cùng nhau tìm hiều lần lượt cách tìm kiếm một giá trị index trong danh sách và thực hiện sắp xếp danh sách theo thứ tự tăng dần. Sắp xếp và tìm kiếm là hai thuật toán không thể thiếu trong các ngôn ngữ lập trình, bì vậy các bạn hãy luyện tập cho thành thạo nhé.

1. Tìm kiếm trong danh sách liên kết đơn

Trong phần này mình sẽ thực hiện tìm kiếm một giá trị index được nhập từ phím trong danh sách liên kết đơn. Đây là một thao tác đơn giản, chỉ cần ta duyệt từng phần tử trong danh sách.

Giả sử chúng ta có giá trị index = 5 là giá trị cần tìm trong danh sách. Lúc này ta cần khai báo một Node tạm pTmp để thay thế cho pHead duyệt danh sách.

Thực hiện vòng lặp while lặp từng phần tử trong danh sách với điều kiện pTmp != Null. Nếu pTmp -> data == index thì thoát khỏi vòng lặp và thông báo đã tìm thấy, ngược lại thì thông báo không tìm thấy.

/* tìm kiếm giá trị index trong danh sách */ Node * SearchNode(SingleList list,int d) { Node *pTmp=list.pHead; // khai báo biến tạm pTmp thay thế cho pHead để duyệt danh sách //Thực hiện vòng lặp các phần tử trong danh sách với điều kiện pTmp != null while(pTmp!=NULL) { if(pTmp->data==d) // nếu tìm thấy index thì thoát khỏi vòng lặp break; // chưa tìm thấy thì tiếp tục duyệt phần tử kết tiếp pTmp=pTmp->pNext; } return pTmp; }

2. Sắp xếp trong danh sắp liên kết đơn

Ở phần sắp xếp phần tử trong danh sách liên kết đơn, mình sẽ thực hiện sắp xếp bằng cách so sánh và thay đổi giá trị data chứ không thay đổi Node. Tức là chỉ so sánh các giá trị data rồi sắp xếp, các Node vẫn giữ nguyên không dịch chuyển.

Thao tác sắp xếp trong danh sách về cơ bản tương tự như các thuật toán sắp xếp khác, đơn giản chỉ là duyệt từng phần tử rồi so sánh với nhau, sau đó hoán đổi vị trí của chúng.

Bài viết này được đăng tại [free tuts .net]

Đầu tiên ta có một vòng lặp For sử dụng biến pTmp để lặp từng phần tử trong danh sách, vòng lặp For thứ hai sử dụng biến pTmp2 để lặp từng phần tử trong danh sách.

Nếu pTmp > pTmp2 thì hoán đổi vị trí giữa chúng, nếu pTmp < pTmp2 thì tiếp tục so sách các phần tử tiếp theo, cứ như vậy cho đến hết danh sách.

/* sắp xếp trong danh sách liên kết đơn theo thứ tự tăng dần */ void SortList(SingleList &list) { // for loop thứ nhất for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext) { //for loop thứ hai for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) { if(pTmp->data>pTmp2->data) // nếu giá trị trước > giá trị sau thì hoán đổi hai vị trí { int tmp=pTmp->data; pTmp->data=pTmp2->data; pTmp2->data=tmp; } } } }

3. Ví dụ tìm kiếm và sắp xếp trong danh sách liên kết đơn

Trong phần ví dụ này chúng ta sẽ sử dụng dữ liệu ở ví dụ trước để áp dụng cho việc tìm kiếm và sắp xếp. Các bạn lưu ý rằng muốn sử dụng được các thao tác mình đã hướng dẫn thì luôn luôn khái báo cấu trúc dữ liệu của DSLK đơn trước nhé.

#include using namespace std; /* Khai báo giá trị data và con trỏ pNext trỏ tới phần tử kế tiếp */ struct Node { int data;// giá trị data của node Node *pNext;// con trỏ pNext }; /* Khai báo Node đầu pHead và Node cuối pTail*/ struct SingleList { Node *pHead; //Node đầu pHead Node *pTail; // Node cuối pTail }; /* khởi tạo giá trị cho Node đầu và Node cuối */ void Initialize(SingleList &list) { list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null } /* Đếm số phần tử trong danh sách */ int SizeOfList(SingleList list) { Node *pTmp=list.pHead; int nSize=0; while(pTmp!=NULL) { pTmp=pTmp->pNext; nSize++; } return nSize; } /* tạo Node trong danh sách liên kết đơn */ Node *CreateNode(int d) { Node *pNode=new Node; //sử dụng pNode để tạo một Node mới if(pNode!=NULL) // Nếu pNode != Null, tức là pNode có giá trị thì { pNode->data=d; // gán giá trị data cho d pNode->pNext=NULL;// và cho con trỏ pNext trỏ tới giá trị Null } else // Nếu pNode == Null, tức là pNode không có giá trị thì xuất thông tin { cout<<"Error allocated memory"; } return pNode;//trả về pNode } /* chèn Node đầu danh sách */ void InsertFirst(SingleList &list,int d) { Node *pNode=CreateNode(d); if(list.pHead==NULL) { list.pHead=list.pTail=pNode; } else { pNode->pNext=list.pHead; list.pHead=pNode; } } /* chèn node vào cuối danh sách */ void InsertLast(SingleList &list,int d) { Node *pNode=CreateNode(d); if(list.pTail==NULL) { list.pHead=list.pTail=pNode; } else { list.pTail->pNext=pNode; list.pTail=pNode; } } /* chèn node vào giữa danh sách */ void InsertMid(SingleList &list, int pos, int d){ // Nếu pos < 0 hoặc pos lớn hơn kích thước của danh sách thì reuturn if(pos < 0 || pos >= SizeOfList(list)){ cout<<"Không thể chèn Node!!!"; return; } // Nếu pos == 0 thì gọi hàm InsertFirst if(pos == 0){ InsertFirst(list, d); } //Nếu pos == SizeOfList - 1 thì gọi hàm InsertLast else if(pos == SizeOfList(list)-1){ InsertLast(list, d); } //Ngược lại thì thay đổi mối liên kết giữa các phần tử, cụ thể: else{ Node *pNode = CreateNode(d); Node *pIns = list.pHead; Node *pPre = NULL; int i = 0; //thực hiện vòng lặp tìm pPre và pIns while(pIns != NULL){ if(i == pos) break; pPre = pIns; pIns = pIns ->pNext; i++; } //sau khi tìm được thì thay đổi con trỏ pNext pPre ->pNext=pNode; pNode->pNext=pIns; } } /* tìm kiếm giá trị index trong danh sách */ Node * SearchNode(SingleList list,int d) { Node *pTmp=list.pHead; // khai báo biến tạm pTmp thay thế cho pHead để duyệt danh sách //Thực hiện vòng lặp các phần tử trong danh sách với điều kiện pTmp != null while(pTmp!=NULL) { if(pTmp->data==d) // nếu tìm thấy index thì thoát khỏi vòng lặp break; // chưa tìm thấy thì tiếp tục duyệt phần tử kết tiếp pTmp=pTmp->pNext; } return pTmp; } /* sắp xếp trong danh sách liên kết đơn theo thứ tự tăng dần */ void SortList(SingleList &list) { // for loop thứ nhất for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext) { //for loop thứ hai for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) { if(pTmp->data>pTmp2->data) // nếu giá trị trước > giá trị sau thì hoán đổi hai vị trí { int tmp=pTmp->data; pTmp->data=pTmp2->data; pTmp2->data=tmp; } } } } /* hàm xuất dữ liệu */ void PrintList(SingleList list) { Node *pTmp=list.pHead; if(pTmp==NULL) { cout<<"The list is empty!"; return; } while(pTmp!=NULL) { cout<data<<" "; pTmp=pTmp->pNext; } } int main() { SingleList list; Initialize(list); //Thêm node đầu danh sách InsertFirst(list, 5); InsertFirst(list, 7); InsertFirst(list, 3); cout<<"Các Node trong danh sách sau khi InsertFirst là: "; PrintList(list); //Thêm node cuối danh sách InsertLast(list, 4); InsertLast(list, 2); InsertLast(list, 6); cout<<"\nCác Node trong danh sách sau khi InsertLast là: "; PrintList(list); //Thêm node giữa danh sách InsertMid(list, 4, 11); InsertMid(list, 2, 12); InsertMid(list, 3, 13); cout<<"\nCác Node trong danh sách sau khi InsertMid là: "; PrintList(list); //Tìm kiếm giá trị index trong danh sách int index; cout<<"\nNhập vào số bạn muốn tìm: "; cin>>index; Node *pFound = SearchNode(list, index); if(pFound == NULL){ cout<<"Không tìm thấy số "<

Kết quả:

Như vậy là chúng ta đã thực hiện xong chương trình tìm kiếm và sắp xếp các phần tử trong danh sách liên kết đơn. Cũng như kết thúc hướng dẫn thao tác tìm kiếm và sắp xếp. Chúc các bạn thực hiện thành công !!!