10 January 2011 Comments Off

Sorting again, advanced!

Sorting again, advanced!

In common programming, you don’t often find yourself coming across a need for direct sorting. The user will usually want the info in whatever order it is given for usual reasons. However, if the user wants something sorted in a certain direction, how would you go about doing it?

Say you have a 1, 5, 10, 20, and 50 dollar bill in the order of 50 – 10 – 20 – 1 – 5. We has humans can easily sort this money into least to greatest or greatest to least. But we take for granted the actual undertaking of the common practice.

When we try an implement one via machine code, we hit algebraic equations, recursion functions, numbers we’ve never seen. We can’t simply put it in order like we do with our brain however easy that seems. However, we can simulate how we order our dollar bills.

For instance, take the dollar bills and try and sort them. By default and by nature, your brain should have told you to go by some pattern. My brain told me the highest numbers were 50 and 1 then placed them in respective locations. Then I look for something of equal or lower value and place it underneath and then keep iterating looking for more of the same value or lower until I come up with a lowest. And then I try and reiterate trying to find the second lowest, and then next highest, and so on until its organized.

Implementing it in this respect is easy but to be honest, its often not very efficient. Our brains take a simple route because it has the power to calculate it in milliseconds and we often can’t tell the difference. If our brain chose a too difficult a pattern to organize the bills, it will choose another path that is more simple or will continue going about the same pattern in a different manner. However, you never change algorithms via digital sort and you are always trying to find the most optimized and fastest ways to code possible. This is why the algorithm article is here. It shows not only different algorithms but the math behind it and where to apply them.

Terms and Concepts

Some terms and concepts you may need to know will also not be explained by myself as I am not one to really teach the concepts, but more to understand it in my own little world. Instead, I will give you directions on where to look for understanding of the concepts and terms, starting with Big O notation.

Big O notation is simply a mathematical way to express the time it takes for a function to finish: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Another concept you will need to understand is algorithm complexity, which is the a judgement of difficulty of the algorithm given which often measures space and timing of the algorithm. A much better source of information would be here on the wiki: http://en.wikipedia.org/wiki/Computational_complexity_theory#Machine_models_and_complexity_measures

I personally and honestly do not understand all there is to it, just enough to understand the measurement of complexity. Another article worth looking at would be this: http://www.progressive-coding.com/tutorial.php?id=1

Another concept to understand would be algorithm stability which is the ability of an algorithm to keep the relative locations of an element of the same value in the sorted array. Say for instance, you have 2 five dollar bills and they need to be sorted and one has a check mark on them and the other does not. In a stable algorithm, the one in front of the other will still be in front of the other after sorted. This is considered having a stable algorithm. In most cases its not needed but in the case that you have a second value attached to the array of values you want sorted, it is a must to understand algorithm stability and how it affects you.

And last but not least is algorithm adaptability. This is the ability of the algorithm to take an already partially-sorted array and be able to continue where it left off and finish sooner than if it it wasn’t pre-sorted. This is often a big deal since it can exponentially save you time.

Once you understand the basics of these terms and concepts, you may be able to follow and compare different algorithms and understand why I choose one algorithm over the other.

Comparison Sort Algorithms

The most common type of algorithm in use today is called the comparison sort which is a general category of algorithms. All it means is that the algorithm compares one element to another and reacts based on the outcome of that comparison to sort the array.

A common comparison sort is the bubble sort which is in a subcategory of comparison sorting called exchange sorting, which consists of swapping adjacent items until the sort is finished:

Slightly optimized version: http://codepad.org/YCJpEFMN

It’s often inefficient and is used for simplistic, educational reasons only. The complexity of the algorithm on average is O(n^2) which means that it is very bad on larger lists. The complexity on best case performance would be O(n) in the case that the array is already sorted. However, it is easy to implement, stable, and adaptable.

A step up from this type of sort is the insertion sort which is a type and sort on it’s own with many variations. It’s a bit more efficient than bubble sort although the complexity is often O(n^2) as is the inefficient bubble sort we talked about. It has many advantages over bubble sort but most of which aren’t good enough to be used commonly for larger lists. It’s also a bit more complex to implement. Here is an example:


26 October 2010 Comments Off

