Searching and Sorting

Searching Techniques:

Searching for data is one of the fundamental fields of computing. Often, the difference between a fast program and a slow one is the use of a good algorithm for the data set. This article will focus on searching for data stored in a linear data structure such as an array or linked list.

Linear Search, Binary Search and other Searching Techniques:

 

Linear Search

The most obvious algorithm is to start at the beginning and walk to the end, testing for a match at each item:

bool jw_search ( int *list, int size, int key, int*& rec )
{
  // Basic sequential search
  bool found = false;
  int i;

  for ( i = 0; i < size; i++ ) {
    if ( key == list[i] )
      break;
  }
  if ( i < size ) {
    found = true;
    rec = &list[i];
  }

  return found;
} 

Binary Search

All of the sequential search algorithms have the same problem; they walk over the entire list. Some of our improvements work to minimize the cost of traversing the whole data set, but those improvements only cover up what is really a problem with the algorithm. By thinking of the data in a different way, we can make speed improvements that are much better than anything sequential search can guarantee.

bool jw_search ( int *list, int size, int key, int*& rec )
{
  // Binary search
  bool found = false;
  int low = 0, high = size - 1;

  while ( high >= low ) {
    int mid = ( low + high ) / 2;
    if ( key < list[mid] )
      high = mid - 1;
    else if ( key > list[mid] )
      low = mid + 1;
    else {
      found = true;
      rec = &list[mid];
      break;
    }
  }

  return found;
}

Conclusion:

Searching is an important function in computer science. Many advanced algorithms and data structures have been devised for the sole purpose of making searches more efficient. And as the data sets become larger and larger, good search algorithms will become more important. At one point in the history of computing, sequential search was sufficient. But that quickly changed as the value of computers became apparent.

Linear search has many interesting properties in its own right, but is also a basis for all other search algorithms. Learning how it works is critical.

Binary search is the next logical step in searching. By dividing the working data set in half with each comparison, logarithmic performance, O(log n), is achieved. That performance can be improved significantly when the data set is very large by using interpolation search, and improved yet again by using binary search when the data set gets smaller.

 Sorting:  It is the process of aranging a set of similar 

info into inc. or dec. order  

Techniques:

1. Insertion sort

2. Bubble sort

3. Merge sort 

source codes:

2d  insertion sort [linked list]:
#include <stdio.h>
#include <stdlib.h>

struct node {
 int number;
 struct node *next;
};

struct node *head = NULL;

/* insert a node directly at the right place in the linked list */
void insert_node(int value);

int main(void) {
 struct node *current = NULL;
 struct node *next = NULL;
 int test[] = {8, 3, 2, 6, 1, 5, 4, 7, 9, 0};
 int i = 0;

 /* insert some numbers into the linked list */
 for(i = 0; i < 10; i++)
  insert_node(test[i]);

 /* print the list */
 printf(" before  after\n"), i = 0;
 while(head->next != NULL) {
  printf("%4d\t%4d\n", test[i++], head->number);
  head = head->next;
 }

 /* free the list */
 for(current = head; current != NULL; current = next)
  next = current->next, free(current);

 return 0;
}

void insert_node(int value) {
 struct node *temp = NULL;
 struct node *one = NULL;
 struct node *two = NULL;

 if(head == NULL) {
  head = (struct node *)malloc(sizeof(struct node *));
  head->next = NULL;
 }

 one = head;
 two = head->next;
 
 temp = (struct node *)malloc(sizeof(struct node *));
 temp->number = value;
 
 while(two != NULL && temp->number < two->number) {
  one = one->next;
  two = two->next;
 }

 one->next = temp;
 temp->next = two;
}

Insertion sort [linked list]:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct lnode {
 char *str;
 struct lnode *next;
};

struct lnode *insert(char *data, struct lnode *list);
void free_list(struct lnode *list);
void print_list(struct lnode *list);

int main(void) {
 char line[1024];
 struct lnode *list;

 list = NULL;
 while((fgets(line, 1024, stdin)) != NULL)
  list = insert(line, list);

 print_list(list);
 free_list(list);
 return 0;
}

struct lnode *insert(char *data, struct lnode *list) {
 struct lnode *p;
 struct lnode *q;

 /* create a new node */
 p = (struct lnode *)malloc(sizeof(struct lnode));
 /* save data into new node */
 p->str = strdup(data);

 /* first, we handle the case where `data' should be the first element */
 if(list == NULL || strcmp(list->str, data) > 0) {
  /* apperently this !IS! the first element */
  /* now data should [be|becomes] the first element */
  p->next = list;
  return p;
 } else { 
  /* search the linked list for the right location */
  q = list;
  while(q->next != NULL && strcmp(q->next->str, data) < 0) {
   q = q->next;
  }
  p->next = q->next;
  q->next = p;
  return list;
 }
}
   
void free_list(struct lnode *list) {
 struct lnode *p;

 while(list != NULL) {
  p = list->next;
  free(list);
  list = p;
 }
}
 
void print_list(struct lnode *list) {
 struct lnode *p;
 
 for(p = list; p != NULL; p = p->next)
  printf("%s", p->str);
}

 Bubble sort [linked list]:
#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;
  }
 }
}

Merge sort [linked list]:

#include <stdio.h>
#include <stdlib.h>

struct node {
 int number;
 struct node *next;
};

/* add a node to the linked list */
struct node *addnode(int number, struct node *next);
/* preform merge sort on the linked list */
struct node *mergesort(struct node *head);
/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two);

int main(void) {
 struct node *head;
 struct node *current;
 struct node *next;
 int test[] = {8, 3, 2, 6, 1, 5, 4, 7, 9, 0};
 int i;

 head = NULL;
 /* insert some numbers into the linked list */
 for(i = 0; i < 10; i++)
  head = addnode(test[i], head);

 /* sort the list */
 head = mergesort(head);

 /* print the list */
 printf(" before  after\n"), i = 0;
 for(current = head; current != NULL; current = current->next)
  printf("%4d\t%4d\n", test[i++], current->number);

 /* free the list */
 for(current = head; current != NULL; current = next)
  next = current->next, free(current);

 /* done... */
 return 0;
}

/* add a node to the linked list */
struct node *addnode(int number, struct node *next) {
 struct node *tnode;

 tnode = (struct node*)malloc(sizeof(*tnode));

 if(tnode != NULL) {
  tnode->number = number;
  tnode->next = next;
 }

 return tnode;
}

/* preform merge sort on the linked list */
struct node *mergesort(struct node *head) {
 struct node *head_one;
 struct node *head_two;

 if((head == NULL) || (head->next == NULL))
  return head;

 head_one = head;
 head_two = head->next;
 while((head_two != NULL) && (head_two->next != NULL)) {
  head = head->next;
  head_two = head->next->next;
 }
 head_two = head->next;
 head->next = NULL;

 return merge(mergesort(head_one), mergesort(head_two));
}

/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two) {
 struct node *head_three;

 if(head_one == NULL)
  return head_two;

 if(head_two == NULL)
  return head_one;

 if(head_one->number < head_two->number) {
  head_three = head_one;
  head_three->next = merge(head_one->next, head_two);
 } else {
  head_three = head_two;
  head_three->next = merge(head_one, head_two->next);
 }

 return head_three;
}