Searching and Sorting

Introduction
• Searching and Sorting are fundamental operations in
computer science.
• Searching is the operation of finding the location of a given
item in a collection of items .
• Sorting refers to the operation of arranging data in some
order such as increasing or decreasing with numerical data
or alphabetically with character data.
• Sorting and searching frequently applies to a files of records.
Sorting
• Let A be a list of n elements A1, A2,…,An in memory.
• Sorting A refers to the operation of rearranging the contents of A so
that they are in an order.
• Since A has n elements there are n factorial ways that the contents
can appear in A.
• Sorting may be done using various sorting algorithms
Quick Sort
• Divide and conquer type algorithm
• ie the problem of sorting a set is reduced to a problem of sorting two
smaller sets.
• The reduction step is illustrated with an example:
• Suppose A is a list of 12 numbers : A[1],A[2],A[3],…A[12]
44 33 11 55 77 90 40 60 99 22 88 66
The first step of quicksort algorithm finds the final position of one of
the numbers ,here 44
This is done as follows
Beginning with the last number 66,scan the list from right to left,
comparing each number with 44 and stop at the first number less than
44.
The number is 22.
Interchange 44 and 22 to obtain the list
22 33 11 55 77 90 40 60 99 44 88 66
Now the numbers 88 and 66(to the right) are greater than 44 .
Beginning with 22 next scan the list in the opposite direction ,from left
to right, comparing each number with 44 and stop at the first number
greater than 44.
The number is 55
Interchange 44 and 55 to obtain the list as
22 33 11 44 77 90 40 60 99 55 88 66
Scan the list from right to left, starting from 55 ,compare with 44 and
stop at first number less than 44.
The number is 40
Interchange 44 and 40
22 33 11 40 77 90 44 60 99 55 88 66
Beginning with 40, scan the list from left to right, compare each
number with 44 and stop at the first number greater than 44.
The number is 77.
Interchange 44 and 77
22 33 11 40 44 90 77 60 99 55 88 66.
Scan the list from right to left, starting from 77 ,compare with 44 and
stop at first number less than 44.
There is no such number(all numbers have been scanned and
compared with 44)
All numbers less than 44 form a sublist to the left of 44
All numbers greater than 44 form a sublist to the right of 44
[22 33 11 40] 44 [90 77 60 99 55 88 66].
44 is correctly placed in its final position,A[5].
• The task of sorting the original list is reduced to the tsk of sorting
the two sublists.
• The reduction step is repeated with each sublist containing 2 or
more elements
• To keep track of sublists for future processing two stacks are used
called LOWER and UPPER (to temporarily hold sublists).
• The addresses of the first and last elements of each sublists
called its boundary values are pushed onto the stacks LOWER
and UPPER resp.
• The reduction step is applied to a sublist only after its boundary
values are removed from the stacks.
• Illustration:
• Consider the list A with n=12 elements .
• The algorithm begins by pushing the boundary values 1 and 12 of A onto
the stacks
LOWER=1 UPPER =12
• To apply the reduction step the algorithm first removes the top values 1
and 12 from the stacks leaving them empty.
• After executing the reduction step the new boundary values 1 and 4 of first
sublist and 6 ad 12 of second sublist are pushed to the respective stacks
LOWER=1,6 UPPER=4,12
• To apply the reduction step again the algorithm removes the top values 6
and 12 from the stacks
LOWER=1 UPPER= 4
• Then the algorithm is applied to the second sublist
2nd sublist: A[6] A[7] A[8] A[9] A[10] A[11] A[12]

90 77 60 99 55 88 66

66 77 60 99 55 88 90

66 77 60 90 55 88 99

[66 77 60 88 55] 90 [99]