90+ Beginners Lab Assignments in C Langauge

  1. A Calculator in C Using Graphics & Mouse Operations
  2. A chat program in C
  3. A program to implement Heap Sort
  4. All types of Linked List Operations
  5. Analog and Digital clock
  6. Begginers of system programming
  7. Bomber Fighter Plane simulation
  8. Bubble Sorting Algorithm
  9. Calendar of Thousands of Years
  10. Calendar Program
  11. Calender Program in C
  12. Calender
  13. Class with constructor ( for bank account )
  14. Convert decimail nos to roman equivalent upto 10,000
  15. Converting Roman letter to number
  16. convertion of number to letters
  17. CPU Scheduling algorithm implementation
  18. Decimal to Binary, Octal and HEX converter
  19. encryption and decryption of files
  20. Finding LCM and GCD
  21. Frequency Based Histogram
  22. Graphical Calculator Design
  23. Guessing Game in C
  25. Invoke function without main in C Language
  26. Kite flying code in C
  27. Merge sort
  28. No guessing
  29. N-Queen’s Problem
  30. Factorial Function
  31. Prg. to convert upper case to lower case or lower case to upper case
  32. Prg. to correct rudimentary syntax errors
  33. Prg. to count no. of characters,no. of blanks,no. of words & no.
  34. Prg. to sort any no. of numeral i-p in ascending or descending order.
  35. Printint a double pyramid
  36. Program for Binary, Octal, Hexadecimal Conversions
  37. Program for computing Area, Volume and Perimeter of Rrectangle using
  38. Program for finding the prime numbers
  39. Program for finding the sum of digits of a five digit number
  40. Program for Prime Number Generation
  41. Program for rotating circles using maths.(sin,cos,Phase defference,e.t.c)
  42. Program Implementing the rot13 algorithm
  43. Program of Falling Characters
  44. Program to calculate frequency of vowels in a string
  45. Program to Calculate the Pascal triangle
  46. Program to calculate the sum of series

Source: http://www.c.happycodings.com/Beginners_Lab_Assignments/

4 July 2010 Comments Off

Sorting Algorithm Examples

This is a collection of programs implementing a wide variety of sorting algorithms. The code has been optimized for speed instead of readability. You will find them to perform better than the perspective standard algorithms. The Combo Sort should be suitable for production usages.

These examples were constructed by studying the following text books:

  • Robert Sedgewick, “Algorithms in C”
  • Mark Allen Weiss, “Data Structures and Algorithm Analysis”
  • Tenenbaum, Langsam, Augenstein, “Data Structures Using C”

Some short descriptions on each of the algorithms:

  • Bubble Sort :Exchange two adjacent elements if they are out of order. Repeat until array is sorted. This is a slow algorithm.
  • Selection Sort: Find the largest element in the array, and put it in the proper place. Repeat until array is sorted. This is also slow.
  • Insertion Sort :Scan successive elements for out of order item, then insert the item in the proper place. Sort small array fast, big array very slowly.
  • Quicksort :Partition array into two segments. The first segment all elements are less than or equal to the pivot value. The second segment all elements are greater or equal to the pivot value. Sort the two segments recursively. Quicksort is fastest on average, but sometimes unbalanced partitions can lead to very slow sorting.
  • Mergesort :Start from two sorted runs of length 1, merge into a single run of twice the length. Repeat until a single sorted run is left. Mergesort needs N/2 extra buffer. Performance is second place on average, with quite good speed on nearly sorted array. Mergesort is stable in that two elements that are equally ranked in the array will not have their relative positions flipped.
  • Heapsort :Form a tree with parent of the tree being larger than its children. Remove the parent from the tree successively. On average, Heapsort is third place in speed. Heapsort does not need extra buffer, and performance is not sensitive to initial distributions.
  • Shellsort: Sort every Nth element in an array using insertion sort. Repeat using smaller N values, until N = 1. On average, Shellsort is fourth place in speed. Shellsort may sort some distributions slowly.
  • Combo Sort: Sorting algorithms can be mixed and matched to yield the desired properties. We want fast average performance, good worst case performance, and no large extra storage requirement. We can achieve the goal by starting with the Quicksort (fastest on average). We modify Quicksort by sorting small partitions by using Insertion Sort (best with small partition). If we detect two partitions are badly balanced, we sort the larger partition by Heapsort (good worst case performance). Of course we cannot undo the bad partitions, but we can stop the possible degenerate case from continuing to generate bad partitions.