Data Structure

Unit-4

Lectuer-1

Internal Sorting

Lecture-2

Bubble Sort & Merge Sort

Lecture-3

Quick Sorting

Lecture-4

Heap Sorting

Lecture-5

Searching

Lecture-6

Radix  Sort

Lecture-7

Hashing

Lecture-8 and Lecture-9

Collision Resolution Techniques

UNIT – 4

Internal Sorting

Unit-04/Lecture-01

Insertion Sort  [RGPV/Dec 2011(10)] [RGPV/Dec 2012(7)] [RGPV/June2012(7)]

Algorithm Analysis
The insertion sort works just like its name suggests - it inserts each item into its proper place in the final list. The simplest implementation of this requires two list structures - the source list and the list into which sorted items are inserted. To save memory, most implementations use an in-place sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place.

Like the bubble sort, the insertion sort has a complexity of O(n²). Although it has the same complexity, the insertion sort is a little over twice as efficient as the bubble sort.

Pros: Relatively simple and easy to implement.
Cons: Inefficient for large lists.

The insertion sort is a good middle-of-the-road choice for sorting lists of a few thousand items or less. The algorithm is significantly simpler than the shell sort, with only a small trade-off in efficiency. At the same time, the insertion sort is over twice as fast as the bubble sort and almost 40% faster than the selection sort. The insertion sort shouldn't be used for sorting lists larger than a couple thousand items or repetitive sorting of lists larger than a couple hundred items.

Source Code
Below is the basic insertion sort algorithm. BACK

BACK

BACK

Selection Sort [RGPV/Dec 2011(10)] [RGPV/June2011(5)]

Algorithm Analysis

The selection sort works by selecting the smallest unsorted item remaining in the list, and then swapping it with the item in the next position to be filled. The selection sort has a complexity of O(n²).

Pros: Simple and easy to implement.
Cons: Inefficient for large lists, so similar to the more efficient insertion sort that the insertion sort should be used in its place.

The selection sort is the unwanted stepchild of the n² sorts. It yields a 60% performance improvement over the bubble sort, but the insertion sort is over twice as fast as the bubble sort and is just as easy to implement as the selection sort. In short, there really isn't any reason to use the selection sort - use the insertion sort instead.

If you really want to use the selection sort for some reason, try to avoid sorting lists of more than a 1000 items with it or repetitively sorting lists of more than a couple hundred items.

Source Code
Below is the basic selection sort algorithm.

BACK

BACK

BACK

Unit-04/Lecture-02/

Bubble Sort & Merge Sort

Bubble Sort

Algorithm Analysis
The bubble sort is the oldest and simplest sort in use. Unfortunately, it's also the slowest.

The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.

The bubble sort is generally considered to be the most inefficient sorting algorithm in common usage. Under best-case conditions (the list is already sorted), the bubble sort can approach a constant O(n) level of complexity. General-case is an abysmal O(n²).

While the insertion, selection, and shell sorts also have O(n²) complexities, they are significantly more efficient than the bubble sort.

Pros: Simplicity and ease of implementation.
Cons: Horribly inefficient.

