bubble sort with linear search using linked list

to add a linear search function in this program to the elements sorted

Page 1 of 1

2 Replies - 9332 Views - Last Post: 29 July 2009 - 12:35 PM Rate Topic: -----

#1 nehzz.agarwal  Icon User is offline

  • New D.I.C Head

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

bubble sort with linear search using linked list

Post icon  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;
} *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;
  }
 }
}



Is This A Good Question/Topic? 0
  • +

Replies To: bubble sort with linear search using linked list

#2 sbromley  Icon User is offline

  • D.I.C Head

Reputation: 21
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 wildgoose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 67
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1