4

Running head: SORTING ALGORITHMS AND DYNAMIC DATASTRUCTURES

Sorting Algorithms and dynamic data structures

[Your Name Here]

[Your Class Name Here]

[Your School Name Here]

[Date Here]

A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions:

1.  The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);

2.  The output is a permutation, or reordering, of the input.

Sorting algorithms are of two main types:-

1>Comparision sorts:-

These include Bubble sort, Cocktail sort, Combo sort, Gnome sort, Selection sort, Insertion sort ,Shell sort, Library sort, Binary sort, Merge sort, In-place merge sort, Heap sort, Smooth sort, Quick sort sort ,Intro sort ,Patience sorting, Strand sort

2>Non comparison sorts: -

These include Pigeon hole sort, bucket sort, Counting sort, LSD Radix sort , MSD Radix sort, Spread sort.

As far as business applications of sorting algorithms are concerned, the list is numerous. For e.g we can take an example of a bank where the names and other details of the customer needs to be stored in a sorted manner. How can we imagine to do this without use of sorting algorithms. We cannot manually sort all the bulk amount of data. Sorting finds similar use in library systems, telephone books and other applications where data needs to be stored. Of course we need to choose the most efficient sorting algorithm taking into account the space and time complexity involved.

Now coming to dynamic data structures. These are data structures that grow and shrink as you need them to by allocating and deallocating memory from a place called the heap. They are extremely important because they allow the programmer to exactly control memory consumption and help in proper and efficient use of memory. Dynamic data structures allocate blocks of memory from the heap as required, and link those blocks together into some kind of data structure using pointers. When the data structure no longer needs a block of memory, it will return the block to the heap for reuse. This recycling makes very efficient use of memory.Link lists ,trees are good example of dynamic data structures.

As far as buusiness appications are concerned,the appications are far too many.For e.g when we have limited storage and we need to store important dat but not permanently.Also the data size is not fixed. To site when a mobile station needs to allocate voice channels to mobile users.These channels are not fixed and need to be deleted after the call is over.Aother example is suppose we want to store some customer details but don’t know how much details and of what size we are going to store.We obviously need to use dynamic data structures as the size is not fixed.If we use static data structures we may find that the storage space is insufficient or the storage space is wasted too much.Here dynamic data structures come into rescue and allocate space only how much is required.

References

How C Programming works,”Dynamic datastructures”. Retrieved April 14, 2009 from http://computer.howstuffworks.com/c27.htm

“Static and Dynamic datastructures” , Retrieved April 14, 2009 from http://en.wikipedia.org/wiki/Static_data_structure

Sorting algoithm overview,”Sorting algorithms”.Retrieved April 14, 2009 from http://linux.wku.edu/~lamonml/algor/sort/index.html