A fair number of algorithm purists (which means they've probably never written software for a living) claim that the bubble sort should never be used for any reason. Realistically, there isn't a noticeable performance difference between the various sorts for 100 items or less, and the simplicity of the bubble sort makes it attractive. The bubble sort shouldn't be used for repetitive sorts or sorts of more than a couple hundred items.

Source Code
Below is the basic bubble sort algorithm.  BACK

BACK

BACK

Merge Sort [RGPV/Dec 2013(7)]

Algorithm Analysis

The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list. Like most recursive sorts, the merge sort has an algorithmic complexity of O(n log n).

Elementary implementations of the merge sort make use of three arrays - one for each half of the data set and one to store the sorted list in. The below algorithm merges the arrays in-place, so only two arrays are required. There are non-recursive versions of the merge sort, but they don't yield any significant performance enhancement over the recursive algorithm on most machines.

Pros: Marginally faster than the heap sort for larger sets.
Cons: At least twice the memory requirements of the other sorts; recursive.

The merge sort is slightly faster than the heap sort for larger sets, but it requires twice the memory of the heap sort because of the second array. This additional memory requirement makes it unattractive for most purposes - the quick sort is a better choice most of the time and the heap sort is a better choice for very large sets.

Like the quick sort, the merge sort is recursive which can make it a bad choice for applications that run on machines with limited memory.

Source Code
Below is the basic merge sort algorithm.

BACK

BACK

Unit-04/Lecture-03/Quick Sorting

 BACK

Quick Sort [RGPV/Dec 2011(10)] [RGPV/June 2011(10)] [RGPV/Dec 2013(7)]

Algorithm Analysis

The quick sort is an in-place, divide-and-conquer, massively recursive sort. As a normal person would say, it's essentially a faster in-place version of the merge sort. The quick sort algorithm is simple in theory, but very difficult to put into code (computer scientists tied themselves into knots for years trying to write a practical implementation of the algorithm, and it still has that effect on university students).

The recursive algorithm consists of four steps (which closely resemble the merge sort):

1. If there are one or less elements in the array to be sorted, return immediately.
2. Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.)
3. Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot.
4. Recursively repeat the algorithm for both halves of the original array.

The efficiency of the algorithm is majorly impacted by which element is choosen as the pivot point. The worst-case efficiency of the quick sort, O(n²), occurs when the list is sorted and the left-most element is chosen. Randomly choosing a pivot point rather than using the left-most element is recommended if the data to be sorted isn't random. As long as the pivot point is chosen randomly, the quick sort has an algorithmic complexity of O(n log n).

Pros: Extremely fast.
Cons: Very complex algorithm, massively recursive.

The quick sort is by far the fastest of the common sorting algorithms. It's possible to write a special-purpose sorting algorithm that can beat the quick sort for some data sets, but for general-case sorting there isn't anything faster.

As soon as students figure this out, their immediate implulse is to use the quick sort for everything - after all, faster is better, right? It's important to resist this urge - the quick sort isn't always the best choice. As mentioned earlier, it's massively recursive (which means that for very large sorts, you can run the system out of stack space pretty easily). It's also a complex algorithm - a little too complex to make it practical for a one-time sort of 25 items, for example.

With that said, in most cases the quick sort is the best choice if speed is important (and it almost always is). Use it for repetitive sorting, sorting of medium to large lists, and as a default choice when you're not really sure which sorting algorithm to use. Ironically, the quick sort has horrible efficiency when operating on lists that are mostly sorted in either forward or reverse order - avoid it in those situations.

Source Code
Below is the basic quick sort algorithm.

BACK

UNIT 2/LECTURE-04/Heap Sorting

BACK

 Heap Sort [RGPV/Dec 2013(7)]

Algorithm Analysis

The heap sort is the slowest of the O(n log n) sorting algorithms, but unlike the merge and quick sorts it doesn't require massive recursion or multiple arrays to work. This makes it the most attractive option for very large data sets of millions of items.

The heap sort works as it name suggests - it begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

To do an in-place sort and save the space the second array would require, the algorithm below "cheats" by using the same array to store both the heap and the sorted array. Whenever an item is removed from the heap, it frees up a space at the end of the array that the removed item can be placed in.

Pros: In-place and non-recursive, making it a good choice for extremely large data sets.
Cons: Slower than the merge and quick sorts.

As mentioned above, the heap sort is slower than the merge and quick sorts but doesn't use multiple arrays or massive recursion like they do. This makes it a good choice for really large sets, but most modern computers have enough memory and processing power to handle the faster sorts unless over a million items are being sorted.

The "million item rule" is just a rule of thumb for common applications - high-end servers and workstations can probably safely handle sorting tens of millions of items with the quick or merge sorts. But if you're working on a common user-level application, there's always going to be some yahoo who tries to run it on junk machine older than the programmer who wrote it, so better safe than sorry.

