Sorting
Dr.Gireesh Kumar T
Bubble sort
Bubble sort
Selection Sort
Algorithm
Insertion sort
Algorithm
Sequantial search
Binary search
Merge sort
Merge sort
Quick sort
• scan the subarray from both ends,comparing the subarray’s
elements to the pivot.
• The left-to-right scan, denoted below by index pointer i, starts with
the second element. Since we want elements smaller than the pivot
to be in the left part of the subarray, this scan skips over elements
that are smaller than the pivot and stops upon encountering the
first element greater than or equal to the pivot.
• The right-to-left scan, index pointer j, starts with the last element of
the subarray.
• Since we want elements larger than the pivot to be in the right part
of the subarray, this scan skips over elements that are larger than
the pivot and stops on encountering the first element smaller than
or equal to the pivot.
• After both scans stop, three situations may arise, depending
on whether or not the scanning indices have crossed.
• If scanning indices i and j have not crossed, i.e., i < j, we simply
exchange A[i] and A[j ] and resume the scans by incrementing
I and decrementing j, respectively:
• If the scanning indices have crossed over, i.e., i
> j, we will have partitioned the subarray after
exchanging the pivot with A[j ]:
• if the scanning indices stop while pointing to the same
element, i.e., i = j, the value they are pointing to must be
equal to p. Thus, we have the subarray partitioned, with the
split position s = i = j :
• We can combine the last case with the case of crossed-over
indices (i > j ) by exchanging the pivot with A[j ] whenever i ≥ j
.
Quick sort
