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 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 the beginning of the i-th pass, the first (i-1) elements of the array are those that have been selected in the previous passes. The smallest element is now searched in the remaining (n-i+1) elements. After (n-1) passes, the sorted array is completely developed in the space occupied by the original array.
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.
This method makes repeated use of straight insertion or shuttle sort. 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.
Please find detail information on Shell Sort https://en.wikipedia.org/wiki/Shellsort
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 algorithm is O(n^2). Continue reading “Straight Insertion 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 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.
This example shows how Binary Search Algorithm works.
Binary search algorithm is better when an array is sorted because it makes comparison between the search key “k” and middle element of the array. Since the array is sorted, the comparison results either in a match between “k” and the middle element of the array or identifying the left half or right half of the array to which the desired element may belong. This process continues on the half in which the desired element may be present in case “k” is not equal to the middle element. In this way, either the element is detected or the final division leads to a half, where the array does not contain the desired element “k”.
This is very efficient method of searching algorithm because the comparison enables one to eliminate half of the elements from further consideration.
This example shows how Sequential Search algorithm works.
Simple way to search for a key value
k in an array
a is to compare the values of the elements in
k. The process starts with the first element of the array and
k and comparison continues as long as either the comparison does not result in a success or the list of elements in the array are exhausted. This method of searching is known as sequential search or linear search.
The following code example will return the index of the array when a successful search is found for the given key value and when the search is unsuccessful, the function returns
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 empty tree is a binary tree
- a binary tree consists of a node is called root, a left and right sub-tree both of which are binary trees once again.
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 added to the queue.
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 we will see the operations on stack using linked list because the stack is never full as long as the system has enough space for dynamic memory allocation. Continue reading “Stack using Linked List in C Program”