Source Code
Below is the basic heap sort algorithm. The siftDown() function builds and reconstructs the heap.

void heapSort(int numbers[], int array_size)

{

  int i, temp;

  for (i = (array_size / 2)-1; i >= 0; i--)

    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)

  {

    temp = numbers[0]; BACK

    numbers[0] = numbers[i];

    numbers[i] = temp;

    siftDown(numbers, 0, i-1);

  }

}

BACK

void siftDown(int numbers[], int root, int bottom)

{

  int done, maxChild, temp;

  done = 0;

  while ((root*2 <= bottom) && (!done))

  {

    if (root*2 == bottom)

      maxChild = root * 2;

    else if (numbers[root * 2] > numbers[root * 2 + 1])

      maxChild = root * 2;

    else

      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])

    {

      temp = numbers[root];

      numbers[root] = numbers[maxChild];

      numbers[maxChild] = temp;

      root = maxChild;

    }

    else

      done = 1;

  }

}

BACK

Unit-04/Lecture-05/Searching

Linear Search BACK

In C Programming, we looked at the problem of finding a specified value in an array. The basic strategy was:

Look at each value in the array and compare it to what we're looking for. If we see the value at any time, return that we've found it. Otherwise, if after we're done at looking through each item in the array, if we still haven't found it, then return that the value isn't in the array. In code, we have something like this:

int search(int array[], int len, int value) {

 int i;

  for (i=0; i<len; i++) {

    if (array[i] == value)

      return 1;

  }

return 0;

}

Clearly, for an unsorted array, this algorithm is optimal. There's no way you can definitively say that a value isn't in the array unless you look at every single spot. (Similarly, there's no way you can say that you DON'T have some piece of paper or form unless you look through ALL of your pieces of paper.)

Binary Search[RGPV/June 2011(5)] [RGPV/Dec 2013(7)]

Now,  how can we adapt this idea to work for searching for a given value in an array?

If I am given the array:

Now let's put this idea together and code it up:

int binsearch(int a[], int len, int value) {

 int low = 0, high = len-1;

 while (low <= high) {

 int mid = (low+high)/2;

  if (value < a[mid])

      high = mid-1;

    else if (value > a[mid])

      low = mid+1;

    else

      return 1;

  } BACK

return 0;

}

At the end of each array iteration, all we do is update either low or high. Doing so modifies our search region to be smaller than it previously was, based on the last comparison we made.

BACK

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

What are the different techniques of searching. Explain the one which is more efficient among them.

DEC2013

7

Q.2

Explain briefly Binary searching.

June 2011

5

Unit-04/Lecture-06/Radix  Sort

Radix  Sort :

BACK

Definition[edit]

Each key is first figuratively dropped into one level of buckets corresponding to the value of the rightmost digit. Each bucket preserves the original order of the keys as the keys are dropped into the bucket. There is a one-to-one correspondence between the number of buckets and the number of values that can be represented by the rightmost digit. Then, the process repeats with the next neighbouring more significant digit until there are no more digits to process. In other words:

1.     Take the least significant digit (or group of bits, both being examples of radices) of each key.

2.     Group the keys based on that digit, but otherwise keep the original order of keys. (This is what makes the LSD radix sort a stable sort.)

3.     Repeat the grouping process with each more significant digit.

The sort in step 2 is usually done using bucket sort or counting sort, which are efficient in this case since there are usually only a small number of digits.

An example[edit]

Original, unsorted list:

170, 45, 75, 90, 802, 2, 24, 66

Sorting by least significant digit (1s place) gives:

170, 90, 802, 2, 24, 45, 75, 66

Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.

Sorting by next digit (10s place) gives:

802, 2, 24, 45, 66, 170, 75, 90

Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.

Sorting by most significant digit (100s place) gives:

2, 24, 45, 66, 75, 90, 170, 802

It is important to realize that each of the above steps requires just a single pass over the data, since each item can be placed in its correct bucket without having to be compared with other items.

