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]

# Tag Archives: Example

# 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]

# 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]