Page 224 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

Clearly, the outer loop runs n–1 times. The only complexity in this analysis is the inner loop. Notes
If we think about a single time the inner loop runs, we can get a simple bound by noting that it
can never loop more than n times. Since the outer loop will make the inner loop complete n
times, the comparison can’t happen more than O(n2) times. Also, the same complexity applies to
worst case or even best case scenario.

Advantages and Disadvantages of Selection Sort

The advantages of Selection Sort are:
easy to implement;
requires no additional storage space.

it performs well on a small list.
Disadvantages of Selection Sort are
poor efficiency when dealing with a huge list of items
its performance is easily influenced by the initial ordering of the items before the sorting
process.
Selection sort is sorting algorithm known by its simplicity. Unfortunately, it lacks efficiency on
huge lists of items, and also, it does not stop unless the number of iterations has been achieved
(n-1, n is the number of elements) even though the list is already sorted.

Self Assessment

Fill in the blanks:
3. ............................, also called naive (selection) sort, is an in-place comparison sort.
4. The ............................ for selection algorithm is of O(n ), which is of the same order as the
2
insertion sort.

13.3 Merge Sort

Merging means combining elements of two arrays to form a new array. The simplest way of
merging two arrays is to first copy all the elements of one array into a new array and then
append all the elements of the second array to the new array. If you want the resultant array to
be sorted, you can sort it by any of the sorting techniques.
If the arrays are originally in sorted order, they can be merged in such a way as to ensure that the
combined array is also sorted. This technique is known as merge sort.
Merge sort is based on Divide and conquer method. It takes the list to be sorted and divide it in
half to create two unsorted lists. The two unsorted lists are then sorted and merged to get a
sorted list. The two unsorted lists are sorted by continually calling the merge-sort algorithm; we
eventually get a list of size 1 which is already sorted. The two lists of size 1 are then merged.

A list of keys for mergesort is divided into two sublists of about the same length. Then, these
two sublists are further divided into half each. We keep doing this until each sublist consists of
only one key. Then, the way we conquer the sorting is to merge the sublists two pieces by two
pieces. According to our order requirement, when we merge two sublists, we put the smaller
one in the front for ascending order, or the larger one in the front for descending order. Now,
each sublist consists of two keys in order. Then, we merge the sublists two pieces by two pieces
again in the same way of ordering. By repeating this process, we finally obtain a sorted list.

LOVELY PROFESSIONAL UNIVERSITY 217