Some radix sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an array. Consider the previous list of keys viewed in a different way:

170, 045, 075, 090, 002, 024, 802, 066

The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes: BACK

2 (bucket size for digits of 0: 170, 090)

2 (bucket size for digits of 2: 002, 802)

1 (bucket size for digits of 4: 024)

2 (bucket size for digits of 5: 045, 075)

1 (bucket size for digits of 6: 066)

A second counting pass on the next more significant digit of each key will produce an array of bucket sizes:

2 (bucket size for digits of 0: 002, 802)

1 (bucket size for digits of 2: 024)

1 (bucket size for digits of 4: 045)

1 (bucket size for digits of 6: 066)

2 (bucket size for digits of 7: 170, 075)

1 (bucket size for digits of 9: 090)

A third and final counting pass on the most significant digit of each key will produce an array of bucket sizes:

6 (bucket size for digits of 0: 002, 024, 045, 066, 075, 090)

1 (bucket size for digits of 1: 170)

1 (bucket size for digits of 8: 802)

At least one LSD radix sort implementation now counts the number of times that each digit occurs in each column for all columns in a single counting pass. (See the external linkssection.) Other LSD radix sort implementations allocate space for buckets dynamically as the space is needed.

BACK

UNIT-04/LECTURE -07/Hashing

BACK

HASHING [RGPV/June 2011(10)][RGPV/June2012(14)][RGPV/Dec2012(14)][RGPV/Dec2013(7)]

Hashing is a searching technique which is key to address transformation technique. The normal linear and binary search technique, searches for a key via sequence of comparisons. Hashing differs from this in that the address or location of an identifier X, is obtained by computing some arithmetic function, f of X, f(x) gives the address of X in the table. This address will be referred to as the hash or home address of X. Depending on the address yielded by the function the data are stored in sequential memory location, called hash table.

Hash Table:

The memory available to maintain the symbol table is assumed to be sequential. This memory is referred to as the hash table HT. The hash table is partitioned into b buckets, HT(0), HT(1), …,HT(b –1). Each bucket is divided into S slots and each slot is capable of holding a records. Thus, a bucket is said to consist of s slots, each slot being large enough to hold  1 record. Usually s =1 and each bucket can hold exactly 1 record. A hashing function, f(x), is used perform an identifier transformation on X. f(x) maps the set possible identifier on to the integers 0 through b –1.

The ratio n/T is the identifier density, while n /(s*b) is the loading density or loading factor.

Where             n is the number of identifiers ,

b is number of buckets,

T is total number of possible identifiers

s is number of slots.

BACK

HASHING FUNCTION [RGPV/Dec 2011(10)]

 A hashing function, f ,transforms an identifier X into a bucket address in the hash table .As mentioned earlier the desired properties of such  a function are that it be easily computable and that it minimize the number of collisions.

Since many programs use several identifiers with the same first letter, we would like the function to depend upon all the characters in the identifiers in addition, we would like the hash function to be such that it does not result in a biased use of the hash table for random inputs.

Several kinds of uniform hash functions are in use.

1 . Division      2.  Mid-square      3 .Folding   4.  Digit Analysis

Only division method is used frequently and is most preferred one.

BACK

Division Method:

This is the most common method used for hash function. The function is used to find a number may be prime or it is number of buckets. Then the number will be used to divide the key by it. The remainder is the hash address for that key. For example let us consider a hash table of 10 buckets and try to find the address of following values.

34, 56, 89, 432, 87, 651

the home address of 34 will be 34%10 = 4

The home address of 56 will be 56%10 = 6

And so on for others as mentioned in the table

                                                   KEY       INFO

Some times two different keys may yield same hash address. The there will be collision between the keys. There are few techniques for resolving the collision.

BACK

Collision Resolution Technique:

When there is a collision, then a random rehashing function is used to resolve the collision. The efficiency of collision resolution procedure is measured by the average number of probes(key comparisons) needed to find the location of the record with the given key.

