DS Complete Unit 5

1110.6 QUICK SORT Lapeli cali af stack) It is one of the most po Jar sorting techniques. Quick sort possesses a very good average-case behaviour among alll the sorting techniques. This is developed by C.A’R. Hoare. The quicksort algorithm works by partitioning the array to be sorted. And each partition is in_Q\Wot turn sorted recursively. In partition, one of the array elements is chosen as a key value. This key value can be the first element of an array. Thatis, if is an array then key = a[0], and rest of the array elements are grouped into two partitions such that © One partition contains elements smaller than the key value. % Another partition contains elements larger than the key value. Figure 10.2 shows a key and partitions of element in an array. Values < Key Key Values > keyBe ing elements : ji with the following ©! ider an array Wr sp 99 90 14 68 6 97 key Wo Tiren two indices namely, low and high are ; Here, 45 is selected as @ [34 ent. The low index starts on the left Use, ® indicate the element (key +1) and the last elem« i that is grea Jue. Then these elements are interchange ty an clement that is grea ter than the key val cs srocess is repeated until all elements to the left of the key are smaller than the key oe i elements to the right of the key are greater i than the key value. And ‘The steps involved in placing the key value, 45 in its proper position in the array are frat below. The elements being compared are encircled on each line. Bix Aus low. 45 —___| The given array has been p: \ artitior i the second subarray is (68, ator eataate subarrays. The first subarray is (14, 26,3914 | of these subarrays until the entire arrey wo cat SePeatedly apply this procedure on DNs an) exchange technique, ‘anged, this technique is called partition In the quick sort techni ique, each ti . subarrays, each of these subarrays time the given array is partitioned into two smallet recursive quick sort Slgosthes eee Broessed either Heraively or recursive: ™ gorithm is presented belaw(0 10.7 BUCKET OR RADIX SORT Bucket sort or radix sort, is a method can be used to sort a list of names alphabetically. Here the base or radix is 26, (the 26 letters of the alphabet). First of all the list of names is sorted according to the first letter of each name thus the names are arranged in 26 buckets. Insecond pass, names are arranged according to the second letter of each name and so on this process depend on the length of the names with maximum letters. Suppose if no name contains more than 15 letters, the names are alphabetized with at most 15 passes. To sort decimal numbers, where radix or base is 10, we need ten buckets. These buckets are numbered 0, 1, 2, 3, 4, 5,6; 7, 8, 9. Unlike, sorting names, decimal numbers are sorted from tight to left.aoe . — an — we _ 121 70 965 432 12 7 a 906 on [siz 603 |__| L_] sa] Lo} Lt peed a 0 7 7 0 7 (a) (Pass-t) : | [7 70° o05| [577] | oss [12 fat 432 uj 4 2 0 1 2 3 4 5 8 cone (6) (Passi 70 124 | 482 | 2 683 965, 70 ) Sv7 12 121 432 577, 683 965, 0 1 2 3 4 5 6 7 8 9 (b) (Pass-Hl) After pass III, when the numbers are checked, they are in ascending order : 12-70 «121 432 «577. 683 965 In this example, there are three passes, depending upon the number of digits in largest number 965. Algartthim Let a be an array with n elements in the memory. 1. Find the largest element of the array. 2. Find the total no. of digits num in the largest digit set digit = num 3. Repeat steps 4, Wfor pass = 1 to num 4. Initialize buckets For i=1to(n-1) Set num = obtain digit number pass of af i] put af i J in bucket number digit [end of for Joop] 5. calculate al] numbers from the bucket in order 6. Exit195 FA! awl DATA STRUCTURES THROUGH C Paiag 7? 557 a 110.8 MERGE SORT 2h ebwvh ‘Merge sort is a sorting technique which divides the array into subarrays of size 2 and merge ‘djacent pairs. We then have approximately n/2 arrays of size 2. This process is repeated until there is only one array remaining of size n. Suppose an array a withn elements afl}, a[2], which sorts a will first be described by me: +, a[N] is in memory. The merge-sort algorithm ans of a specific example. less zexampl yi Suppose the array a contains 12 elements as follows: Z (ess 85,76, 46, 92, 30, 41, 12,19, 93,3, 50, 11 A Each pass of the merge sort algorithm will start at the beginning of the array A and merge pairs of sorted subarrays as follows : Pass I: Merge each pair of elements to obtain the following list of sorted pairs : 76 | 85 46 | 92 30 | 41 12 | 19 3 | 93 11 | 50 Pass I: Merge each pair of pairs to obtain the lists of sorted elements : 46 | 76 | 85 | 92 2 [19 | 90] a 3 [at] 50] 93 Pass Ill: Again Merge the two subarrays to get two lists. | 19 | 30 | 41 | 46 | 76 | a5 | 92 3 | 1 | 50 | 93 Pass IV: Merging the above two lists, we get 3 | mM | 12 | 19 | 30 | 41 | 46 | 50 | 76 | 85 | 92 | 93 In Pass IV, we get Sorted list of elements of array a with the size 12.VATA STRUCTURES, THROUGH 0.9 HEAP SORT 61 a! jn this method, we will interpret th 5 : he arra representation of the binary tree; we aie '0 be sorted as a bina s have . ry tree, i i a _ » in a sequential 1. The father node at location (i ~ 29/2 if jis not | 's Not equal to zero. Z. The left child at location 2i 4, | Oy }3) x3 The right child at location 2i 43. re 2 Up. ft aay = OA} {as the subscripts in C start from 0 to (MAXSIZE " 7) 2 2 “s heap is defined as an alm to ‘ost complete binary tree of ode is less than or equal to the value of the father, i ghee eater complete binary tree, we can write it as * WU) SKG- DA for os GI HAL LaNy in " Sequential representation of an almost This implies that fre root of the bina 112 mnt) has the largest key in ; Toot c ry tree (ie., the first array gest key i element) h i the heap. This type of heap is usually called descending heap or max I _ fe = from the root node to a terminal node fo1 ordered iis arrange Ms an ord i i ie inal node dered list of elements arranged in descending o | 2 us G [es [43 | | 28 38 [48 | 50 | Figure403_ A heap representation almost complete binary tree in which the value of {We can also define an ascending heap a5." Jue of its father. This implies that the root ‘of the each node is greater than or equal to the val binary tree has the smallest element of the heap. This type of heaps also called min heap. ] Zheap is very useful in implementing priority ae ‘The priority queue is a data structure ih which the intrinsic ordering of the data items vietermines the result ofits basic operations. Primarily queues can be classified as shown below : % Ascending priority queue: % Descending priovity queue: 3 An ascending priority queue can be defined as a grou are inserted arbitrarily but only the smallest element is descending priority queue can be defined 25 0 group of elem but only the largest element is deleted from it pp of elements to which new elements e other hand, a deleted from it, On th ents that are inserted arbitrarilyDATA STRUCTURES THROUGH C ou . .gorting Using a Heap wes pha e 10% can be used to sort a set of clin, Let A be an array of n elements which is used to ane a descending priority queue. The two main Processing stages of a heapsort are va a heap using DPQ_insert operation and adjusting the heap as a result of deletion creat operation. 565 construction and adjustment phases of a heap are illustrated below, The following are the The a inal array. elements of the ofigi y’ a ;eure 10.4 shows the trace of the creation of the heap. The dotted lines indicate an element Fe ed an ee. 56S) io Has) @THROUGH © DATA STRUCTURES sos HOP. ae hela 3 dale) (9) Al2] = DPQ_delete_max(A, 3) (b) Aft] = DPQ_delete_max(A, 2) Figure404_ Heap adjustment Qrted ? me —“Gi ialee- se ———— ici di = : 40,60, 50, 83, 55,41): 6 ——OF 5 Kook = A NOLL, age locs = Nove pe = Nee” exit Co) 5 em = § a at —— oy tS ee ae = = esl ele Q3 Ve Ne ) Heige @alonce-Ti lace. Cost fice) ; tae wal a, pew fined nodeg_Ottiy al No lool” hear Laas alt node 2 le Lever han | Loe, A A trees hetpitt balanie ade de 4S agit S, He Tes San of bagale ‘sublice rot nmotie ome eee ret Te called aa vet . ia . £ Lends’) i Bak pele ‘Av Teed. “hela. we ‘ AG “has fi te idee 9 res rws puck 2) lee Hon ty Le, Les _ | — tee po OS Me eam hot Het — f tuo subtree, GAg_ Larne, _ ! sy “Eh ub tree is ok Sob Pree 1s Role. End i bast vrbalen ca inn fers serted- hes "Tap Nido Hn HE int _ 2 node Unbalence node rn 7 direction of leaf node. ten use Prpar wiitien2 | BF che not ‘mart. tear +4 or-| Thea ake Hy Rotadn 1 oe y 1 eR 4) en i) Lt ebay. 2 el _ @_— (8) —_— “LL on \ Le : 6) @ (A) ©mn 66,22, IS, Ny 83,22, 35°, 25,46, 88) 99oe = es + ‘ oO arn So a eG e—& SS. cE — ams a sen pase BC ve cs Ao = a Sara | B PE} 7 XS a RR om == | Dis Y ? .| Bixee fs a balanced Moi 7 : anode (ie Bee ys wh Wee fa whe a : — Keyed E, ! painter to. hbilebuen aes ae —i BT sae _Fs alte snoon 102 Lalanie ef A binasy bree, * ac Te - Fare ke sensnal Cualiffones Eas | lta Bent be top sa MEAP ALLA 2 : __ © hee Auuk Le no engty gbbiee Of Teay of da tice ns ball be on Mu same loue en ne hase atleast — ME eoironttant no: 4g arte: a a] J to Coes at H ee ped. ele meds dun - EER e ot ! 56/88, 12, 13, 120, 5 F——— yo a plbhipgpleinn ok oye aa) Ee jo — ES sen her 3 - C5: 8 ©. © Ada 1B: + a od = Th, 31S oo —DS Bre of oe ws. Qers wTet nS DuKzsePA eran aes x = = ATS a Kars a 6) Add nN iv - ae i—s —> _oe <—oN,d Ww 8 GZ C2) Act M.8.11.2 B-Tree Deletion ‘asin the insertion method, the record to be delete is frst searched for. GW the record isin terminal node, deletion is simple. The record along with an appropriate pointer is deleted. @ Ifthe record is not in terminal node, it is replaced by a copy of its successor, that is, a seine Tvh a next higher value. The successor of any record not atthe lowest level ‘Sirways be ina ferminal node. Thus in all cases deletion involves removing a record from a terminal node. cord, the new node size is not below the minimum, the deletion is @ Ifondeleting the re “over. If the new node size is lower than the Redistribution is carried out if either of adjacent siblings contains more than the minimum number of records, for redistribution the contents of the node which has less than minimum records, and the separating record from parent are collected, The central record from this rollection is written back to parent. The left and right halves are written back to the two siblings. . In case the node with less than mi more than minimally full. Concatenation i adjacent sibling and the separating record from its parent. It may be solved by redistribution or concatenation. minimum, an underflow occurs. inimum number of records has no adjacent sibling that is In this case the node is merged with its ceExample: We will illustrate by deleting keys from the tree given below : we 1. Delete ‘i’ this is a simple deletion.pre caia wy i sor is, 2. Delete 7.’ is not ata leaf node, Therefore, its succe™ moved up‘ moved down and deleted. @) a Cg) KadaAd DaedeD . Delete “7” the node contains less than minimum number of keys required. The sibling can spare a key. So f moves up and ‘s’ moves down. yO) Delete “@”, Again node is less that minimal required. This leaves the parent with only one key. I ts sibling cannot contribute, therefore, f, j, mand t are combined to form the new ot -radus Royall) | wall delete me SfTTNN B-TREE OF ORDER 5 Let us build a B-tree of order 5 for following data : 1 hgat Dp 2 HKZ are simple inserted in the same node D H K Z .ek. child Nede if All te frat of doveds rant. Gxts vel DATA STRUCTURES THROUGH C 435 3, Add B : node is full so it must split H is median for BDHKZ His made as the parent. Since the splitting is at root node we must make one node. ’ 4. P,Q, E, A are simply inserted in ps Good S to be added at K P.QZ Q becomes the median G+) o Geo ” ; Wand T are simply inserted after Q 6 ply 7 After adding C we get@ ° L,Nare simply inserted Cud GD) GD Eup GrwD 2 Y to be added in S T W Z since W is median Cao CS CD) GND ED M to put in K LN P &is median. Then, it will be promoted to CHQW but that is also full therefore this root will be split and new root will be created : Seo : aw Con) Bede GD GDGD (8.12 B+-TREE One of the popular techniques for implementing indexed sequential organisation is to use a variation on the basic known as B*-tree. In B” tree all the leaves have been connected to form a linked list of the keys in sequential the sequence set is the linked leaves are an excellent aspect of B* tree; the keys ean be accessed wiry tly both directly and sequentially. cessed efficiently bo! BY tree is used to provide indexed sequential file organi ation, the key values in the sequence set are the key values in the record collection, the key values in the index Part exist solely for internal purposes of directing access to the sequence set.DATA STRUCTURES THROUGH C a4] :C/C++ ond Garbage Collection Many garbage collection systems rely on compiler support to help the pare when a pointer goes out of scope, so the object the pointer points to can ned However, most C and C++ compilers don’t support garbage collection. There are sev: packages that’ support garbage collection for C and C++. This garbage collector is designed to be a replacement for malloc in C and new in C+. a 1 13.2 GARBAGE COLLECTION In computer science, garbage collection (GC) is a form of automatic memory management. ‘The garbage collector, or just collector, attempts to reclaim garbage, or memory used by objects that are no longer in use by the application. Garbage collection was invented by John McCarthy around 1959 to solve the problems of manual memory management in Lisp. Garbage collection is often portrayed as the opposite of manual memo management, which requires the programmer to specify which objects to deallocate and oeten ean return to the memorygystem. However, many systems use a combination of the two a oTher techniques being studied (such as region inference) to solve tre en eee aE ian same fundamental ‘The basic principles of garbage collection are : 41, Find data objects in a program that cannot be accessed in the future 2. Reclaim the resources used by those objects By making manual memory deallocation unnecessary (and often forbidding it), garbage collection frees the programmer from having to worry about releasing objects that are Es longer needed, which can otherwise consume a significant amount of design effort. It also aids programmers in their efforts to make programs more stable, because it prevents several classes of runtime errors. For example, it prevents dangling pointer errors, where a reference toa deallocated object is used. (The pointer still points to the location in memory where the object or data was, even though the object or data has since been deleted and the memory may now be used for other purposes, creating a dangling pointer. This can, and often does, lead to storage violation errors that are extremely difficult to detact.) Many computer languages require garbage collection, either as part of the language Specification (eg, Java, C# and most scripting languages) or effectively for practical implementation (e.g.. formal languages like lambda calculus); these are said to be garbage collected languages. Other languages were designed for use with manual memory management, but have garbage collected implementations available (e.g, C, C+#). Some languages, like Ada, Modula-3, and C+/CLI allow both garbage collection and manuel ‘memory management to co-exist in the same application by using separate heaps for collected and manually managed objects ; others, like D, are garbage collected but allow the user to manually delete objects and also entirely disable garbage collection when speed is required. In any case, it is far easier to implement garbage collection.as part of the Janguage’s compiler and runtime system, but post loc GC systems exist, including ones that do not require recompilation. The garbage collector will almost always be closely integrated with the memory allocator. , Benefits Garbage collection frees the programmer from manually dealing with memory allocation and eallocation. As a'result, certain categories of bugs are eliminated or substantially reduced: % Dangling pointer bugs, which occur when a piece of memory is freed while there are still pointers to it, and one of those pointers is used. © Double free bugs, which occur when the program attempts to free that is already free. % Certain kinds of memory leaks, in which a program fails to free memory that is nO | longer referenced by any variable, leading, over time, to memory exhaustion. Researchers draw a distinction between “physical” and “logical” memory leaks. Ina physical arpa, leak, the last pointer to a region of allocated memory is removed, but the memory is freed: In a logical memory leak, a region of memory is still referenced by a pointer, but is ‘ a region of memoryA ae 592 (0 11.4 HASHING tng involves storing information ina table and the, ipm in data processing | me jer a database of driv, Avery common paradigm a ae there, For example, cons a : sued ers later retrieving the information s for each driver's license issued. Given Se tains one recor i Zconse records, The database contains one Tee ad eae ea Hee rm m wwe can look up the information associa ed with that numb icense number, we ¢a er. the C++ compiler. The co! jiler_ uses_a symbol table to keep fi . As it compil ram, the compil Jefined symbols in 2 CH program. Asi comple » Pres ny the compe : i; i jared, ition, a 7 sie ynibol table every time a new symbol is ee are ot Ina or sey inserts an ent y : reaps ‘tat used, the compiler looks up the attributes aes with sty ol to see time asym sed, ; os ’ math is being used correctly and to guide the generation of the ex driv Similar operations are done by i - irs. Information is retrieved i f key-and-value pairs. In f ically the database comprises a collection o! : : rs database by searching for a given key. In the case of the driver's ence database, the key is the driver's license number and in the case of the symbol table, the key is the name of the symbol. In general, an application may perform a large number of insertion and/or look-up operations, Occasionally itis also necessary to remove items from the database. Because 2 large number of operations will be done we want to do them as quickly as possible. 11.4.1 Hash Tables Der. A nary in which keys are mapped to array positions by hash FS} _iunctions. In tree tables, the search for an identifier key is carried out via a sequence of comparisons. Hash 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 th i This address will be referred to as the hash or home address of X. address will be referred to as the hash The memory available to maintain the symbol table is assumed to be sequenti igreferred to as the hash table, HT. The term bucket denotes a unit of stora one or more records. A bucket is typi smaller or larger than a disk block. 1. This memory If the number of buckets in a Hash table HT is b, then the buckets are designated HT(0), .. HT(b-1). Each bucket is capable of holding one or more records, The number of records a bucket can store is known as its slot-size. Thus, a bucket is said to consist of s slots, if it can hold s number of records in it. A function that is a record in the hash table, is known as has! A function that js used to compute the addross o| the hash table, is known as hash funciion. Usually s = 1 and in this case each re bucket can hold exactly 1 re d. A hashin; ; . ead exactly 1 record. A % function, f(X) is used to perform an identifier transformation on X. f(X) maps the set of possible identifiers (ic,, X) onto the integers 0 through b-1, giving the bucket number where this identifier will eventually be stored.

DS Complete Unit 5

Uploaded by

Copyright:

Available Formats

DS Complete Unit 5

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS Complete Unit 5

Uploaded by

Copyright:

Available Formats

You might also like