[go: up one dir, main page]
Scribd
Upload
17 views47 pages

Unit 5 - Sorting and Hashing

Uploaded by

Ilesh Shah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views47 pages

Unit 5 - Sorting and Hashing

Uploaded by

Ilesh Shah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 47

UNIT 5

Sorting and Hashing


SORTING METHODS SYLLABUS:
 5.1.Sorting Methods
a. Bubble Sort,
b. Selection Sort,
c. Quick Sort,
d. Insertion Sort,
e. Merge Sort,
f. Radix Sort
 5.2.Hashing Concepts
CONTINUE…
 5.3.Hash functions : Division Method, Middle
Square Method, Folding Method
 5.4.Collision in Hashing

 5.5.Collision resolution techniques: Linear


Probing
5.1 SORTING METHOD
 Classification of Sorting method:

 Internal sort:
• Bubble sort
• Quick sort(Partition Exchange sort)
• Selection sort
• Insertion sort
CONTINUE…
o External sort:
• Merge sort
• Radix sort
SORTING DEFINITION
 Sorting refers to ordering data in an increasing
or decreasing fashion according to some linear
relationship among the data items.
 ordering: arranging items in a sequence ordered
by some criterion;
 categorizing: grouping items with similar
properties
A. BUBBLE SORT
 Bubble sort is easy to understand and simple sorting
technique.

 During the first pass element 1 and 2 are compared


and if they are out of order then they are interchanged.
This process is repeated for elements 2 and 3 and so
on.

 After the end of first pass the record with the largest
value is placed at nth(last) position.
CONTINUE...
Bubble_Sort(List,N) Algorithm
Where, List-> Array of N Elements
N-> Size of array(Total No of Elements)

Step:1 [Initialization]
i0

Step:2 while(i<N-1) repeat thru Step 7

Step:3 j0

Step:4 while (j<N-i-1) repeat thru Step 6


CONTINUE….
Step:5 if (List[j] > List[j+1])
(i) tempList[j]
(ii) List[j]List[j+1]
(iii) List[j+1]temp
Step:6 jj+1
Step:7 ii+1
Step :8 [Finished]
Exit.
EXAMPLE…
B.SELECTION SORT

 It starts from first element and searches the


entire array until it find smallest element. Then
smallest value interchanges with the first
element.
 Now select second element and searches for the
second smallest element from the array, if found
then interchange with second element.
 So in this method after pass 1 smallest value
arranged at first position then after pass 2
second minimum will arrange at second position
and so on.
 This process continues until all the elements in
the array are arranged in ascending order.
CONTINUE...
Selection Sort(List,N) Algorithm

Where, List-> Array of N Elements


N-> Size of array(Total No of
Elements)
Step:1 [Initialization]
i0
Step:2 while(i<N-1) repeat thru Step 7
Step:3 ji+1
Step:4 while (j<N) repeat thru Step 6
CONT….
Step:5 if (List[i] > List[j])
(i) tempList[i]
(ii) List[i]List[j]
(iii) List[j]temp

Step:6 jj+1

Step:7 ii+1

Step :8 [Finished]
Exit.
EXAMPLE…
QUICK SORT(PARTITION EXCHANGE SORT)
 We pick the first element from the array and place it in
it’s proper position in the array such that all the
elements preceding the element having smaller value
and all the elements following the element having larger
value.

 Thus the table is divided into two sub tables.

 The same process is then applied to each of the sub


tables and repeated until all records are placed in their
final position.
CONTINUE...
Quick_Sort(K,Start,End) Algorithm:

Where, K -> Array


Start-> Index of First Element
End-> Index of Last Element

Step:1 If Start <End then


iStart
jEnd +1
KeyK[Start]

Step:2 Repeat thru step 3 while I < j


CONT….
Step:3 i i+1
while (K[i] < Key)
i++

jj-1

while (K[j] > Key)


j--

if i< j then
tempK[i]
K[i]K[j]
K[j]temp
CONT….
Step:4 [Place the Key element to its Position]
tempK[j]
K[j]Key
Keytemp

Step:5 Call Quick_Sort(K,Start,j-1)


Call Quick_Sort(K,j+1,End)

Step: 6 [Finished]
Exit.
EXAMPLE..
D.INSERTION SORT
ALGORITHM:
Insertion Sort(a,N)
Where, a -> Array
N-> Total no of elements

Step:1 Read N

Step:2 Repeat thru step 2 for


i=0,1,2,…N-1
Read (a[i])

Step:3 Repeat thru Step 6 for


i=0,1,2,…N-1
CONT….
Step:4 Index  a[i]
j i

Step :5 Repeat while (j>0 and a[j-1]>index)


a[j]a[j-1)
j  j-1

Step :6 a[j] Index

Step :7 [Finished]
Exit.
EXAMPLE…
E.MERGE SORT

 Merge Sort is the process of combining two list into


third list.