Normally the collision is resolved by dividing the each bucket into multiple slots. So, that the keys of same address can be kept in different slots of same bucket. There are two different ways to resolve the collision.

(I)                 Open Addressing

(II)                Chaining.

The open addressing is uses a sequential representation for hash table like two dimensional or three dimensional array. The chaining concept uses a linked representation for each bucket and each bucket is linked with linked list maintaining the slots of that bucket.

 BACK

BACK

UNIT-04/LECTURE-08/ Collision Resolution Techniques

Collision Resolution Techniques [RGPV/Dec2011(10)]

(1)   Chaining

BACK

Hash collision resolved by separate chaining.

In the method known as separate chaining, each bucket is independent, and has some sort of list of entries with the same index. The time for hash table operations is the time to find the bucket (which is constant) plus the time for the list operation. (The technique is also called open hashing or closed addressing.)

In a good hash table, each bucket has zero or one entries, and sometimes two or three, but rarely more than that. Therefore, structures that are efficient in time and space for these cases are preferred. Structures that are efficient for a fairly large number of entries are not needed or desirable. If these cases happen often, the hashing is not working well, and this needs to be fixed.

Separate chaining with linked lists.

Chained hash tables with linked lists are popular because they require only basic data structures with simple algorithms, and can use simple hash functions that are unsuitable for other methods.

The cost of a table operation is that of scanning the entries of the selected bucket for the desired key. If the distribution of keys is sufficiently uniform, the average cost of a lookup depends only on the average number of keys per bucket—that is, on the load factor.

Chained hash tables remain effective even when the number of table entries n is much higher than the number of slots. Their performance degrades more gracefully (linearly) with the load factor. For example, a chained hash table with 1000 slots and 10,000 stored keys (load factor 10) is five to ten times slower than a 10,000-slot table (load factor 1); but still 1000 times faster than a plain sequential list, and possibly even faster than a balanced search tree.

For separate-chaining, the worst-case scenario is when all entries are inserted into the same bucket, in which case the hash table is ineffective and the cost is that of searching the bucket data structure. If the latter is a linear list, the lookup procedure may have to scan all its entries, so the worst-case cost is proportional to the number n of entries in the table.

The bucket chains are often implemented as ordered lists, sorted by the key field; this choice approximately halves the average cost of unsuccessful lookups, compared to an unordered list. However, if some keys are much more likely to come up than others, an unordered list with move-to-front heuristic may be more effective. More sophisticated data structures, such as balanced search trees, are worth considering only if the load factor is large (about 10 or more), or if the hash distribution is likely to be very non-uniform, or if one must guarantee good performance even in a worst-case scenario. However, using a larger table and/or a better hash function may be even more effective in those cases.

Chained hash tables also inherit the disadvantages of linked lists. When storing small keys and values, the space overhead of the next pointer in each entry record can be significant. An additional disadvantage is that traversing a linked list has poor cache performance, making the processor cache ineffective.

Separate chaining with list head cells[edit] BACK

Hash collision by separate chaining with head records in the bucket array.

Some chaining implementations store the first record of each chain in the slot array itself.The number of pointer traversals is decreased by one for most cases. The purpose is to increase cache efficiency of hash table access.

The disadvantage is that an empty bucket takes the same space as a bucket with one entry. To save memory space, such hash tables often have about as many slots as stored entries, meaning that many slots have two or more entries.

Separate chaining with other structures BACK

Instead of a list, one can use any other data structure that supports the required operations. For example, by using a self-balancing tree, the theoretical worst-case time of common hash table operations (insertion, deletion, lookup) can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost if long delays must be avoided at all costs (e.g. in a real-time application), or if one must guard against many entries hashed to the same slot (e.g. if one expects extremely non-uniform distributions, or in the case of web sites or other publicly accessible services, which are vulnerable to malicious key distributions in requests).

