Searching & Sorting in DS
Bubble sort algorithm implementation in C
Bubble Sort is a simple algorithm which is
used to sort a given set of
n elements
provided in form of an array with n
number of elements. Bubble Sort compares all the element one by one
and sort them based on their values.
If the given array has to be sorted in ascending
order, then bubble sort will start by comparing the first element of
the array with the second element, if the first element is greater
than the second element, it will swap both the elements, and
then move on to compare the second and
the third element, and so on.
If we have total
n
elements, then we need to repeat this process for n-1
times.
It is known as bubble sort,
because with every complete iteration the largest element in the
given array, bubbles up towards the last place or the highest index,
just like a water bubble rises up to the water surface.
Sorting takes place by stepping through all the
elements one-by-one and comparing it with the adjacent element and
swapping them if required.
#include <stdio.h> int main() { int a[10], n, i, j, temp; printf("Enter size of array elements\n"); scanf("%d", &n); printf("Enter %d integers\n", n); for (i = 0; i < n; i++) scanf("%d", &a[i]); for (i = 0 ; i< n - 1; i++) { for (j = i ; j < n -1; j++) { if (a[i] > a[j+1]) /* For decreasing order use < */ { temp = a[i]; a[i] = a[j+1]; a[j+1] = temp; } } } printf("Sorted list in ascending order:\n"); for (i = 0; i < n; i++) printf("%d\n", array[i]); return 0; }Output
Enter size of array elements 3
Enter
3 integers 5 9 4
Sorted
list in ascending order: 4 5 9
linear search
Linear
search is used on a collections of items. It relies on the technique
of traversing a list from start to end by exploring properties of all
the elements that are found on the way.
For example, consider an array of integers of size You should find
and print the position of all the elements with value . Here, the
linear search is based on the idea of matching each element from the
beginning of the list to the end of the list with the integer , and
then printing the position of the element if the condition is `True'.
output#include<stdio.h>#include <stdio.h> int main() { int a[10], n, i, j, key; printf("Enter size of array elements\n"); scanf("%d", &n); printf("Enter %d element in ascending order\n", n); for (i = 0; i < n; i++) {scanf("%d",&a[i]);}printf (“ Enter the element to be search \n”);scanf(“ %d”, &key);/* for : Check elements one by one - Linear */for (i = 0; i <n; i++){/* If for Check element found or not */if (a[i] ==key) {printf("Linear Search : %d is Found at array : %d.\n",key, i + 1);break;}}if (i ==n)printf("\nSearch Element : %d : Not Found \n",key);getch();}
Enter size of array elements 3
Enter 3 element in ascending order 5 9 15
Enter
the element to be search 15 Linear
Search : 15 is Found at array : 3
Binary Search in C
Binary
search
is the most popular Search algorithm.It is efficient and also one of
the most commonly used techniques that is used to solve problems.
If
all the names in the world are written down together in order and you
want to search for the position of a specific name, binary search
will accomplish this in a maximum of
iterations.
Binary search
works only on a sorted set of elements. To use binary search on a
collection, the collection must first be sorted.
When binary
search is used to perform operations on a sorted set, the number of
iterations can always be reduced on the basis of the value that is
being searched.
Let us
consider the following array:
By using linear search, the position of element 8 will be determined in the
iteration.
Let's see how the number of iterations can be reduced by using binary search. Before we start the search, we need to know the start and end of the range. Lets call them
Low
and High. Or first and last.Now, compare the search valueLow or first= 0high or last= n-1
with the element located at the median of the lower and upper bounds. If the value
is greater, increase the lower bound, else decrease the upper bound.
Referring to the image above, the lower bound is
and the upper bound is
. The median of the lower and upper bounds is
(lower_bound
+ upper_bound) / 2 = 4. Here a[4] = 4.
The value 4>2, which is the value that you are searching for.
Therefore, we do not need to conduct a search on any element beyond 4
as the elements beyond it will obviously be greater than 2.
Therefore, we can always drop the upper bound of the array to the position of element 4. Now, we follow the same procedure on the same array with the following values:
Repeat this procedure recursively untilLowor first: 0Highor last: 3
Low >
High. If at any iteration, we get , we return value of . This
is the position of in the array. If is not present in the array, we
return
Implementation:
Program for Binary Search in C
#include<stdio.h>
int
main()
{
int a[10],i,n,key,found=0,first,last,mid;
printf("Enter size of array:");
scanf("%d",&n);
printf("\nEnter array element(ascending order)\n");
for(i=0;i<n;++i)
scanf("%d",&a[i]);
printf("\nEnter the element to search:");
scanf("%d",&key);
first=0;
last=n-1;
while(first<=last)
{
mid=(first+last)/2;
if(key==a[mid])
{
found=1;
break;
}
else if(key>a[mid])
first=mid+1;
else
last=mid-1;
}
if(found==1)
printf("\nElement found at position %d",mid+1);
else
printf("\nElement not found");
return 0;
}
Enter size of array:6
Enter array element(ascending order)
20 27 40 50 58 99
Enter the element to search:27
Element found at position 2
Explain following array function
- create
- insert element at particular position in array
- delete array element
- display
Ans :
1. Create array function
void creat( )
{ int size, arr[5];
printf("Enter size of array elements\n");
scanf("%d", &size); printf("Enter %d integers\n", n); for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
}
2. C Program to Insert an Element in a Specified Position in a given Array
void insert( int arr[5],int size)
{
int i,num,pos;
// Create( );
// Create( );
/* Array is created Input new element and position to insert */ printf("Enter element to insert : "); scanf("%d", &num); printf("Enter the element position : "); scanf("%d", &pos); /* If position of element is not valid */ if(pos > size+1 || pos <= 0) {printf("Invalid position! Please enter position between 1 to %d", size); } else { /* Make room for new array element by shifting to right */ for(i=size; i>=pos; i--) { arr[i] = arr[i-1]; } /* Insert new element at given position and increment size */ arr[pos-1] = num; size++; /* Print array after insert operation */
printf("Array elements after insertion : "); for(i=0; i<size; i++) { printf("%d\t", arr[i]); } }
3. Void delet ( int arr[5],int size)
{ int i,num,pos;
printf("Enter the element position to delete : "); scanf("%d", &pos); /* Invalid delete position */ if(pos < 0 || pos > size) { printf("Invalid position! Please enter position between 1 to %d", size); } else { /* Copy next element value to current element */
for(i=pos-1; i<size-1; i++) { arr[i] = arr[i + 1]; } /* Decrement array size by 1 */ size--; } /* Print array after deletion */ printf("\nElements of array after delete are : "); for(i=0; i<size; i++) { printf("%d\t", arr[i]); }
}
Void display(int arr([5],int size)
{ int i;
printf("Array elements are \n"); for (i = 0; i < size; i++)
Printf("%d \t", are[i]);
