DATA STRUCTURES AND
ALGORITHM
CHAPTER THREE
SIMPLE SORTING AND
SEARCHING ALGORITHMS
3.1. SORTING
INTRODUCTION - SORTING
• Sorting refers to arranging data in a particular format.
• Sorting algorithm specifies the way to arrange data in a
particular order.
• Most common orders are in numerical or lexicographical
order.
•• Sort:
The importance of into
arrange values sorting lies in the fact that data
an order
searching can be optimized to a very high level, if data is
• Alphabetical
stored in a sorted manner.
• Ascending (smallest to largest) numeric
• Descending (largest to smallest) numeric
Cont.…
• Sorting is also used to represent data in more readable
formats.
• Following are some of the examples of sorting in real-life
scenarios −
• Telephone Directory − The telephone directory stores
the telephone numbers of people sorted by their names,
so that the names can be searched easily.
• Dictionary − The dictionary stores words in an
alphabetical order so that searching of any word
becomes easy.
Cont.…
• The values stored in an array have keys of a type for
which the relational operators are defined. (We also
assume unique keys.)
• Sorting rearranges the elements into either ascending
or descending order within the array. (We’ll use
ascending order.)
4
SOME SORTING ALGORITHMS
• There are so many sorting algorithms like:
• Bubble sort
• Insertion Sort
• Selection Sort
• Merge Sort
• Quick Sort
Cont.…
BUBBLE SORT ALGORITHM
• Bubble sort is a simple sorting algorithm.
• This sorting algorithm is comparison-based algorithm in
which each pair of adjacent elements is compared and the
elements are swapped if they are not in order.
• This algorithm is not suitable for large data sets as its
average and worst case complexity are of Ο(n2) where n is
the number of items.
Cont.…
BUBBLE SORT ALGORITHM
1. Compare 1st two elements and exchange them if
they are out of order.
2. Move down one element and compare 2nd and 3rd
elements. Exchange if necessary. Continue until
the end of the array.
3. Pass through the array again, repeating the
process and exchanging as necessary.
4. Repeat until a pass is made with no exchanges.
Cont.…
BUBBLE SORT EXAMPLE
Array numlist3 contains
17 23 5 11
First, compare values 17 Finally, compare values
and 23. In correct order, 23 and 11. Not in correct
so no exchange. order, so exchange them.
Then, compare values
23 and 5. Not in correct
order, so exchange them.
Cont.…
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
INSERTION SORT
• This is an in-place comparison-based sorting algorithm.
• Here, a sub-list is maintained which is always sorted.
• For example, the lower part of an array is maintained to be
sorted.
• An element which is to be 'inserted’ in this sorted sub-list,
has to find its appropriate place and then it has to be
inserted there.
• Hence the name, insertion sort.
Cont.…
INSERTION SORT
• The array is searched sequentially and unsorted items are
moved and inserted into the sorted sub-list (in the same
array).
• This algorithm is not suitable for large data sets as its
average and worst case complexity are of Ο(n2), where n is
the number of items.
Cont.…
INSERTION SORT - ALGORITHM
Step 1 : If it is the first element, it is already sorted. return 1;
Step 2 : Pick next element
Step 3 : Compare with all elements in the sorted sub-list
Step 4 : Shift all the elements in the sorted sub-list that is
greater than the
value to be sorted
Step 5 : Insert the value
Step 6 : Repeat until list is sorted
SELECTION SORT
• Selection sort is a simple sorting algorithm.
• This sorting algorithm is an in-place comparison-based
algorithm in which the list is divided into two parts, the
sorted part at the left end and the unsorted part at the right
end.
• Initially, the sorted part is empty and the unsorted part is the
entire list.
Cont.…
SELECTION SORT
• The smallest element is selected from the unsorted array and
swapped with the leftmost element, and that element
becomes a part of the sorted array.
• This process continues moving unsorted array boundary by
one element to the right.
• This algorithm is not suitable for large data sets as its
average and worst case complexities are of Ο(n2), where n is
the number of items.
Cont.…
SELECTION SORT - ALGORITHM
Step 1 : Set MIN to location 0
Step 2 : Search the minimum element in the list
Step 3 : Swap with value at location MIN
Step 4 : Increment MIN to point to next element
Step 5 : Repeat until list is sorted
MERGE SORT ALGORITHM
• Merge sort is a sorting technique based on divide and
conquer technique.
• With worst-case time complexity being Ο(n log n), it is one of
the most respected algorithms.
• Merge sort first divides the array into equal halves and then
combines them in a sorted manner.
Cont.…
MERGE SORT ALGORITHM
• Merge sort keeps on dividing the list into equal halves until it
can no more be divided.
• By definition, if it is only one element in the list, it is sorted.
• Then, merge sort combines the smaller sorted lists keeping
the new list sorted too.
Cont.…
MERGE SORT ALGORITHM
• Step 1 : if it is only one element in the list it is already
sorted, return.
• Step 2 : divide the list recursively into two halves until it
can no more be
divided.
• Step 3 : merge the smaller lists into new list in sorted
order.
QUICK SORT
• Quick sort is a highly efficient sorting algorithm and is based
on partitioning of array of data into smaller arrays.
• A large array is partitioned into two arrays one of which holds
values smaller than the specified value, say pivot, based on
which the partition is made and another array holds values
greater than the pivot value.
Cont.…
QUICK SORT
• Quicksort partitions an array and then calls itself recursively
twice to sort the two resulting subarrays.
• This algorithm is quite efficient for large-sized data sets as its
average and worst-case complexity are O(n2), respectively.
Cont.…
QUICK SORT - ALGORITHM
Step 1 : Choose the highest index value has pivot
Step 2 : Take two variables to point left and right of the list
excluding pivot
Step 3 : left points to the low index
Step 4 : right points to the high
Step 5 : while value at left is less than pivot move right
Step 6 : while value at right is greater than pivot move left
Step 7 : if both step 5 and step 6 does not match swap left
and right
3.2. INTRODUCTION TO SEARCH ALGORITHMS
• Search: to locate a specific item in a list (array,
vector, etc.) of information
• Two algorithms (methods) considered here:
• Linear search (also called Sequential Search)
• Binary search
LINEAR SEARCH
Linear search is a very simple search algorithm. In
this type of search, a sequential search is made
over all items one by one. Every item is checked
and if a match is found then that particular item is
returned, otherwise the search continues till the
end of the data collection.
Cont.…
LINEAR SEARCH EXAMPLE
• Array numlist contains
17 23 5 11 2 29 3
• Searching for the value 11, linear search examines 17, 23,
5, and 11
• Searching for the value 7, linear
search examines 17, 23, 5, 11, 2, 29, and 3
Cont.…
LINEAR SEARCH ADVANTAGE AND DIS-ADVANTAGE
• Advantage
• Easy algorithm to understand and to implement
• Elements in array can be in any order
• Disadvantage
• Inefficient (slow): for array of N elements, it
examines N/2 elements on average for a value that
is found in the array, N elements for a value that is
not in the array
BINARY
SEARCH
Binary search is a fast search algorithm with run-time
complexity of Ο(log n). This search algorithm works on the
principle of divide and conquer. For this algorithm to work
properly, the data collection should be in the sorted form.
Binary search looks for a particular item by comparing the
middle most item of the collection. If a match occurs, then
the index of item is returned.
If the middle item is greater than the item, then the item is
searched in the sub-array to the left of the middle item.
Otherwise, the item is searched for in the sub-array to the
right of the middle item. This process continues on the sub-
array as well until the size of the sub array reduces to zero.
Cont.…
Cont.…
BINARY SEARCH ALGORITHM
1. Divide a sorted array into three sections:
• middle element
• elements on one side of the middle element
• elements on the other side of the middle
element
2. If the middle element is the correct value, done.
Otherwise, go to step 1, using only the half of
the array that may contain the correct value.
3. Continue steps 1 and 2 until either the value is
found or there are no more elements to
examine.
Cont.…
BINARY SEARCH EXAMPLE
• Array numlist2 contains
2 3 5 11 17 23 29
• Searching for the the value 11, binary search
examines 11 and stops
• Searching for the the value 7, binary
search examines 11, 3, 5, and stops
Cont.…
BINARY SEARCH ADVANTAGE AND DIS-ADVANTAGE
• Advantage
• Much more efficient than linear search. For an array of
N elements, it performs at most
log2N comparisons.
• Disadvantage
• Requires that array elements be sorted
End of Chapter Three
Any ?
