Algorithms for Sorting and Searching

Binary search

Binary search
What does it mean for one element to be less than another?

Binary search
What does mean sorting?
Sorting means: to put into some well-defined order.

Binary search
Binary search requires the array being searched to be already sorted.

Binary search
Binary search has the advantage that it takes only O(lgn) time to search an n-element array.

Binary search
The books on the bookshelf already sorted by author name.
The position of the book is named a slot.
The key is the author name.

Binary search

Binary search

Binary search
The running time of binary search is O(lgn).
! The array is already sorted.

Selection sort
Remind: Each element is less than or equals to its following element in the array.

Selection sort
Selection sort => on an array of six elements

Selection sort
What is the running time of SELECTION-SORT?

Selection sort
The total number of inner-loop iterations is (n-1)+(n-2)+(n-3)+…+2+1

Selection sort
n+(n-1)+(n-2)+(n-3)+…+2+1=
=n(n+1)/2
It is sum of arithmetic series.
(n-1)+(n-2)+(n-3)+…+2+1=
=n(n-1)/2=(n2-n)/2

Insertion sort

Insertion sort

Insertion sort
Insertion sort => on an array of six elements

Insertion sort
What do we say about the running time of INSERTION-SORT?

Merge sort
The running times of
selection sort and insertion sort are Θ(n2) .
The running time of merge sort is Θ(nlgn) .
Θ(nlgn) better because lgn grows more
slowly than n.

Merge sort
Disadvantages:
The constant factor in the asymptotic notation is higher than for the other two algorithms.
If the array size n is not large, merge sort isn’t used.
2. Merge sort has to make complete copies of
all input array.
If the computer memory is important,
merge sort isn’t used also.

Merge sort
Divide-and-conquer algorithm
Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer. The subproblems solve recursively. If they are small, than the subproblems solve as base cases.
Combine the solutions to the subproblems into the solution for the original problem.

Merge sort
Divide all index (slot) of books in two part. The center of index’s books is q equals (p + r)/2.
Conquer. We recursively sort the books in each of the two subproblems: [p;q] and [q+1;r].
Combine by merging the sorted books.
Divide-and-conquer algorithm for example with bookshelf

Merge sort

Merge sort
The initial call is MERGE-SORT (A, 1, 10).
Step 2A computes q to be 5,
in steps 2B and 2C are MERGE-SORT (A, 1, 5)
and MERGE-SORT (A, 6, 10).
After the two recursive calls return, these two subarrays are sorted.

Merge sort
At last, the call MERGE (A, 1, 5, 10) in step 2D
The procedure MERGE is used to merge the sorted subarrays into the single sorted subarray.

Merge sort
Let’s look at just the part of the bookshelf from slot 9 through slot 14.
We have sorted the books in slots 9–11 and that we have sorted the books in slots 12–14.

Merge sort
We take out the books in slots 9–11 and make a stack of them, with the book whose author is alphabetically first on top,
and we do the same with the books in slots 12–14.

Merge sort
Because the two stacks are already sorted, the book that should go back into slot 9 must be one of the books atop its stack.
We see that the book by Dickens comes before the book by Flaubert, and so we move it into slot 9.

Merge sort
Into slot 10 must be the book still atop the first stack, by Flaubert, or the book now atop the second stack, by Jack London. We move the Flaubert book into slot 10.

Merge sort

Merge sort

Merge sort
Let’s say that sorting a subarray of n elements takes time T(n).
The time T(n) comes from the three components of the divide-and-conquer algorithm:
Dividing takes constant time, because it amounts to just computing the index q.
Conquering consists of the two recursive calls on subarrays, each with n/2 elements. It is time T(n/2).
Combining the results of the two recursive calls by merging the sorted subarrays takes Θ(n) time.
T(n)=T(n/2)+T(n/2)+Θ(n)=2T(n/2)+Θ(n) => T(n)= Θ(nlgn)

Quick sort
Quicksort uses the divide-and-conquer paradigm and uses recursion.
There are some differences from merge sort:
Quicksort works in place.
Quicksort’s worst-case running time is Θ(n2) but its average-case running time is better: Θ(nlg n).
Quicksort is often a good sorting algorithm to use in practice.

Quick sort
Divide by first choosing any one book that is in slots p through r. Call this book the pivot.
Rebuild the books on the shelf so that all other books with author names that come before the pivot’s author are to the left of the pivot, and all books with author names that come after the pivot’s author are to the right of the pivot.
The books to the left of the book by London are in no particular order, and the same is true for the books to the right.
Conquer by recursively sorting the books to the left of the pivot and to the right of the pivot.
Combine – by doing nothing!

Quick sort

Quick sort
The procedure PARTITION (A, p, r) that partitions the subarray A[p; r], returning the index q where it has placed the pivot.

Quick sort

Quick sort

Quick sort
In better case quicksort has the running time Θ(nlgn).
In the worst case quicksort has the running time Θ(n2).

Recap