Concept of Sorting

Concept of Sorting

• Definition : Sorting is a mechanism in which the data is arranged in increasing or decreasing order.

• There are two types of sorting techniques ‒

o Internal sorting

o External sorting

• Internal sorting : Internal sorting is a technique in which data resides in the memory of the computer.

• External sorting : External sorting is a technique in which data resides in external or secondary storage devices such as hard disk, floppy disk etc. When huge amount of data needs to be sorted then this technique is applied.

1. Sorting Order

• The sorting is a technique by which we expect the list of elements to be arranged as we expect. Sorting order is nothing but the arrangement of the elements in some specific manner. Usually the sorting order is of two types ‒

• Ascending order : It is the sorting order in which the elements are arranged from low value to high value. In other words elements are in increasing order.

For example: 10, 50, 40, 20, 30

can be arranged in ascending order after applying some sorting technique as

10, 20, 30, 40, 50

• Descending order : It is the sorting order in which the elements are arranged from high value to low value. In other words elements are in decreasing order. It is reverse of the ascending order.

For example : 10, 50, 40, 20, 30

can be arranged in descending order after applying some sorting technique as

50, 40, 30, 20, 10

• While sorting the elements, we always consider a specific order and expect our data to be arranged in that order.

2. Sorting Stability

• The sorting stability means comparing the records of same value and expecting them in the same order even after sorting them.

For example:

(Pune, BalGandharva)

(Pune, Shaniwarwada)

(Nasik, Panchavati)

(Mumbai, Gateway‒of‒India)

• Now in the above list, we will sort the list according to the first alphabet of the city. The ascending order for the alphabets P(for Pune), N(for Nasik), M(for Mumbai) will be M, N, P. The sorting stability can be achieved by arranging the records as follows.

(Mumbai, Gateway‒Of‒India)

(Nasik, Panchavati)

(Pune, BalGandharva)

• Note that in the above list same record as Pune is twice. But we have preserved the original sequence as it is after comparing them. Thus the stability is achieved in sorting the records.

3. Efficiency and Passes

• The efficiency of sorting algorithms is denoted in terms of big oh notations.

• Commonly there are O(n²) and O(nlogn) time complexities.

• The sorting techniques such as bubble sort, insertion sort, selection sort, shell sort has the time complexity O(n²) and the techniques such as merge sort, quick sort has the time complexity as O(nlogn). The quick sort is the fastest algorithm and bubble sort is the slowest one

• While sorting the elements in some specific order there is lot of arrangement of elements. The phases in which the elements are moving to acquire their proper position is called passes.

For example : 10, 30, 20, 50, 40

Pass 1: 10, 20, 30, 50, 40

Pass 2: 10, 20, 30, 40, 50

• In the above method we can see that data is getting sorted in two passes distinctly.