Traverse list and count '0', '1' and '2'. (O(N))
int zerosCount = 10;
int onesCount = 5;
int twosCount = 4;
Traverse list and fill according to counters. (O(N))
Time: O(N)
Space: O(1)
/* Program to reverse a doubly linked list */
#include
#include
/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};
struct node* sort(struct node *head)
{
struct node* current=head;
struct node* temp=NULL;
if (current!= NULL)
{
int zeroCount = 0;
int oneCount = 0;
int twoCount = 0;
//Find out the count for 0, 1 and 2
while(current!=NULL)
{
if (current->data == 0) {
zeroCount++;
} else if (current->data == 1) {
oneCount++;
} else if (current->data == 2) {
twoCount++;
}
else
{
break;
}
current=current->next;
}
//Fill a based on counts of 0, 1 and 2
temp=head;
for (int i = 0; i < zeroCount; i++)
{
temp->data = 0;
temp=temp->next;
}
for (int i = 0; i < oneCount; i++) {
temp->data = 1;
temp=temp->next;
}
for (int i = 0; i < twoCount; i++) {
temp->data = 2;
temp=temp->next;
}
}
temp=head;
return temp;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* since we are adding at the begining,
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;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 2);
sort(head);
printf("\n Original Linked list ");
printList(head);
getchar();
}
Not Efficient Because it Requires 3 Paas Over Array
TC O(n)
SC O(1)
Run Here https://ideone.com/XdipA
As You Can See Above method Will take More Instruction to Execute , because it requires same thing to be do in three pass can't we do in single pass . yeas there exist an algorithm Named 3-Way Partioning or Dutch National Flag Algorithm , so that we can finish it in single pass & can make program more efficient.
But Above Algo Requires Mid points to be calculated , Again & Again until Array or list is not empty ..so think getting the mid point in array can be done in O(1) & for n items we repeat the things & can be done in O(logn) because we know starting & ending of array but what to do in-case of linked list calculating the mid point will take O(logn) & for n item this algo will take O(nlogn) ..ohh we are beyond of limit ..we din't expected this Time for an O(n) Solution...but we can add some pointer overhead for maintaining start & end location of o,1,2 & then in finally we can append 1's to 2's & 2's to 3's isn't ..yes it will work & we have done
so Algorithms is
1 Divide the list into 3 different lists,
2 list0 having all 0's, list2 having all 1's and list2 having all 2's
3 Concatenate list0, list1 and list2
2nd Method Implementation
/* Program to reverse a doubly linked list */
#include
#include
/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};
struct node* sort(struct node *head)
{
struct node* current=head;
struct node* start0=NULL;
struct node* start1=NULL;
struct node* start2=NULL;
struct node* n0=NULL;
struct node* n1=NULL;
struct node* n2=NULL;
if(!current)
return NULL;
while(current)
{
switch(current->data)
{
case 0:
if(n0)
{
n0->next=current;
}
else
{
start0=current;
}
n0=current;
break;
case 1:
if(n1)
{
n1->next=current;
}
else
{
start1=current;
}
n1=current;
break;
case 2:
if(n2)
{
n2->next=current;
}
else
{
start2=current;
}
n2=current;
break;
}
current=current->next;
}
if(n0)
n0->next=start1;
if(n1)
n1->next=start2;
if(n2)
n2->next=NULL;
return start0;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* since we are adding at the begining,
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;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 2);
head=sort(head);
printf("\n Sorted Linked list ");
printList(head);
getchar();
}
Advantage Sorting Can Be Done in Single Pass
TC O(n)
SC O(1)
Run Here https://ideone.com/clone/Ny3OI
Feel Free to Comment if you Find Anything Wrong Above..??
No comments :
Post a Comment