Solutions: Insertion Sort List

 Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list
 

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
3. It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

.

Bài toán này mình không tự tin dùng con trỏ trên C++ nên mình sẽ code bằng Java cho đỡ bị lỗi hơn.

Thuật toán sắp xếp chọn là những thuật toán đầu tiên được tiếp cận sau sắp xếp nổi bọt và sắp xếp chọn, ý tưởng ban đầu là mặc định dãy được sắp xếp ban đầu là một phần tử nhỏ nhất, sau đó chọn 1 phần tử trong dãy chưa sắp xếp đặt đúng vào dãy đã được sắp xếp.

Như đoạn animation minh họa ở đề bài trên.

Vì vậy, chúng ta duyệt trên list, với mỗi phần tử hiện thời, được gọi là ta CHỌN phần tử đó để chuẩn bị thêm vào dãy đã được sắp xếp.

Gọi phần tử chọn là curr, ta cần quan tâm tới nó trỏ đến gì, gọi là curr.next.

Gọi dãy đã sắp xếp ban đầu là res, ban đầu, dãy gồm một phần tử siêu nhỏ (âm vô cùng).

Gọi nextRes=res.next(vì res ban đầu là âm vô cùng), gọi prevRes= res ( tại vì sau khi chọn phần tử curr để thêm vào dãy, ta sẽ cố thêm phần tử đó đứng sau prevRes)

Thấy đã khá là loằng ngoằng.. 

Nói chung, ta chạy vòng while duyệt trên dãy sắp xếp, dừng khi hết hoặc khi gặp một phần tử lớn hơn thì dừng lại, đó là chỗ cần nối.

Ví dụ dãy: -1 5 3 4 0, có đoạn -1 3 5 đã được sắp xếp:

+ curr = 4

+ curr.next = 0

+ nextRes = 3

+ prevRes = -1

Thấy nextRes=3 < 4, cập nhật: prevRes=nextRes=3, nextRes = 5

Thấy 5>4, dừng vòng lặp duyệt dãy đã sắp xếp.

Giờ đây, ta cần chèn 4 vào giữa 3 và 5. Vậy:

prevRes.next=curr;

curr.next=nextRes

Thế đó.

Sourcecode: