Page 238 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting
Mandeep Kaur, Lovely Professional University

Unit 12: Sorting Notes

CONTENTS

Objectives
Introduction
12.1 Internal Sorting
12.2 Insertion Sort
12.2.1 Algorithm of Insertion Sort
12.2.2 Complexity Analysis
12.3 Shell Sort

12.4 Heap Sort
12.5 Merge Sort
12.6 Merging of two Sorted Lists
12.7 Quick Sort
12.8 Bucket Sort
12.9 External Sorting
12.10 Summary
12.11 Keywords
12.12 Self Assessment
12.13 Review Questions
12.14 Further Readings

Objectives

After studying this unit, you will be able to:
z Discuss internal sorting
z Explain heap sort, merge sort and quick sort
z Describe external sorting

z Discuss the implementation of heaps
Introduction

Retrieval of information is made easier when it is stored in some predefined order. Sorting is,
therefore, a very important computer application activity. Many sorting algorithms are available.
Different environments require different sorting methods. Sorting algorithms can be characterised
in the following two ways:

2
1. Simple algorithms which require the order of n (written as O(n ))comparisons to sort n
2
items.
2. Sophisticated algorithms that require the O(nlog n) comparisons to sort n items.
2

LOVELY PROFESSIONAL UNIVERSITY 233