Sorting Algorithms Notes | EduRev

Created by: Parul Joshi

: Sorting Algorithms Notes | EduRev

 Page 1


1
Data Structures/ Algorithms and
Generic Programming
Sorting Algorithms
Today
?Sorting
?Bubble Sort
?Insertion Sort
?Shell Sort
Comparison Based Sorting
?Input – 2,3,1,15,11,23,1
?Output – 1,1,2,3,11,15,23
?Class ‘Animals’
? Sort Objects – Rabbit, Cat, Rat ??
? Class must specify how to compare Objects
? ‘<‘ and ‘>’ operators
Sorting Definitions
? In place sorting
?Sorting of a data structure does not require any external
data structure for storing the intermediate steps
? External sorting
?Sorting of records not present in memory
? Stable sorting
?If the same element is present multiple times, then they
retain the original positions
STL Sorting
?sort function template
?void sort (iterator begin, iterator end)
?void sort (iterator begin, iterator end,
Comparator cmp)
Bubble Sort
?Simple and uncomplicated
?Compare neighboring elements
?Swap if out of order
?Two nested loops
?O(N
2
)
Page 2


1
Data Structures/ Algorithms and
Generic Programming
Sorting Algorithms
Today
?Sorting
?Bubble Sort
?Insertion Sort
?Shell Sort
Comparison Based Sorting
?Input – 2,3,1,15,11,23,1
?Output – 1,1,2,3,11,15,23
?Class ‘Animals’
? Sort Objects – Rabbit, Cat, Rat ??
? Class must specify how to compare Objects
? ‘<‘ and ‘>’ operators
Sorting Definitions
? In place sorting
?Sorting of a data structure does not require any external
data structure for storing the intermediate steps
? External sorting
?Sorting of records not present in memory
? Stable sorting
?If the same element is present multiple times, then they
retain the original positions
STL Sorting
?sort function template
?void sort (iterator begin, iterator end)
?void sort (iterator begin, iterator end,
Comparator cmp)
Bubble Sort
?Simple and uncomplicated
?Compare neighboring elements
?Swap if out of order
?Two nested loops
?O(N
2
)
2
Bubble Sort
for (i=0; i<n-1; i++) {
for (j=0; j<n-1-i; j++)
 /* compare the two neighbors */
if (a[j+1] < a[j]) {
 /* swap a[j] and a[j+1] */
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
http://www.ee.unb.ca/brp/lib/java/bubblesort/
Insertion Sort
?O(N
2
) sort
?N-1 passes
?After pass p all elements from 0 to p  are sorted
?Following step inserts the next element in
correct position within the sorted part
Insertion Sort Insertion Sort …
Insertion Sort - Analysis
?Pass p involves at most p comparisons
?Total comparisons:
?          = O(N²)
i = 2
? i
N
Insertion Sort - Analysis
?Worst Case ?
? Reverse sorted list
? Max possible number of comparisons
? O(N²)
?Best Case ?
? Sorted input
? 1 comparison in each pass
? O(N)
Page 3


1
Data Structures/ Algorithms and
Generic Programming
Sorting Algorithms
Today
?Sorting
?Bubble Sort
?Insertion Sort
?Shell Sort
Comparison Based Sorting
?Input – 2,3,1,15,11,23,1
?Output – 1,1,2,3,11,15,23
?Class ‘Animals’
? Sort Objects – Rabbit, Cat, Rat ??
? Class must specify how to compare Objects
? ‘<‘ and ‘>’ operators
Sorting Definitions
? In place sorting
?Sorting of a data structure does not require any external
data structure for storing the intermediate steps
? External sorting
?Sorting of records not present in memory
? Stable sorting
?If the same element is present multiple times, then they
retain the original positions
STL Sorting
?sort function template
?void sort (iterator begin, iterator end)
?void sort (iterator begin, iterator end,
Comparator cmp)
Bubble Sort
?Simple and uncomplicated
?Compare neighboring elements
?Swap if out of order
?Two nested loops
?O(N
2
)
2
Bubble Sort
for (i=0; i<n-1; i++) {
for (j=0; j<n-1-i; j++)
 /* compare the two neighbors */
if (a[j+1] < a[j]) {
 /* swap a[j] and a[j+1] */
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
http://www.ee.unb.ca/brp/lib/java/bubblesort/
Insertion Sort
?O(N
2
) sort
?N-1 passes
?After pass p all elements from 0 to p  are sorted
?Following step inserts the next element in
correct position within the sorted part
Insertion Sort Insertion Sort …
Insertion Sort - Analysis
?Pass p involves at most p comparisons
?Total comparisons:
?          = O(N²)
i = 2
? i
N
Insertion Sort - Analysis
?Worst Case ?
? Reverse sorted list
? Max possible number of comparisons
? O(N²)
?Best Case ?
? Sorted input
? 1 comparison in each pass
? O(N)
3
Lower Bound on ‘Simple’ Sorting
? Inversions
?An ordered pair (i, j) such that i<j but a[i] > a[j]
?34,8,64,51,32,21
?(34,8), (34,32), (34,21), (64,51) …
? Once an array has no inversions it is sorted
? So sorting bounds depend on ‘average’ number of
inversions performed
Theorem 1
? Average number of inversions in an array of N
distinct elements is N(N-1)/4
? List L, Reverse list L
1
? All possible number of pairs is
? N(N-1)/2
? Average = N(N-1)/4
2
)
N
(
Theorem 2
?Any algorithm that sorts by exchanging
adjacent elements requires O(N²) average
time
?Average number of inversions = O(N
2
)
?Number of swaps required  = O(N
2
)
Tighter Bound
?O( N log N )
?Optimal bound for comparison based sorting
algorithms
?Achieved by Quick Sort, Merge Sort, and Heap
Sort
Shell Sort
? Also referred to as Diminishing Increment Sort
? Incrementing sequence – h
1
, h
2
,..h
k
? h
1
 = 1
? After a phase using h
k
, for each i, a[i] <= a[i+h
k
]
? In other words – all elements spaced h
k
 apart
are sorted
? Start with h = ?N/2?; keep reducing by half in
each iteration
Shell Sort
Page 4


1
Data Structures/ Algorithms and
Generic Programming
Sorting Algorithms
Today
?Sorting
?Bubble Sort
?Insertion Sort
?Shell Sort
Comparison Based Sorting
?Input – 2,3,1,15,11,23,1
?Output – 1,1,2,3,11,15,23
?Class ‘Animals’
? Sort Objects – Rabbit, Cat, Rat ??
? Class must specify how to compare Objects
? ‘<‘ and ‘>’ operators
Sorting Definitions
? In place sorting
?Sorting of a data structure does not require any external
data structure for storing the intermediate steps
? External sorting
?Sorting of records not present in memory
? Stable sorting
?If the same element is present multiple times, then they
retain the original positions
STL Sorting
?sort function template
?void sort (iterator begin, iterator end)
?void sort (iterator begin, iterator end,
Comparator cmp)
Bubble Sort
?Simple and uncomplicated
?Compare neighboring elements
?Swap if out of order
?Two nested loops
?O(N
2
)
2
Bubble Sort
for (i=0; i<n-1; i++) {
for (j=0; j<n-1-i; j++)
 /* compare the two neighbors */
if (a[j+1] < a[j]) {
 /* swap a[j] and a[j+1] */
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
http://www.ee.unb.ca/brp/lib/java/bubblesort/
Insertion Sort
?O(N
2
) sort
?N-1 passes
?After pass p all elements from 0 to p  are sorted
?Following step inserts the next element in
correct position within the sorted part
Insertion Sort Insertion Sort …
Insertion Sort - Analysis
?Pass p involves at most p comparisons
?Total comparisons:
?          = O(N²)
i = 2
? i
N
Insertion Sort - Analysis
?Worst Case ?
? Reverse sorted list
? Max possible number of comparisons
? O(N²)
?Best Case ?
? Sorted input
? 1 comparison in each pass
? O(N)
3
Lower Bound on ‘Simple’ Sorting
? Inversions
?An ordered pair (i, j) such that i<j but a[i] > a[j]
?34,8,64,51,32,21
?(34,8), (34,32), (34,21), (64,51) …
? Once an array has no inversions it is sorted
? So sorting bounds depend on ‘average’ number of
inversions performed
Theorem 1
? Average number of inversions in an array of N
distinct elements is N(N-1)/4
? List L, Reverse list L
1
? All possible number of pairs is
? N(N-1)/2
? Average = N(N-1)/4
2
)
N
(
Theorem 2
?Any algorithm that sorts by exchanging
adjacent elements requires O(N²) average
time
?Average number of inversions = O(N
2
)
?Number of swaps required  = O(N
2
)
Tighter Bound
?O( N log N )
?Optimal bound for comparison based sorting
algorithms
?Achieved by Quick Sort, Merge Sort, and Heap
Sort
Shell Sort
? Also referred to as Diminishing Increment Sort
? Incrementing sequence – h
1
, h
2
,..h
k
? h
1
 = 1
? After a phase using h
k
, for each i, a[i] <= a[i+h
k
]
? In other words – all elements spaced h
k
 apart
are sorted
? Start with h = ?N/2?; keep reducing by half in
each iteration
Shell Sort
4
Shell Sort Shell Sort - Analysis
?Each pass (h
k
) is O(h
k
(N/h
k
)
2
)
?h = 1, 2, 4,…N/2
?Total sums to O(N
2
)?1/h
k
??1/h
k
 = 2
?So ..O(N
2
)
Brain Tweezer
int n, k = 20;
for(n = 0; n < k; n--)
printf(“X”);
Change, remove, add ONLY one character
anywhere to make this code print X 20 times (give
or take a few)
Done
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!