Logo

Navigation
 

C Algorithms

Knowledge of algorithms not only provides strong programming fundamentals but is also often used to solve various mathematical problems. In this training, each algorithm is explained in detail, beginning with a few notions regarding algorithms, moving on to an easy step by step example and provides proper explanations where required. These algorithms are fully working code. Example program is provided for each algorithm. An output screenshot is also provided so that you can see what to expect after running the code.

The code in the tutorials follows the footsteps that are explained in the step by step example. Also, if you get stuck at any time, or you are missing something out, do not forget about the DEBUGGER from the VS2010 for example, you can run step by step the code, and see exactly what happens with the variables, the array or anything that code has.

Target Audience
C Algorithms tutorials provides concrete self-learning platform for beginners and will strengthen the fundamentals for intermediate level programmers and IT professionals. You need to have minimum knowledge in a programming language like C or C++.

C Algorithms – The Problem of Sorting the Elements

In this tutorial, I will talk a little about the classification, stability and complexity of each algorithm, more regarding this you can read a little bit lower of this article. Then, the advantages or disadvantages of each algorithm are shown, which should give you the big picture of each algorithm. In the end there is a conclusion to sum things up or maybe to emphasis certain things. Sorting the elements is an operation that is encountered very often in the solving of problems. For this reason, it is important for a programmer to learn how sorting algorithms work. A sorting…
September 8, 2011 - - Comments:

C Algorithms – Bubble Sort

Bubble sort is a simple sorting algorithm, which compares repeatedly each pair of adjacent items and swaps them if they are in the incorrect order. At the first run, the highest element of the list ends on the last place of the sorted list, and then, at the following run, the next highest element ends on one position lower than the previous element and so on. The initial list is finally sorted, when at a run, no swaps occur. Even though it’s one of the simplest sorting algorithms, it’s almost never used in real life because of the bad performance…
September 9, 2011 - - Comments:

C Algorithms – Insertion Sort

Insertion sort is a simple comparison sorting algorithm, that considers at a step k, the elements of the array A[0,k-1] are already sorted out, and the element on the k position will be inserted that way that after the insertion, the elements A[0,k] are sorted out. Inserting the k element in the A[0,k-1] sequence requires a few steps: the element must be retained in a temporal variable; moving all the elements from the A[0,k-1] array that are greater than A[k] with a position to the right (this presumes a run from right to left of the array); placing the A[k]…
September 9, 2011 - - Comments:

C Algorithms – Shell Sort

Shell sort is a generalization of the Insertion Sort, it sorts subsequences that become increasingly higher, until it is reached the value n – the total number of elements. Each subsequence i is determined by a number h_i called increment. Also, the increments must satisfy the following condition: h_t > h_t-1 > h_t-2 > … > h_2 > h_1 Step by step example : Having the following list, let’s try to use shell sort to arrange the numbers from lowest to greatest: Unsorted list: 16, 4, 3, 13, 5, 6, 8, 9, 10, 11, 12, 17, 15, 18, 19, 7,…
September 10, 2011 - - Comments:

C Algorithms – Radix Sort

Radix sort is a sorting algorithm that sorts the data, integers for example, by splitting the numbers into individual digits and comparing the individual digits sharing the same significant position. Also, a positional notation is required, because instead of integers there could be strings of characters or floating point numbers. The radix sort can be classified into 2 types: LSD (least significant digit) or MSD (most significant digit). The LSD sorting type begins from the least significant digit to the most significant digit and the MSD works the other way around. Note: having the number 150, the number 0 is…
September 10, 2011 - - Comments:

C Algorithms – Selection Sort

Selection sort, also called naive (selection) sort, is an in-place comparison sort. It may look pretty similar to insertion sort, but it performs worse. It is a quite simple sorting algorithm, and may perform better than more complicated algorithms in particular cases, for example in the ones where the auxiliary memory is limited. How it works: First it finds the smallest number in the array and exchanges it with the element from the first position, then it finds the second smallest number and exchanges it with the element from the second position, and so on until the entire list is…
September 11, 2011 - - Comments:

C Algorithms – Heap Sort

Heapsort is a comparison based algorithm. It bases on building a heap tree from the data set, and then it removes the greatest element from the tree and adds it to the end of the sorted list. There are two ways to do this, either to add the highest value to the root of the tree, or as one of the left/right child with the greatest depth. How it works: The heap tree is built according to the data set. Then the greatest value is move to the root of the tree, and then it is removed. This represents the…
September 11, 2011 - - Comments:

C Algorithms – Counting Sort

Counting sort is a sorting algorithm that is not based on comparison like most other methods. This method of sorting is used when all elements to be sorted fall in a known, finite and reasonably small range. How it works: The algorithm refers to finding for each element a[i] the number of elements from the array that are lower than it. Step by step example : Having the following list, let;s try to use counting sort to arrange the numbers from lowest to greatest: Unsorted list, the array A contains the elements to be sorted: We count the number of…
September 12, 2011 - - Comments:

C Algorithms – Merge Sort

