# bubble sort with linear search using linked list

Page 1 of 1

## 2 Replies - 10882 Views - Last Post: 29 July 2009 - 12:35 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=117428&amp;s=978fce74c6f8de9d41cd0cda4da9baef&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 nehzz.agarwal

Reputation: 0
• Posts: 1
• Joined: 29-July 09

# bubble sort with linear search using linked list

Posted 29 July 2009 - 08:53 AM

i need to add a linear search function in this program to the elements sorted sorted by bubble sort.. im getting stuck and unavialble to do so.. pls help
```#include <stdio.h>
#include <stdlib.h>

#define MAX 10

struct lnode {
int data;
struct lnode *next;

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) {

struct lnode *newnode = NULL;
int i = 0; /* a general counter */

for(i = 0; i < MAX; i++) {
}

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) {

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
*/
b = a->next;
while(a != e) {
if(a->data > b->data) {
tmp = b -> next;
b->next = a;
a->next = tmp;
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;
}
}
}

```

Is This A Good Question/Topic? 0

## Replies To: bubble sort with linear search using linked list

### #2 sbromley

Reputation: 21
• Posts: 127
• Joined: 20-May 09

## Re: bubble sort with linear search using linked list

Posted 29 July 2009 - 09:34 AM

If you want to implement a linear search algorithm all's you have to do is iterate over the list and compare each node with your key.

So you could start at the head element compare it to your key, and if it is not equal then go to the next element. And once you reach your tail, or head (depending on if the linked list is circular or not) and that node is not equal to the key then you know the key is not in the list.

### #3 wildgoose

• D.I.C Regular

Reputation: 67
• Posts: 468
• Joined: 29-June 09

## Re: bubble sort with linear search using linked list

Posted 29 July 2009 - 12:35 PM

If the list is always searched only after a sort then you only need to search up to where that key either matches the node, or just went past it in the search thus its not in the list. No need to compare to the entire list!

Bubble sorts bubble nodes into position by swapping their positions if they're found to be out of position. If you run an entire list with no swaps then you are done. I don't see a change flag to tell the outer loop that the inner loop has been fully checked and pass/fail.

A bubble sort is one of the slowest search algoithms. When you get this working, you should try other sorts using a single linked list. Then try a double-linked list!

This post has been edited by wildgoose: 29 July 2009 - 12:36 PM