SORTING:

COMPARISON BASED SORTING ALGORITHM

BUBBLE SORT
INSERTION SORT
SELECTION SORT
QUICK SORT
MERGE SORT
HEAP SORT
NON-COMPARISON(LINEAR) SORTING ALGORITHMS
RADIX SORT
 SORTING
• Sorting means arranging the elements of a list
in a certain order(either ascending or
descending)
• That is, 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].
Example: int A[] = {21, 34, 11, 9, 1, 0, 22};
sorted array (ascending order)
A[] = {0, 1, 9, 11, 21, 22, 34;
Sorting Algorithm
• Sorting algorithms is a set of instructions
that take an array or list as an input and
arrange the items into a particular order.
• Ascending order (A-Z, 0-9)
• Descending order (Z-A, 9-0)
• Lexicographical order (dictionary order )
Why sorting algorithms are
important?
• Sorting can significantly reduce the
complexity of a problem.
• Sorting algorithms have direct applications
in
• Searching algorithms
• Database algorithms
• Divide and conquer methods and many
more..
Classification of sorting algorithms
1. Based on number of comparisons:
• Comparison based sorting algorithms : Elements are
compared with each other to find the sorted order.
• Best case complexity O(nlogn)
• Worst case complexity: O(n2)
• Examples: Bubble sort, Insertion sort, Selection sort,
heap sort, merge sort, quick sort.

• Non-Comparison(linear) sorting algorithms: Impose

few restrictions on the inputs to improve the
complexity.
• Examples: Counting sort, Bucket sort, Radix Sort.
Classification of sorting algorithms
2. Based on number of swaps (inversions): This is
the number of times the algorithm swaps
elements to sort the input. Selection
Sort requires the minimum number of swaps.
3. Based on extra memory usage(in-place or out
place): Sorting algorithms are said to be in
place if they require a constant O(1) extra space
for sorting. Insertion, quick sort
Out place : Which requires extra memory space
for it’s operations. Example: Merge sort
Classification of sorting algorithms
4. Based on Recursion or Non-Recursion:
• Some sorting algorithms, such as Quick Sort,
use recursive techniques to sort the input.
• Other sorting algorithms, such as Selection
Sort or Insertion Sort, use non-recursive
techniques.
• Finally, some sorting algorithm, such as Merge
Sort, make use of both recursive as well as non-
recursive techniques to sort the input.
Classification of sorting algorithms
5. Based on Stability:
• Sorting algorithms are said to be stable if the
algorithm maintains the relative order of elements
with equal keys.
• Means, two equivalent elements remain in the
same order in the sorted output as they were in
the input.
• Insertion sort, Merge Sort, and Bubble Sort are
stable
• Heap Sort, selection sort and Quick Sort are not
stable
Classification of sorting algorithms
6. Based on Adaptability:
• A sorting algorithm that can take advantage of
existing order in the input.
• If the time taken by a sorting algorithm is same
over sorted and unsorted list of elements ,
then that sorting algorithm is said to be non-
adaptive.
• All the sorting algorithms except Bubble sort,
Insertion sort are non-adaptive.
Quick recap…
• In applications where the cost of swapping
items is high, which sorting should be used?
selection sort
• Input data is small and nearly sorted.
Insertion sort, as it adapts to the data
• For array and for linked-list
Quick sort for arrays, merge-sort for linked list
• When the smallest or highest value is needed
instantly
Heap sort (In priority queue)
Why stability is important
Why stability is important

Stability effect
 Why stability is important
Sort by Name then Sort by Department
Name Department 1. Sort by Name
Name Department
Janak Telecommunications
Aditya Electronics
Raj CSE
Divya CSE
Aditya Electronics
Huma Telecommunications
Huma Telecommunications
Janak Telecommunications
Divya CSE
Raj CSE

2. Sort by Department (unstable) 2. Sort by department (stable)

Name Department Name Department
Raj CSE Divya CSE
Divya CSE Raj CSE
Aditya Electronics Aditya Electronics
Huma Telecommunications
Janak Telecommunications
Janak Telecommunications
Huma Telecommunications
 The ideal sorting algorithm
• Stable: Equal keys aren’t reordered.
• Operates in place, requiring O(1) extra space.
• Worst-case O(n·lg(n)) key comparisons.
• Worst-case O(n) swaps.
• Adaptive: Speeds up to O(n) when data is
nearly sorted or when there are few unique
keys.
There is no algorithm that has all of these properties,
and so the choice of sorting algorithm depends on the
application.
 Sorting algorithms for Array
and Linked List
• The list of records can be either stored in a
contiguous and randomly accessible data
structure (array) or may be stored in a
dispersed and only sequentially accessible data
structure like a linked list.
• But irrespective of the underlying data
structure used to store the records, the logic to
sort the records will be same and only the
implementation details will differ.
BUBBLE SORT
 Bubble Sort: A[] = {30, 52, 29, 87, 63, 27, 19, 54}
PASS 1:
1. Compare 30 and 52. Since 30 < 52, no swap
2. Compare 52 and 29. Since 52 > 29, swap.
30, 29, 52, 87, 63, 27, 19, 54
3. Compare 52 and 87. Since 52 < 87, no swap
4. Compare 87 and 63. Since 87 > 63, swap
30, 29, 52, 63, 87, 27, 19, 54
5. Compare 87 and 27. Since 87 > 27, swap
30, 29, 52, 63, 27, 87, 19, 54
6. Compare 87 and 19. Since 87 > 19, swap
30, 29, 52, 63, 27, 19, 87, 54
7. Compare 87 and 54. Since 87 > 54, swap
30, 29, 52, 63, 27, 19, 54, 87
 Outcome after first pass?
If the elements are to be sorted in ascending order

• At the end of the first pass, the largest element

in the list will be placed at its proper position
(i.e., at the end of the list)
If the elements are to be sorted in descending
order
• Smallest element is moved to the highest
index of the array
PASS -2: { 30, 29, 52, 63, 27, 19, 54, 87}

1. Compare 30 and 29. Since 30 > 29, swap

29, 30, 52, 63, 27, 19, 54,87
2. Compare 30 and 52. Since 30 < 52, no swap
3. Compare 52 and 63. Since 52 < 63, no swap
4. Compare 63 and 27. Since 63 > 27, swap
29, 30, 52, 27, 63, 19, 54, 87
5. Compare 63 and 19. Since 63 > 19, swap
29, 30, 52, 27, 19, 63, 54, 87
6. Compare 63 and 54. Since 63 > 54, swap
29, 30, 52, 27, 19, 54, 63, 87
Bubble Sort Algorithm
Time Complexity
• Best case : O(n2)
• Average case : O(n2)
• Worst case : O(n2)
 Bubble Sort
• Bubble sort is a sorting technique that sorts the array
elements by repeatedly moving the largest element
to the highest index position of the array segment
• In bubble sorting, consecutive adjacent pairs of
elements in the array are compared with each other.
• If the element at the lower index is greater than the
element at the higher index, the two elements are
interchanged so that the element is placed before the
bigger one.
• This process will continue till the list of unsorted
elements exhausts
Is bubble sort an adaptive
sorting?
• No, by nature, bubble sort is not
adaptive.
• However, we can make it adaptive.
How?
• If the list is already sorted, modify the
bubble sort having time complexity of
O(n).
Is bubble sort an adaptive sorting?
No, by nature, bubble sort is not adaptive.
However, we can make it adaptive by
introducing flag variable.