Page 88 - DCAP507_SYSTEM_SOFTWARE

System Software Avinash Bhagat, Lovely Professional University

Notes Unit 6: Table Processing: Sorting

CONTENTS

Objectives
Introduction
6.1 Sorting
6.1.1 Classification of Sorting
6.2 Interchange Sort

6.3 Shell Sort
6.4 Bucket Sort
6.5 Radix Exchange Sort

6.6 Summary
6.7 Keywords
6.8 Review Questions
6.9 Further Readings

Objectives

After studying this unit, you will be able to:

 Understand the concept of sorting
 Discuss interchange sort, shell sort, bucket sort, etc.

Introduction

It appears evidently that binary search is more competent than linear search, but such a search
needs an ordered table which may not be simply obtainable. Here you will recognize the
interchange sort, shell sort, bucket sort, etc.

6.1 Sorting

Sorting refers to the operation of arranging data in some given order, such as increasing or
decreasing, with numerical data or alphabetically, with character data.
Let P be a list of n elements P , P , P ...P in memory. Sorting P refers to the operation of
1 2 3 n
rearranging the contents of P so that they are increasing in order (numerically or
lexicographically), that is,

P < P < P ...< P
1 2 3 n
Since P has n elements, there are n! ways that the contents can appear in P. These ways correspond
precisely to the n! permutations of 1, 2, ...n.

!
Caution Accordingly, each sorting algorithm must take care of these n! possibilities.

82 LOVELY PROFESSIONAL UNIVERSITY