Data Structures --- Sorting (PART-1 INTRO + INSERTION SORT) REFERENCE: PANIMALAR ENGINEERING COLLEGE NOTES

A sorting algorithm is an algorithm that puts element of a list in a certain order (ascending or descending).

Sorting Algorithm are often classified by :

• Computational complexity (worst, Average, Best cases) in the term of size of the list n.

                                             Best case     : O(nlogn)

                                              Worst case  : O(n²)

                                             Average case : O(n)

• Memory utilizations
• Number of comparisons
• Method applied like Insertion, exchange, selection, merging etc.

Sorting techniques are categorized into

                                               Internal Sorting

                                               External Sorting

Internal Sorting takes place in the main memory of a computer

Example : Insertion sort, Bubble sort, Shell sort, Quick sort, Heap sort, Merge sort, Radix(Bucket) sort.

External Sorting takes place in the secondary memory of a computer.

Example: Multiway Merge, Poluphase Merge, Replacement Selection, 2-way Merge

INSERTION SORT

Insertion sorts work by taking elements from the list one by one and inserting them into their current position into a new sorted list. Insertion sort consists of N-1 passes, where N is the number of elements to be sorted.

In the insertion sort the element in the position P is saved in tmp and all larger elements prior to position P are moved one spot to the right. The tmp is placed in the correct spot.

Algorithm

void InsertionSort (ElementType A[], int B)

{

int j,P;

ElementType tmp;

for(P=i;P

{

Tmp = A[P];

for(j = P; j>0 && A[j-1]>temp; j--)

A[j] = A[j-1];

A[j] = temp;

}

}

Example

Consider an unsorted array as follows:

34    8   64    51     32      21                                      where (N = 6)

Original	34	8	64	51	32	21	Positions Moved
Pass = 1	8	34	64	51	32	21	1
Pass = 2	8	34	64	51	32	21	0
Pass = 3	8	34	51	64	32	21	1
Pass = 4	8	32	34	51	64	21	3
Pass = 5	8	21	32	34	51	64	4

The final Sorted array : 8     21        32        34        51        64       

Analysis of Insertion Sort

Worst Case Analysis               -- O(N²)

Best Case Analysis                 -- O(N)

Average Case Analysis           -- O(N²)

Limitations of Insertion Sort

It is relatively efficient for small lists and mostly sorted lists.

It is expensive because of shifting all following elements one by one.

                                                                                                                                         (Contd.....)