Merge sort is another comparison based sorting algorithm. Also, it is a divide and conquer algorithm, which means the problem is split into multiple simplest problems and the final solution is represented by putting together all the solutions. How it works: The algorithm divides the unsorted list into two sub-lists of about half the size. Then sort each sub-list recursively by re-applying the merge sort and then merge the two sub-lists into one sorted list. Step by step example : Having the following list, let’s try to use merge sort to arrange the numbers from lowest to greatest: Unsorted list:…
September 12, 2011 - - Comments:

C Algorithms – Quick Sort

Quick sort is a comparison sort developed by Tony Hoare. Also, like merge sort, it is a divide and conquer algorithm, and just like merge sort, it uses recursion to sort the lists. It uses a pivot chosen by the programmer, and passes through the sorting list and on a certain condition, it sorts the data set. How it works: A pivot is chosen from the elements of the data set. The list must be reordered in such a way that the elements with the value less than the pivot come before it and the ones that are greater come…
September 13, 2011 - - Comments:

C Algorithms – Bucket Sort

Bucket sort is a sorting algorithm that works by inserting the elements of the sorting array intro buckets, then, each bucket is sorted individually. The idea behind bucket sort is that if we know the range of our elements to be sorted, we can set up buckets for each possible element, and just toss elements into their corresponding buckets. We then empty the buckets in order, and the result is a sorted list. It is similar to radix sort. How it works: Initially we have to set up an array of empty buckets, then put each object into its bucket….
September 13, 2011 - - Comments:

C Algorithms – Comb Sort

Comb sort is a simple sorting algorithm which improves on bubble sort. The main idea for this type of algorithm is to eliminate the small values near the end of the list, as these slow down the sorting process. How it works: In comb sort, the main usage is of gaps. For example, in bubble sort the gap between two elements was 1 whilst here the gap starts out as a large value and shrinks until it reaches the value 1, when it practically becomes bubble sort. The shrink factor determines how much the gap is lessened. The value is…
September 14, 2011 - - Comments:

C Algorithms – Gnome Sort

Gnome sort is an extremely simple sorting algorithm, very similar to insertion sort. Also, it is another comparison and exchange sort. You could say that it looks like bubble sort, and you would be right. How it works: In gnome sort, two adjacent elements are compared, and if they are in the wrong order, they are swapped. The comparison continues with the next element, and the same condition is checked, but the order is wrong, a swap takes place, and after the swap, the lower element is now compared to the previous element and if they are not in order,…
September 14, 2011 - - Comments:

C Algorithms – Graph Theory

The graph theory refers to the study of graphs. A graph is a mathematical object that captures the notion of connection. For example, you want to connect two or more dots that could be considered a graph. Leonhard Euler is the inventor of graph theory, as he tried to solve the known problem of the Seven Bridges of Konigsberg.The townspeople supposedly posed the question “Is it possible to take a walk through town, crossing each of the seven bridges just once, and ending up wherever you started?”A representation of the bridges:Euler realized that all the points on the island (for…
September 15, 2011 - - Comments:

C Algorithms – Topological Sort

Let us say that the order relation that was defined the in introduction lesson was a partial one, for example: a1 < a0, a1 < a2 < a3. The problem is to determine a list of order, in which if ai < aj then ai will come before aj in the final sorted list . For example, our list could be : a1, a0, a2, a3 or a1, a2, a0, a3 or a1, a2, a3, a0 Any partial ordered list can be sorted topological. For a graph, a topological sort of a directed graph refers to an ordering of the…
September 15, 2011 - - Comments:

C Algorithms – Depth-First Search (DFS)

Depth-first search (DFS) and breadth-first search (BFS) are two algorithms for traversing a graph. Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Each node may have to be visited more than once, and a root-like node that connects to all other nodes might not exist. Let us start first with DFS. DFS A Depth-first search (DFS) is a technique for traversing a finite undirected graph. DFS visits the child nodes before visiting the sibling nodes, that is, it traverses the depth of the tree before the breadth. Example: Legend: white…
September 16, 2011 - - Comments:

C Algorithms – Breadth-First Search (BFS)

Depth-first search (DFS) and breadth-first search (BFS) are two algorithms for traversing a graph. A breadth-first search (BFS) begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal. Example: In the case of BFS: If for DFS the traversal would be A, B, E, F, C, D, in the case of BFS it would be A, B, C, D, E, F. he BFS visits the nodes level by level, so it will start with level 0 which is…
September 16, 2011 - - Comments:

C Algorithms – Dijkstra’s Algorithm

This algorithm is a graph search algorithm that solves the shortest path problem for a graph. In the graph, the path between vertices has a cost or a length, so Dijkstra’s algorithm simply determines the path with the lowest cost between a vertex and another. The algorithm ends when the shortest path from a vertex to a destination vertex was discovered. How it works: 1) First thing to do is to set the distance value, which is 0 for the current node and infinity for the rest. 2) Set all the nodes as unvisited and initial node as current one;…
September 17, 2011 - - Comments:
Ads
Ads

Exforsys e-Newsletter

ebook
 
© 2021. All Rights Reserved.IT Training and Consulting