Tag Archives: C Language

Fibonacci Search Algorithm, written in C

The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search, Fibonacci search examines locations whose addresses have lower dispersion. Therefore, when the elements being searched have non-uniform access memory storage (i.e., the time needed to access a storage location varies depending on the location previously accessed), the Fibonacci search has an advantage over binary search in slightly reducing the average time needed to access a storage location. The typical example of non-uniform access storage is that of a magnetic tape, where the time to access a particular element is proportional to its distance from the element currently under the tape’s head. Note, however, that large arrays not fitting in cache or even in RAM can also be considered as non-uniform access examples. Fibonacci search has a complexity of O(log(x)).

Fibonacci Search Algorithm, written in C:

#include <stdio.h>

int ricerca_fib(int a[], int n, long x)
{ 
	int inf=0, pos, k;
	static int kk= -1, nn=-1, fib[]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141};

if(nn!=n)
{ 
	k=0;
	while(fib[k]<n) k++;
	kk=k;
	nn=n;
}
else
	k=kk;

while(k>0)
{
	pos=inf+fib[--k];
	if((pos>=n)||(x<a[pos]));
	else if (x>a[pos])
	{
		inf=pos+1;
		k--;
    }

	else {
		return pos;
	}
}
	return -1;
}

Recursive Quicksort Algorithm written in C language [with example step-by-step]

Quicksort is a sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Although quicksort is usually not implemented as an in-place sort, it is possible to create such an implementation.
Quicksort (also known as “partition-exchange sort”) is a comparison sort and, in efficient implementations, is not a stable sort.
Continue reading Recursive Quicksort Algorithm written in C language [with example step-by-step]

Massimo e Minimo di un array in C

Con le seguenti funzioni, scritte in linguaggio C, è possibile trovare il valore massimo e il valore minimo all’interno di un array di n elementi interi. Con piccolissime modifiche è possibile scrivere la versione che valuta il massimo e il minimo di un array su valori in virgola mobile (float).

Continue reading Massimo e Minimo di un array in C

Binary Search Algorithm, written in C [with video example step-to-step]

In computer science, a binary search is an algorithm for locating the position of an item in a sorted array.[1][2] Binary search works by comparing an input value to the middle element of the array. The comparison determines whether the element is equal to the input, less than the input or greater. When the element being compared to equals the input the search stops and typically returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element. Depending on which it is the algorithm then starts over but only searching the top or bottom subset of the array’s elements. If the input is not located within the array the algorithm will usually output a unique value indicating this. This method halves the number of items to check each time, so it finds it or determines it’s not present in logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.
It is useful to find where an item is in a sorted array. For example, if you had an array for contact information, with people’s names, addresses, and telephone numbers sorted by name, you could use binary search to find out a few useful facts: whether the person’s information is in the array, what the person’s address is, and what the person’s telephone number is.
Continue reading Binary Search Algorithm, written in C [with video example step-to-step]

Linear Search in unordered array [with source code written in C and video example]

In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.[1]
Linear search is the simplest search algorithm; it is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the list; and so is its expected cost, if all list elements are equally likely to be searched for. Therefore, if the list has more than a few elements, other methods (such as binary search or hashing) may be much more efficient. Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list. When many values have to be searched in the same list, it often pays to pre-process the latter in order to use a faster method. For example, one may sort the list and use binary search, or build any efficient search data structure from it.

This is an implementation of Linear Search in C Language, with Main structure.

Source Code


// © Codeido - www.codeido.com - Developed by Paolo Musolino

//Ricerca sequenziale in un array disordinato
#include <stdio.h>

int ricerca_Sequenziale(int a[], int n, int chiave)
{
	int i=0;
	
	while ((a[i]) && (i<n))
		   {
			   if (a[i]==chiave) 
			   {
				   return i;
				   
			   }
			   
			   if (i==n-1) 
			   {
				   return -1;
			   }
			   
			   if(a[i]!=chiave)
				   i++;
			   
		   }
	
}



int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int ris_ricerca;
	ris_ricerca = ricerca_Sequenziale(a, 14, 20);
	printf("\n");
	
	if (ris_ricerca==-1) {
		printf("L'elemento cercato non è presente all'interno dell'array\n");
	}
	
	if (ris_ricerca>=0) {
		printf("L'elemento cercato si trova nella posizione %d ", ris_ricerca);
	}
	
	return 0;
}

Non-uniform probabilities
The performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end. Therefore, if some values are much more likely to be searched than others, it is desirable to place them at the beginning of the list.
In particular, when the list items are arranged in order of decreasing probability, and these probabilities are geometrically distributed, the cost of linear search is only O(1). If the table size n is large enough, linear search will be faster than binary search, whose cost is O(log n).[1]

Linear and Binary Searching

Leadsort written in C

The sorting algorithm “leadsort” is a variant of “bubblesort” that allows you to sort the array in reverse. Computational complexity= O(n^2).

Source Code written in C language:


// © Codeido - www.codeido.com - Developed by Paolo Musolino

#include <stdio.h>

void swap(int *a, int *b)
{	
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
	
	
}
//---------------//---------------//---------------
int confronto(int x, int y)
{
	if(x<y) return -1;
	else if(x>y) return 1;
	else {
		return 0;
	}
	
}

void leadSort(int a[], int n)
{
	int i, j;
	
	for (i=n; i>1; i--) {
		for (j=1; j<i; j++) {
			if (confronto(a[j],a[j-1])<0) {
				swap(&a[j], &a[j-1]);
			}
		}
	}
	
}

int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int i;
	leadSort(a, 14);
	printf("\n");
	for (i=0; i<14; i++) {
		printf("%d ", a[i]);
	}
	
	
	return 0;
}

Bubblesort written in C with example step-by-step

Source code of sorting algorithm “bubblesort” written in C. Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

Step-by-step example
Let us take the array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared.

– First Pass:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
– Second Pass:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.

Source Code in C:


// © Codeido - www.codeido.com - Developed by Paolo Musolino

#include <stdio.h>

void swap(int *a, int *b)
{	
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
	
	
}
//---------------//---------------//---------------
int confronto(int x, int y)
{
	if(x<y) return -1;
	else if(x>y) return 1;
	else {
		return 0;
	}
	
}

void bubbleSort(int a[], int n)
{
	int i, j;
	for (i=0; i<n-1; i++) 
	{
		for (j=n-1; j>i; j--) 
		{
			if (confronto(a[j], a[j-1])<0) 
			
				swap(&a[j], &a[j-1]);
			
		}
	}
}


//Main Function
int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int i;
	bubbleSort(a, 14);
	printf("\n");
	for (i=0; i<14; i++) {
		printf("%d ", a[i]);
	}
	
	
	return 0;
}

[retweet]