Sorting algorithms and programs in data structures using C

Sorting algorithms and programs in data structures using C

Sorting Techniques

• Bubble sort

• Insertion sort

• Selection sort

• Heap sort

• Shell sort

• Merge sort

• Quick sort

• Radix sort

• Time complexity of sorting algorithms

• Stable, In-place and Comparison properties of sorting algorithms

• What is stable sorting algorithm?
  

• What is comparison sorting algorithm?
  

• What is in-place sorting algorithm?
  

different sorting algorithms in data structures

complexity of sorting algorithms

how to sort data efficiently

sorting algorithms comparison

Searching algorithms and programs in data structures using C

Searching algorithms and programs in data structures using C

Searching algorithms

• Linear search
• Algorithm / Pseudocode
• Program in C

• Binary search
• Algorithm / Pseudocode
• Program in C

• Hashing

***********

searching algorithms in data structures

searching algorithms implementation using C

linear search, binary search and hashing techniques 

searching algorithms in C 

Binary search algorithm in data structures using C

Binary search algorithm in data structures

Binary search

Binary search is a search algorithm that works with the concept of divide and conquer. It is a fast search algorithm with the time complexity of O(log n). It requires that the keys in the array should be stored in a sorted order.

Let us assume an array a[] of n elements and the key k to be searched among them. The algorithm finds the middle element of array a[] and compares with the key to be found. If they match, then return the index as result. If not, algorithm divides the array into two halves on the middle element and based on the search key value it searches in one of the sub-arrays. If the key value is smaller than the middle element, then search continues with left sub-array otherwise with the right sub-array. The array is sub-divided recursively until the element is found or the entire array is scanned.

Algorithm:

Step 1: Read the array of keys and the key to be searched as input.

Step 2: Find and compare the middle element of the array with the key to be searched.

Step 3: If the middle matches with the key, then the middle index is returned as result and closes the program.

Step 4: If the middle does not match with the key to be searched, then the algorithm divides the array into two halves.

Step 4a: If the key is greater than middle element, the algorithm omits the lower half of the array and considers only the higher half.

Step 4b: If the key is smaller than the middle element, it considers the lower half. And go to step 2.

Step 5: Repeat steps 2 to 4b until the element is found or all the elements in the array are scanned.

Pseudocode:

int binarySearch(int a[], int low_index, int high_index, int key_to_find)

{

int mid_index;

   While (low_index <= high_index)

   {

     mid_index = (low_index + high_index)/2;

     if(a[mid_index] < key_to_find)

         low_index = mid_index + 1;

     else if(a[mid_index] > key_to_find)

         high_index = mid_index - 1;

     else

         return mid_index;

     }

   }

   return -1;

 }

Algorithm Description:

Algorithm / Pseudocode

Description

1: bSearch (a[], low_index, high_index, key_to_find) 2:  { 3:  int mid_index; 4:  while (low_index <= high_index) 5:  { 6:     mid_index = (low_index + high_index)/2; 7:     if(a[mid_index] < key_to_find) 8:         low_index = mid_index + 1; 9:     else if(a[mid_index] > key_to_find) 10:         high_index = mid_index - 1; 11:     else 12:         return mid_index; 13:   } 14:   return -1;                15: }

4: if left most index of the array is smaller/equal to right most index then loop 6: find the middle index 7: if the element stored in middle index < key 8: new low index will be middle + 1 (right half) 9: if middle element > key 10: new high index will be middle -1 (left half) 12: if 7 and 9 are invalid, our result is middle. 14: if the key not found in array return -1

************

Go to binary search algorithm implementation - program in C

Go to linear search algorithm in data structures

Binary search algorithm in data structures

How does binary search algorithm work

Implementation of binary search algorithm

Binary search algorithm implementation using C program

Binary search algorithm implementation using C program

Program:

/* recursive binary search*/

#include<stdio.h>

int bsearch(int [ ],int, int, int); //function declaration

int main( )

{

int a[20], i, low_index, high_index;

int position, total_keys, key_to_find

printf("\nEnter the total number of values:");

scanf("%d", &total_keys);

for(i = 0; i < total_keys; i++)

{

    printf("\nEnter the key elements %d  : ", i);

    scanf("%d", &a[i]);

}

printf("\nEnter the key to search : ");

scanf("%d", &key_to_find);

low_index = 0;

high_index = n-1;

//the following line calls the function bsearch with parameters

position = bsearch(a, key_to_find, low_index, high_index);

if(position!=-1)

    printf("Search successful, element found at position %d", position);

else

    printf("Search unsuccessful, element not found");

getch();

}

int bsearch(int a[ ], int k, int lb, int ub)

{

int mid;

while(ub >= lb) //repeat this loop while upper bound >= lower bound

             {

             mid=(lb+ub)/2; //finds new middle index in each iteration

             if(k < a[mid]) //if the key_to_find is smaller than middle element of array,

                  ub = mid-1; //set the new upper bound as middle-1

             else if(k > a[mid]) //if key_to_find is larger than middle

                  lb = mid+1; //set the new lower bound as middle+1

             else if(k == a[mid]) //if key_to_find is equal to middle element

                  return(mid); //return the middle element as result

             return (bsearch(a,k,lb,ub)); //if none of the above holds, call bsearch (recursive)

}

return -1; //if the key_to_find is not in the list, return -1 to tell ‘NOT FOUND’

}

**************

Go to binary search algorithm page

Download program - binary search in C 

Go to linear search/sequential search algorithm/program

binary search program in C

binary search algorithm using recursive functions in C

binary search divide and conquer algorithm

binary search simple program in C