90 is fixed in the final position, A[11]
• The second sublist has only one [Link] the upper and lower bounds of 1st
sublist is pushed to the stack
LOWER=1,6 UPPER= 4,10
• Now pop 6 and 10 from stack to process the first sublist.
A[6] A[7] A[8] A[9] A[10]
66 77 60 88 55
55 77 60 88 66
55 66 60 88 77
[55 60] 66 [88 77] and so on…
• The algorithm ends when the stacks do not contain any sublists to be
processed by reduction step.
Quick Sort -Algorithm
Complexity of Quick sort
• The running time of a sorting algorithm is measured
by the number of comparisons required to sort n
elements
• The quick sort algorithm has a worst case running
time of the order n2/2
• The average case running time is of order n log n
Selection Sort
• Suppose an array with n elements A[1],A[2],…,A[N] is in
memory.
• The selection sort algorithm works as follows.
• First find the smallest element in the list and put it in the first
position.
• Then find the second smallest element in the list and put it in
the second position . And so on..
Pass 1 : Find the location LOC of the smallest element in the list of N elements
A[1],A[2],……A[N] and then interchange A[LOC] and A[1].
Then A[1] is sorted.
Pass2 : Find the location LOC of the smallest in the sublist of N-1 elements
A[2],A[3],…A[N] and then interchange A[LOC]and A[2].
Then A[1],A[2] is sorted ,since A[1]<=A[2].
Pass 3: Find the location LOC of the smallest in the sublist of N-2 elements
A[3],A[4],…A[N] and then interchange A[LOC] and A[3].
Then A[1],A[2],A[3] is sorted since A[2]<=A[3]
…… ……………………………………………………………………………………………………….
…… ……………………………………………………………………………………………………....
Pass N-1 : Find the location LOC of the smaller of the elements A[N-1],A[N] and then
interchange A[LOC] and A[N-1].Then
A[1,],A[2],…,A[N] is sorted since A[N-1]<=A[N]
Thus A is sorted after N-1 passes.
• To find the smallest among elements A[K],A[K+1],…A[N] during Kth
pass,a variable MIN is used (to hold the current smallest value while
scanning the subarray from A[K] to A[N]
• First set MIN=A[K] and LOC=K and then traverse the list comparing
MIN with each other element A[J] as follows.
a) If MIN<=A[J] ,then simply move to the next element
b) If MIN> A[J],then update MIN and LOC by setting MIN:=A[J] and
LOC=J
After comparing MIN with the last element A[N],MIN will contain the
smallest among the elements
Algorithm –Selection Sort
Complexity of Selection Sort
• The number of comparisons is independent of the original order of
the elements in selection sort.
• Accordingly
the worst case running time is of the order of n2 –O(n2)
the average case running time is of the order n2 –O (n2)
Insertion Sort
• An array A with n elements A[1],A[2],…,A[N] is in memory.
• The insertion sort scans A from A[1] to A[N] inserting each element A[K]
into its proper position in the previously sorted subarray A[1], A[2],…..,A[K-
1] That is
Pass 1: A[1] by itself is trivially sorted.
Pass 2: A[2] is inserted either before or after A[1] so that : A[1],A[2]
is sorted
Pass 3: A[3] is inserted into its proper place in A[1],A[2],that is
before A[1] ,between A[1] and A[2],or after A[2],so that
A[1], A[2],A[3] is sorted.
Pass 4: A[4] is inserted into its proper place in A[1],A[2],A[3],A[4]
is sorted.
… ……………………………………………………………………………………...
Pass N : A[N] is inserted into its proper place in A[1],A[2],…..A[N-1]
so that A[1],A[2],…A[N] is sorted.
• This algorithm is frequently used when n is small.
• It should be decided how to insert A[K] in its proper place in the
sorted subarray A[1],A[2],….,A[K-1].This can be done by comparing
A[K] with A[K-1], comparing A[K] with A[K-2], comparing A[K] with
A[K-3] etc until meeting an element A[J] such that A[J]<=A[K].
• Then each of the elements A[K-1],A[K-2],…A[J+1] is moved forward
one location and A[K] is then inserted in the J+1st position in the
array.
• The algorithm is simplified if there always is an element A[J] such that
A[J]<=A[K].This condition can be accomplished by introducing a
sentinel element A[0]=-∞(or a very small number)
Algorithm –Insertion Sort
Complexity of insertion sort
• Worst case : O(n2)
• Average case : O(n2)
Hashing
• Hashing or hash addressing is a search technique which is
independent of the number of elements to be searched(unlike the
other discussed searching techniques).
• We assume that there is a file F of n records with a set of keys which
uniquely determine the records in F.F is maintained in memory by a
table T of m memory locations and that L is the set of memory
addresses of the locations in T.
• To do hashing we need to know even more about where the items
might be when we go to look for them in the collection. If every item
is where it should be, then the search can use a single comparison to
discover the presence of an item.
• Hashing is a technique to convert a range of key values into a range of
indexes of an array.
• Using a key to determine the address of a record takes the form of a
function H from the set K of keys into the set L of memory addresses.
• Such a function H:K L is called a hash function or hashing
function.
• It is possible that two different keys k1 and k2 will yield the same
hash address. This situation is called collision and some method must
be used to resolve.
• Accordingly hashing is divided into two parts: hash functions and
collision resolutions.
 .

Hash table and Hash functions