The variant called array hash table uses a dynamic array to store all the entries that hash to the same slot. Each newly inserted entry gets appended to the end of the dynamic array that is assigned to the slot. The dynamic array is resized in an exact-fit manner, meaning it is grown only by as many bytes as needed. Alternative techniques such as growing the array by block sizes or pages were found to improve insertion performance, but at a cost in space. This variation makes more efficient use of CPU caching and the translation look aside buffer (TLB), because slot entries are stored in sequential memory positions. It also dispenses with the next pointers that are required by linked lists, which saves space. Despite frequent array resizing, space overheads incurred by operating system such as memory fragmentation, were found to be small.

An elaboration on this approach is the so-called dynamic perfect hashing, where a bucket that contains k entries is organized as a perfect hash table with k² slots. While it uses more memory (n² slots for n entries, in the worst case and n*k slots in the average case), this variant has guaranteed constant worst-case lookup time, and low amortized time for insertion.

BACK

UNIT-04/LECTURE-09/ Collision Resolution Techniques

(2)      Open addressing

BACK

Hash collision resolved by open addressing with linear probing (interval=1). Note that "Ted Baker" has a unique hash, but nevertheless collided with "Sandra Dee", that had previously collided with "John Smith".

In another strategy, called open addressing, all entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found. When searching for an entry, the buckets are scanned in the same sequence, until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. The name "open addressing" refers to the fact that the location ("address") of the item is not determined by its hash value. (This method is also called closed hashing; it should not be confused with "open hashing" or "closed addressing" that usually mean separate chaining.)

Well-known probe sequences include: BACK

·         Linear probing, in which the interval between probes is fixed (usually 1)

·         Quadratic probing, in which the interval between probes is increased by adding the successive outputs of a quadratic polynomial to the starting value given by the original hash computation

·         Double hashing, in which the interval between probes is computed by another hash function

A drawback of all these open addressing schemes is that the number of stored entries cannot exceed the number of slots in the bucket array. In fact, even with good hash functions, their performance dramatically degrades when the load factor grows beyond 0.7 or so. Thus a more aggressive resize scheme is needed. Separate linking works correctly with any load factor, although performance is likely to be reasonable if it is kept below 2 or so. For many applications, these restrictions mandate the use of dynamic resizing, with its attendant costs.

Open addressing schemes also put more stringent requirements on the hash function: besides distributing the keys more uniformly over the buckets, the function must also minimize the clustering of hash values that are consecutive in the probe order. Using separate chaining, the only concern is that too many objects map to the same hash value; whether they are adjacent or nearby is completely irrelevant. BACK

Open addressing only saves memory if the entries are small (less than four times the size of a pointer) and the load factor is not too small. If the load factor is close to zero (that is, there are far more buckets than stored entries), open addressing is wasteful even if each entry is just two words.

This graph compares the average number of cache misses required to look up elements in tables with chaining and linear probing. As the table passes the 80%-full mark, linear probing's performance drastically degrades.

Open addressing avoids the time overhead of allocating each new entry record, and can be implemented even in the absence of a memory allocator. It also avoids the extra indirection required to access the first entry of each bucket (that is, usually the only one). It also has better locality of reference, particularly with linear probing. With small record sizes, these factors can yield better performance than chaining, particularly for lookups. Hash tables with open addressing are also easier to serialize, because they do not use pointers.

On the other hand, normal open addressing is a poor choice for large elements, because these elements fill entire CPU cache lines (negating the cache advantage), and a large amount of space is wasted on large empty table slots. If the open addressing table only stores references to elements (external storage), it uses space comparable to chaining even for large records but loses its speed advantage.Generally speaking, open addressing is better used for hash tables with small records that can be stored within the table (internal storage) and fit in a cache line. They are particularly suitable for elements of one word or less. If the table is expected to have a high load factor, the records are large, or the data is variable-sized, chained hash tables often perform as well or better.

Ultimately, used sensibly, any kind of hash table algorithm is usually fast enough; and the percentage of a calculation spent in hash table code is low. Memory usage is rarely considered excessive. Therefore, in most cases the differences between these algorithms are marginal, and other considerations typically come into play.

BACK