Sorting and Searching

SORTING AND
SEARCHING
Searching
• The basic characteristics of any searching algorithm is that
• searching should be efficient,
• it should have less number of computations involved into it,
• as well as the space occupied by such a technique should be less.
• Various searching techniques are:

• Linear search
• Binary search
Linear Search / Sequential Search
• Itis a method for finding a particular value in a list that checks each
element in sequence until the desired element is found or the list is
exhausted.
• The list need not be ordered.
• Linear search is usually very simple to implement, and is practical when

the list has only a few elements, or when performing a single search in
an unordered list.
• If
the search element is not in the array, then it scans the entire array, so
takes time as per the number of elements in the array i.e. n.
Algorithm of Linear Search
1. BEGIN
2. Get input A[n] and X (element to be searched)
3. i0
4. Repeat through step 6 for i < n
5. If A[i] == X
Print “Match found at array index i”
Exit
6. ii+1
7. Print “Match not found”
8. END
Linear Search / Sequential Search
Binary Search
• Procedure binary_search
• A ← sorted array
•n ← size of array
•x ← value to be searched
• Set lowerBound = 1
• Set upperBound = n
• while x not found
• if upperBound < lowerBound
• EXIT: x does not exists.
Contd…
• set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
• if A[midPoint] < x
• set lowerBound = midPoint + 1
• if A[midPoint] >x
• set upperBound = midPoint - 1
• if A[midPoint] =x
• EXIT: x found at location midPoint
• end while
• end procedure
Sorting
• Sorting means arranging the elements of an array so that they are placed
in some relevant order which may be either ascending or descending.
• Thatis, if A is an array, then the elements of A are arranged in a sorted
order (ascending order) in such a way that A[0] < A[1] < A[2] < … < A[N].
• The practical considerations for different sorting techniques would be:
• Number of sort key comparisons that will be performed.
• Number of times the records in the list will be moved.
• Best, average and worst case performance.
• Stability of the sorting algorithm where stability means that equivalent elements or
records retain their relative positions even after sorting is done.
Bubble Sort
• Algorithm
• begin BubbleSort(list)
for all elements of list

if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
Selection Sort
• The algorithm divides the input list into two parts:
• the sublist of items already sorted, which is built up from left to right at the front
(left) of the list,
• and the sublist of items remaining to be sorted that occupy the rest of the list.
• Initially, the sorted sublist is empty and the unsorted sublist is the entire
input list.
• The algorithm proceeds by finding the smallest (or largest, depending on
sorting order) element in the unsorted sublist, exchanging it with the
leftmost unsorted element (putting it in sorted order), and moving the
sublist boundaries one element to the right.
Selection Sort
• Technique:
• Consider an array ARR with N elements. The selection sort takes N-1 passes to sort
the entire array and works as follows. First find the smallest value in the array and
place it in the first position. Then find the second smallest value in the array and
place it in the second position. Repeat this procedure until the entire array is sorted.
Therefore,
• In Pass 1, find the position POS of the smallest value in the array and then swap
ARR[POS] and ARR[0]. Thus, ARR[0] is sorted.
• In Pass 2, find the position POS of the smallest value in sub-array of N-1 elements.
Swap ARR[POS] with ARR[1]. Now, A[0] and A[1] is sorted
• In Pass 3, find the position POS of the smallest value in sub-array of N-2 elements.
Swap ARR[POS] with ARR[2]. Now, ARR[0], ARR[1] and ARR[2] is sorted.
• In Pass N-1, find the position POS of the smaller of the elements ARR[N-2] and
ARR[N-1]. Swap ARR[POS] and ARR[N-2] so that ARR[0], ARR[1], … , ARR[N-1] is
sorted.
Selection Sort
Algorithm of Selection Sort
1. BEGIN
2. Get input A[n]
3. Repeat through step 4 for i = 1 to n-1
4. Repeat for j = i + 1, … , n
5. If A[j] < A[i]
temp = A[i]
A[i] = A[min_index]
A[min_index] = temp
END
6. END
THANK YOU
ANY QUESTIONS???

Sorting and Searching

Uploaded by

Copyright:

Available Formats

Sorting and Searching

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

Sorting and Searching

Uploaded by

Copyright:

Available Formats

SORTING AND

• Various searching techniques are:

• Linear search is usually very simple to implement, and is practical when

for all elements of list

You might also like