Page 217 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Introduction

Sorting in general refers to various methods of arranging or ordering things based on criteria
(numerical, chronological, alphabetical, hierarchial, etc.). Sorting the elements is an operation
that is encountered very often in the solving of problems. For this reason, it is important for a
programmer to learn how sorting algorithms work. A sorting algorithm refers to putting the
elements of a data set in a certain order, this order can be from greater to lower or just the
opposite, and the programmer determines this. In practice, the most common order types are
those of numbers and strings (chars) or lexicographical order. Having an array of elements, a ,
1
a , ... , a , it is required to sort the elements that the following condition is assured: a <= a <= a
2 n 1 2 3
< = ... < = a <= a < = ... < = a . Due to obvious reasons, Sorting (of data) is of immense importance
i j n
and is one of the most extensively researched subjects. It is one of the most fundamental
algorithmic problems. So much so that it is also fundamental to many other fundamental
algorithmic problems such as search algorithms, merge algorithms, etc. It is estimated that
around 25% of all CPU cycles are used to sort data. There are many approaches to sorting data
and each has its own merits and demerits.

13.1 Insertion Sort

Insertion sort is an elementary sorting algorithm. The insertion sort is commonly compared to
organizing a handful of playing cards. You pick up the random cards one at a time. As you pick
up each card, you insert it into its correct position in your hand of organized cards. The insertion
sort maintains the two sub-arrays within the same array. At the beginning of the sort, the first
element of the first sub-array is considered the “sorted array”. With each pass through the loop,
the next element in the unsorted second sub-array is placed into its proper position in the first
sorted sub-array.

Did u know? The insertion sort can be very fast and efficient when used with smaller
arrays. Unfortunately, it loses this efficiency when dealing with large amounts of data.
In an insertion sort, all the keys in a given list are assumed to be in random order before sorting.
That is, all possible orderings of the keys within the list are equally likely.
1. First, imagine an item is to be inserted to an “empty” list, which is actually the original
list.
2. Then, the first item in the original list is defaulted into the first position in the list. This
item is now said to be in a sorted list. The sublist from the second item to the end is
regarded as the unsorted list. This means that the original list is divided into sorted and
unsorted sublists.
3. Then, the first (next) item of the unsorted list (i.e. the second item of the original list) is
inserted into the sorted sublist. At this time, the sorted sublist is expanding while the
unsorted sublist is shrinking. And so it goes — step 3 repeats itself until the original list is
exhausted.
The following figure shows a list of integers being sorted in descending order to explain this
algorithm.

210 LOVELY PROFESSIONAL UNIVERSITY