In depth single linked list quicksort details
- 2020-04-01 23:44:32
- OfStack
However, since a single linked list cannot be stored randomly like an array, there are some details to note when compared to the quicksort of an array:
1. Selection of fulcrum. Since the KTH element cannot be accessed randomly, the head pointer of the list to be sorted can be taken every time the fulcrum is selected.
2. Ergodic scale. Since it is impossible to traverse forward from the end of a single linked list, the strategy of traversing backward and forward using two Pointers is effective.
In fact, you can place smaller elements on the left side of a single linked list in a single pass. The specific method is as follows:
1) define two Pointers, pslow and pfast, where pslow points to the head node of the single-linked list and pfast points to the next node of the head node of the single-linked list;
2) use pfast to traverse the single linked list, and make pslow=pslow- for every element smaller than the fulcrum > Next, and then data exchange with pslow.
3. Data exchange mode: directly exchange the part pointed by the data pointer of the linked list, without having to exchange the linked list node itself.
Based on the above ideas, single linked list quicksort is implemented as follows:
#include<iostream>
#include<ctime>
using namespace std;
//Single linked list node
struct SList
{
int data;
struct SList* next;
};
void bulid_slist(SList** phead, int n) //Pointer to a pointer
{
int i;
SList* ptr = *phead;
for(i = 0; i < n; ++i)
{
SList* temp = new SList;
temp->data = rand() % n; //Generate n random Numbers up to n
temp->next = NULL;
if(ptr == NULL)
{
*phead = temp;
ptr = temp;
}
else
{
ptr->next = temp;
ptr = ptr->next;
}
}
}
void print_slist(SList* phead) //The output list
{
SList *ptr = phead;
while(ptr)
{
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("n");
}
void my_swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void sort_slist(SList* phead, SList* pend) //Sort the linked list with the head pointer as phead and the tail pointer as pend
{
if(phead == NULL)
return ;
if(phead == pend)
return ;
SList *pslow = phead;
SList *pfast = phead->next;
SList *ptemp = phead;
while(pfast != pend)
{
if(pfast->data < phead->data) //Each time, the head node of the list to be sorted is selected as the partition benchmark
{
ptemp = pslow; //Ptemp is always the precursor of pslow
pslow = pslow->next;
my_swap(&pslow->data , &pfast->data); //The pslow pointer points to a linked list of nodes smaller than the reference
}
pfast = pfast->next;
}
my_swap(&pslow->data , &phead->data); // At this time The pslow pointer points to a linked list of nodes smaller than the reference The last node of head Node) switching
sort_slist(phead , pslow); //Ptemp is the previous node of the left and right segment point (benchmark)
sort_slist(pslow->next , NULL); //The right part is a linked list of nodes larger than the benchmark
}
void destroy_slist(SList* phead)
{
SList* ptr = phead;
while(ptr)
{
SList* temp = ptr;
ptr = ptr->next;
delete temp;
}
}
int main(void)
{
srand(time(NULL));
printf("Before sort single listn");
SList* phead = NULL;
bulid_slist(&phead, 100);
print_slist(phead);
printf("After sort single listn");
sort_slist(phead, NULL);
print_slist(phead);
destroy_slist(phead);
system("pause");
return 0;
}
The second method:
Select the first node of the list as the benchmark, and then make a comparison. Smaller nodes than the benchmark are put into the left side of the sub-list, and larger nodes are put into the right side of the sub-list. After scanning the sorted list, the node values of the left face list are all less than the benchmark values, and the values of the right sublist are all greater than the benchmark values, and then the benchmark is inserted into the linked list and ACTS as a bridge connecting the two sublists. Then, according to the number of nodes in the left and right sub-linked list, the smaller one is selected for recursive quicksort, while the larger one is iteratively sorted.
The variables used in the sorting function are as follows:
struct node *right; //The first node in the right sublist
struct node **left_walk, **right_walk; //As a pointer, the node to which it points is added to the corresponding sublist
struct node *pivot, *old; //Pivot is the benchmark, and old is the pointer to the loop's entire list to be sorted
The core code is as follows:
for (old = (*head)->next; old != end; old = old->next) {
if (old->data < pivot->data) { //Less than the benchmark, add to the left side of the sub-linked list, continue to compare
++left_count;
*left_walk = old; //Add the node to the list on the left,
left_walk = &(old->next);
} else { //Greater than the benchmark, add to the right sublist, continue the comparison
++right_count;
*right_walk = old;
right_walk = &(old->next);
}
}
Head to struct node * * type, pointing to the list, head end point to list of tail, may be NULL, this program is focused on the use of the pointer to pointer, * left_walk as a pointer to the node node, say the * left_walk value is the node node memory address, but there is another place also has the address of the node, that is the next node to node domain, Therefore, we can simply think that *left_walk = old is to change the next field of the node pointing to the node to the address of the node old, which may cause two situations: One is * left_walk was pointing to the old node, there is no change any change, the other is changed * right_walk point node before next to a node in the domain, the point to the node, and at the back of the middle jumps over several nodes, but doing so will not cause any problems here, either because the linked list of nodes to join the left child of the list, or add to the right of sub chain table, won't appear the condition of the missing node.
Below is a graphic illustration of the above problem:
< img style = "border = 0 border - RIGHT - WIDTH: 0 px; BORDER - TOP - WIDTH: 0 px; BORDER - BOTTOM - WIDTH: 0 px; BORDER - LEFT - WIDTH: 0 px "Alt =" "SRC =" / / files.jb51.net/file_images/article/201305/201305241252347.gif ">
Here we assume that the list values are 5, 2, 4, 6, 1 at a time. According to the program first head = left_walk refers to the node value is 5, old point to value of 2 nodes, 2 is less than 5, so add 2 to the left of the list, * left_walk = old, as we know, * left_walk points to the first node, doing so changed the head pointer value, make it points to the second node, then left_walk ward, old ward, 4 less than 5, the same reason to continue the operation, but this is a * left_walk and old point to the same node, without any change, Left_walk and old ward, greater than 5, 6 different arises at this moment, want to add it to the right of the list, so it is * right_walk = old, actually right_walk first try to & right, this sentence is equivalent to right = old, even old point to the current node as the right of the first node list, after more than a benchmark node should be added to the node, and is always added to the tail. Right_walk right now, and old ward, 1 is less than 5 should be added to the left child list, * left_walk = old, at this time * left_walk point 6, therefore the role of the statement is the next value of node 4 change, change it to 1 address, so 6 is decoupled from the original list, continue to left_walk and old back to 9 nodes, should be added to the right of the list, at this time * right_walk points to 1, so add 9 nodes to the back of the 6 nodes.
This is the basic sorting process, however, there is a problem to be understood, for example, there are nodes in order struct node *a, *b, *c, node **p, p = &b, if *p = c, that is, the actual effect is a-
>
Next = c; We know that this corresponds to the value of the next field of this a. P is just a pointer to the address of the node that b points to, so how can we change the value of *p to next of a? Left_walk is initialized as head, so the first execution of *left_walk is to point the head to the beginning node of the left list, and then left_walk is assigned to &(old-)
>
Next), this sentence is interesting, let's take a look at the following situation in the execution of *left_walk=old, we can simply use an equivalent substitution, *left_walk=old is the same as *&(old-)
>
Next) = old
>
Nex is equal to old, but this old doesn't have to be old minus
>
Next should point to a node that left_walk and right_walk both point to their old node, but are different.
We're not done here, we've just done one partition, we've put the benchmark in the right place, and we're going to keep going, but the next one is a little bit simpler, which is to recursively sort the smaller list, and iterate over the larger list.
The complete code is as follows:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//Linked list node & NBSP; & have spent
struct node
{
int data;
struct node *next;
};
//List quicksort function
void QListSort(struct node **head,struct node *h);
//Print linked list & NBSP; & have spent
void print_list(struct node *head)
{
struct node *p;
for (p = head; p != NULL; p = p->next)
{
printf("%d ", p->data);
}
printf("n");
}
int main(void)
{
struct node *head = NULL;
struct node *p;
int i;
srand((unsigned)time(NULL));
for (i = 1; i < 11; ++i)
{
p = (struct node*)malloc(sizeof(struct node));
p->data = rand() % 100 + 1;
if(head == NULL)
{
head = p;
head->next = NULL;
}
else
{
p->next = head->next;
head->next = p;
}
}
print_list(head);
printf("---------------------------------n");
QListSort(&head,NULL);
print_list(head);
system("pause");
return 0;
}
void QListSort(struct node **head, struct node *end)
{
struct node *right;
struct node **left_walk, **right_walk;
struct node *pivot, *old;
int count, left_count, right_count;
if (*head == end)
return;
do {
pivot = *head;
left_walk = head;
right_walk = &right;
left_count = right_count = 0;
//Take the first node as the benchmark for comparison, and the one smaller than the benchmark is in the left sublist, & PI; & have spent
//Greater than the benchmark is in the right sublist & NBSP; & have spent
for (old = (*head)->next; old != end; old = old->next)
{
if (old->data < pivot->data)
{ //Less than the benchmark, add to the left side of the sub-list, continue to compare & NBSP; & have spent
++left_count;
*left_walk = old; //Add the node to the list on the left, & NBSP; & have spent
left_walk = &(old->next);
}
else
{ //Greater than the benchmark, add to the sublist on the right, and continue to compare & NBSP; & have spent
++right_count;
*right_walk = old;
right_walk = &(old->next);
}
}
//Merge linked lists & NBSP; & have spent
*right_walk = end; //Ending the right list & NBSP; & have spent
*left_walk = pivot; //Put the benchmark in the right place & NBSP; & have spent
pivot->next = right; //Combine linked lists & NBSP; & have spent
//The smaller list is sorted quickly and the larger list is sorted iteratively. & have spent & have spent
if(left_walk > right_walk)
{
QListSort(&(pivot->next), end);
end = pivot;
count = left_count;
}
else
{
QListSort(head, pivot);
head = &(pivot->next);
count = right_count;
}
}
while (count > 1);
}