Merge Sort(List1,n,List2,m,List)
Where,
List1  First List of n elements
List2  Second List of m elements
List  Merge elements are stored in this list
CONTINUE…
Step:1 [Initialization]
i0
j 0
k 0
Else If ( List1[i] > List2[j]) then
List[k] List2[j]
k k+1
j j+1
Step:2 while ((i<n) and (j<m)) repeat thru step3
CONT….

Step 3:
If ( List1[i] < List2[j]) then
List[k] List1[i]
k k+1
i i+1
CONT….
Else
List[k] List1[i]
k k+1
i  i+1
j  j+1

Step :4 if (i<n)
Repeat for x=i,i+1,…n-1
List[k]  List1[x]
k k+1
CONT….
Step :5 if (j < m)
Repeat for y=j,j+1,…m-1
List[k]  List2[y]
k k+1

Step :6 [Finished]
Exit.
EXAMPLE…
F.RADIX SORT
 We use ten pockets for the digits 0 to 9.
 Consider the following set of data:

42 23 74 11 65 57 94 36 99 87 70 81 61

 During first pass we separate the unit digit of the


number and place the number in to appropriate pocket
according to its unit digit.

 For example the first number is 42 so we separate the


unit digit of the number 42 which is 2 so we place the
number in pocket 2. Same procedure is repeated for
remaining numbers.
CONT….
After first pass the numbers in each pockets are as
follow:
61
81 94 87
70 11 42 23 74 65 36 57 99
Pocket: 0 1 2 3 4 5 6 7 8 9

 Now arrange the number according to their pocket.


The numbers after first pass are as follows:
70 11 81 61 42 23 74 94 65 36 57 87 99
CONT….
 During second pass we separate the next higher digit of
the number and place the number in to appropriate
pocket according to its digit.

After second pass the numbers in each pockets are as


follow:
65 74 87 99
11 23 36 42 57 61 70 81 94
Pocket: 0 1 2 3 4 5 6 7 8 9
CONT….
 Now arrange the number according to their pocket.
The numbers after second pass are as follows:

11 23 36 42 57 61 65 70 74 81 87 94 99

 The same process is repeated until all the elements are


sorted.
EXAMPLE…
5.2 HASHING CONCEPTS
 Hashing provides direct access of records from the file
no matter where the record is in the file.

 This technique uses the hashing function say H


which maps the Key to the particular address of the
record.

 Hashing function provides key to address


transformation.

 A hashing function H maps the Key space K into an


address space.
5.3 HASH FUNCTIONS
Some of the most widely used hashing functions are :

 Division Method
 The Mid square Method

 The Folding Method

 Multiplicative Hashing
DIVISION METHOD
Hashing function defined as:
H(x) = x mod m + 1

For example: H (35) = 35 mod 11 + 1 = 2 + 1 = 3

The Division method generates a key value which


belongs to the set {1, 2… m}
MID SQUARE METHOD
 A key is multiplied by itself and the address is
obtained by selecting an appropriate number of digits
from the middle of the square

 For example: consider a six digit key 123456.

Squaring this key result in the value 5241383936. if a


three digit address is required then position 5 to 7 could
be chosen which gives 138.
THE FOLDING METHOD
 A key is partitioned into parts. The length of each part
is similar to the length of the address required. These
parts are added together and final carry is ignored to
produce the address.

 For example if a key 35678943 is transformed into 2


digit address then we have:
35 + 67 + 89 + 43 = 234 = 34.

 This method is known as fold shifting method.


MULTIPLICATIVE HASHING

H(x)= [m (cx mod 1 + 1)] + 1

Where, x=Key
c= Constant(0<c<1)
m= Hash Table Size
5.4 COLLISION IN HASHING
 When a hashing function maps several keys to same
address space then it is known as collision.

 Example: we are storing the records in an array which


ranges from 0 to 99.if a hashing function is H(k) = k %
100 then this function will produces same address for
the keys 15433 and 26733. in this case collision is
encountered.
5.5 LINEAR PROBING
Collision resolution techniques are :

1. Linear Probing
2. Rehashing
3. Quadratic Probing
4. Random Probing
LINEAR PROBING
 If a record with key x is mapped to address location d
and that location is already occupied by another key
then other locations in the table are examined until a
free memory location is found.

For Example,

 Suppose we have to insert the following key values


with hashing function H(k) = k % 100
 50904, 78907, 68403, 86704, 72308
Index Key
00 Empty
01 Empty
02 Empty
03 68403
04 50904
05 86704
06 Empty
07 78907
08 72308
REHASHING
 If a hash function results in a collision then we use the
secondary hash function to calculate the address.

 In above example the hash function H (k) = k % 100


produces collision for the key 86704 so we use
secondary hash function as: H (k) = (k + constant) %
100.
QUADRATIC PROBING

 Thismethod probes the table at locations


h+1, h+4, h+9…., that is h + i2
RANDOM PROBING
 To use a pseudorandom number generator to obtain
the increment.

 The generator should be generates the same sequence


provided it starts with the same need.

You might also like