Introduction Quick sort or quicksort (sometimes called partition-exchange sort) is an efficient and very fast sorting algorithm for internal sorting, serving as a systematic method for placing the elements of an array in order. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quick sort can operate in-place on an array, requiring small additional amounts of memory to…

Continue# Category: Data Structure

Data Structure

## Bubble Sort using C

Introduction Bubble sort is one of the most popular sorting methods. It can be treated as a selection sort because it is based on successively selecting the smallest element, second smallest element and so on. In order to find the successive smallest elements this process relies heavily on the exchange of the adjacent elements and swaps them if they are in the wrong order.

Continue## Straight Selection Sort using C

Selection sorting refers to a class of algorithms for sorting a list of items using comparisons. These algorithms select successively smaller or larger items from the list and add them to the output sequence. This is an improvement of the Simple Selection Sort and it is called Straight Selection Sort. Therefore, instead of replacing the selected element by a unique value in the i-th pass (as happens in Simple Selection Sort), the selected element is exchanged with the i-th element. Let’s assume an array “a” with “n” elements. Thus, at…

Continue## Simple Selection Sort using C

The simplest possible technique based on the principle of repeated selection makes use of “n” passes over an array elements. In the i-th pass, the i-th smallest element is selected from the given array and it is placed in the i-th position of a separate output array. The already selected element is not selected next time and in order to ensure it, a unique value is put in place of the selected element in the original array. Simple selection sort has an O(n²) time complexity which makes inefficient for large…

Continue## Shell Sort using C

I will show here an example on shell sort (invented by Donald Shell) using C programming language. This method makes repeated use of straight insertion or shuttle sort. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. An array with n elements, in each pass, an increment is chosen. The increment must be less than n and the increment progressively should be smaller and the last increment must be equal to 1.

Continue## Straight Insertion Sort using C

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. More details can be found here at https://en.wikipedia.org/wiki/Insertion_sort Let’s say we have an array a, so at each i-th pass, a[i] is successively compared with a[i-1], a[i-2], etc. until an element smaller than a[i] is found or the beginning of the array is reached. Elements that are found to be greater than a[i], are moved right by one position each to make room for a[i]. The time complexity of this…

Continue## Shuttle Sort using C

In Shuttle Sort technique for n elements in an array a, it requires n-1 passes. When i-th pass(1<=i<=n) begins, the first i elements, i.e., elements a[0] to a[i-1] have been sorted and these occupy the first i positions of the array. To insert (i+1)th element, a[i] is compared with a[i-1] and if the value of a[i] is smaller than a[i-1] then they are exchanged. In the same way the process continues until either no exchange is required or the beginning of the array is reached.

Continue## Binary Tree using pointer in C

Introduction Here we will see example on binary tree using pointer in C programming language. The same concept can be used in other language to write program for binary tree. What is Binary Tree? Binary tree is an important class of tree in data structure. A node in binary tree can have at most two children, which are called sub-trees. Children of a node in binary tree are ordered. One child is called left child and another child is called right child. A binary tree can be defined as an…

Continue## Queue using Linked List in C Program

Introduction We will create an example on queue using linked list in C program. A queue like a stack is another special type of ordered list. In queue insertion operations are permitted at one end of the list and deletion operations are performed at the other end of the list. The end where insertion operations are performed is called rear and the end where deletion operations are performed is called front. A queue is often called Fisrt In Fisrt Out(FIFO) list because the first element removed is the first element…

Continue## Stack using Linked List in C Program

Introduction We will see how to create stack using linked list in C program. Stack is a special kind of linear list. Linear list is an ordered collection of a number of items of the same type. Two operations are performed frequently from linear list – insertion and deletion. A stack is a linear list where all insertions and deletions happen at one end of the list. A stack is often called Last In First Out(LIFO) because a first element removed is the last element pushed to the stack. Here…

Continue