• A hash table is a collection of items which are stored in such a way as
to make it easy to find them later. Each position of the hash table,
often called a slot, can hold an item and is named by an integer value
starting at 0.
• For example, we will have a slot named 0, a slot named 1, a slot
named 2, and so on.
• The mapping between an item and the slot where that item belongs
in the hash table is called the hash function
• Two criteria used in selecting a hash function H:K L are ;
1) The function H should be very easy and quick to compute.
2) The function H should uniformly distribute the hash addresses
throughout the set L so that there are a minimum number of
collisions.
Hash functions examples:
1. Division Method:
• Choose a number m larger than the number n of keys in K.(The
number m is chosen to be a prime number since this frequently
minimizes the number of collisions).The hash function H is defined by
H(k)=k (mod m) or H(k)=k (mod m)+1
• K mod m denotes the remainder when k is divided by m.
• The second formula is used when the hash addresses(memory
addresses) ranges from 1 to m rather than 0 to m-1
• Example: A company assigns each of the 68 employees a unique 4 digit emp no.
Suppose L consists of 100 2 digit addresses,00,01,02,…99.
• Emp no:3205,7148,2345
• Choose a prime number m close to 99 such as m=97 .Then
H(3205)=4( remainder when 3205 is divided by 97). 3205 mod 97=4
H(7148)=67(remainder when 7148 is divided by 97). 7148 mod 97=67
H(2345)=17(remainder when 2345 is divided by 97). 2345 mod 97=17
• If the memory address begins with 01 rather than 00 we choose the function
H(k)= k (mod m)+1 to obtain
H(3205)=4+1=5
H(7148)=67+1=68
H(2345)=17+1=18
2. Midsquare method :
• The key k is squared.
• Then the hash function H is defined by H(k) =l where I is obtained by
deleting digits from both ends of k2. (The same positions of k2 must be
used for all keys).
• Example:
k : 3205 7148 2345
k2: 10272025 51093904 5499025
H(k): 72 93 99(4th and 5th digits counting from
the right are chosen as hash address)
3. Folding method :
• The key k is partitioned into a number of parts k1,k2,…kr where each
part except the last has the same number of digits as the required
address
• Then these parts are added together ignoring the last carry.
• ie H(k)=k1+k2+…+kr where the leading digit carries if any is
ignored.(sometimes the even numbered parts are reversed before the
addition)
• Example:
• Folding(Chopping) the key k into two parts and adding yields the
following hash address
• H(3205)=32+05=37
H(7148)=71+48=19(the leading digit 1 is ignored)
H(2345)=23+54=77(reverse the second part)
Collision resolution:
• Suppose we want to add a new record R with key k to our file [Link]
the memory location H(k) is already [Link] situation is called
collision.
• There are different procedures to resolve these collisions which can
be chosen based on a ratio λ=n/m called the load factor.
• [n:[Link] keys or [Link] records in the file ,m : no. of hash addresses or
memory locations ].
• The efficiency of a hash function with collision resolution procedure
is measured by the average number of probes (key comparisons)
needed to find the location of the record with a given key k.
• The efficiency depends on load factor λ.
• S(λ)=average [Link] probes for a successful search
• U(λ)=average [Link] probes for an unsuccessful search.
Open Addressing :Linear Probing and
Modifications
• Suppose a new record R with key k is to be added to the memory table T,
but the memory location with hash address H(k)=h is already filled .
• To resolve this collision assign R to the first available location following
T[h].
• Assume that the table T with m locations is circular so that T[1] comes after
T[m].
• With such a collision procedure we will search for the record R in the table
T by linearly searching the locations T[h] ,T[h+1]T[h+2],… until finding R, or
being unsuccessful.
• This collision resolution is called linear probing.
• The average number of probes for a successful search and for an
unsuccessful search are:
S(λ)=1/2{1+[1/(1- λ)]}
U(λ)=1/2{1+[1/(1- λ)2]}
• One main disadvantage of linear probing is that records tend to
cluster ie appears next to one another when the load factor is greater
than 50 percent .
• Clustering increases the average search time for a record.
• To minimize clustering two techniques are
1) Quadratic probing
2) Double hashing
Quadratic probing:
• Suppose a record R with key k has the hash address H(k)=h.
• Then instead of searching the locations with addresses h,h+1,h+2,…, we
linearly search the locations with addresses
h,h+1,h+4,h+9,h+16,….,h+i2,…
Double Hashing:
• A second hash function H’ is used for resolving a collision.
• Suppose a record R with key k has the hash addresses H(k)=h
and H’(k)=h’≠m.
• Then we linearly search the locations with addresses
h,h+h’,h+2h’,h+3h’,….
Chaining
• Chaining involves maintaining two tables in memory
• There is a table T in memory which contains the records in F except
that T now has an additional field LINK which is used so that all
records in T with the same hash address h may be linked together to
form a linked list
• There is a hash address table LIST which contains pointers to the
linked lists in T
• When a new record R with key k is added to the file F, we place R in
the first available location in the table T and then add R to the linked
list with pointer LIST[H(k)].
• If the linked list of records are not sorted then R is simply inserted at
the beginning of its linked list .
• Searching a record in T is same as searching for a node in the linked
list.
• The average number of probes for successful search and unsuccessful
search are :
S(λ)≈1+1/2 λ
U(λ)≈e– λ+ λ
THANK YOU