Bubble sort - linked list

#define MAX 10

struct lnode
{
int data;
struct lnode *next;
} *head, *visit;

/* add a new entry to the linked list */
void llist_add(struct lnode **q, int num);
/* preform a bubble sort on the linked list */
void llist_bubble_sort(void);
/* print the entire linked list */
void llist_print(void);

int main(void) {
/* linked list */
struct lnode *newnode = NULL;
int i = 0; /* a general counter */

/* load some random values into the linked list */
for(i = 0; i < MAX; i++)
{
llist_add(&newnode, (rand() % 100));
}

head = newnode;
printf("Before bubble sort:\n");
llist_print();
printf("After bubble sort:\n");
llist_bubble_sort();
llist_print();

return 0;
}

/* adds a node at the end of a linked list */
void llist_add(struct lnode **q, int num)
{
struct lnode *tmp;

tmp = *q;

/* if the list is empty, create first node */
if(*q == NULL) {
*q = malloc(sizeof(struct lnode));
tmp = *q;
} else {
/* go to last node */
while(tmp->next != NULL)
tmp = tmp->next;

/* add node at the end */
tmp->next = malloc(sizeof(struct lnode));
tmp = tmp->next;
}

/* assign data to the last node */
tmp->data = num;
tmp->next = NULL;
}

/* print the entire linked list */
void llist_print(void)
{
visit = head;

while(visit != NULL)
{
printf("%d ", visit->data);
visit = visit->next;
}
printf("\n");
}

/* preform a bubble sort on the linked list */
void llist_bubble_sort(void) {
struct lnode *a = NULL;
struct lnode *b = NULL;
struct lnode *c = NULL;
struct lnode *e = NULL;
struct lnode *tmp = NULL;

/*
// the `c' node precedes the `a' and `e' node
// pointing up the node to which the comparisons
// are being made.
*/
while(e != head->next)
{
c = a = head;
b = a->next;
while(a != e)
{
if(a->data > b->data)
{
if(a == head)
{
tmp = b -> next;
b->next = a;
a->next = tmp;
head = b;
c = b;
} else {
tmp = b->next;
b->next = a;
a->next = tmp;
c->next = b;
c = b;
}
} else
{
c = a;
a = a->next;
}
b = a->next;
if(b == e)
e = a;
}
}
}

Related Links :

2 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. Why declare variable as 'a,b,c,d,e' why not prev current new next.. Or something with meaning. So hard to follow.

    ReplyDelete


If you face any Problem in viewing code such as Incomplete "For Loops" or "Incorrect greater than or smaller" than equal to signs then please collect from My Web Site CLICK HERE


More Useful Topics...

 

History Of C..

In the beginning was Charles Babbage and his Analytical Engine, a machine
he built in 1822 that could be programmed to carry out different computations.
Move forward more than 100 years, where the U.S. government in
1942 used concepts from Babbage’s engine to create the ENIAC, the first
modern computer.
Meanwhile, over at the AT&T Bell Labs, in 1972 Dennis Ritchie was working
with two languages: B (for Bell) and BCPL (Basic Combined Programming
Language). Inspired by Pascal, Mr. Ritchie developed the C programming
language.

My 1st Program...


#include
#include
void main ()
{
clrscr ();
printf ("\n\n\n\n");
printf ("\t\t\t*******Pankaj *******\n");
printf ("\t\t\t********************************\n");
printf ("\t\t\t\"Life is Good...\"\n");
printf ("\t\t\t********************************");
getch ();
}

Next Step...


#include
#include

void main ()
{
clrscr ();
printf ("\n\n\n\n\n\n\n\n");
printf ("\t\t\t --------------------------- \n\n");

printf ("\t\t\t | IGCT, Info Computers, INDIA | \n\n");
printf ("\t\t\t --------------------------- ");

getch ();

}

Hits!!!