Page 252 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

element at the bottom of the heap, and allow it to migrate up the father chain till it finds its Notes
proper position. Complexity T(n) = O(n*log (n)).
Some of the advantages of heap sort are:

it does not use recursion;
works just as fast or any data order.
there is no worst case scenario.
Some of the disadvantages of heap sort are:

slower that quick and merge sort;
memory requirement, it requires both an array and a heap of size n;
not stable.

Self Assessment

Fill in the blanks:

13. ........................ is a simple sorting algorithm, which compares repeatedly each pair of adjacent
items and swaps them if they are in the incorrect order.
14. Quick Sort uses a ........................ chosen by the programmer, and passes through the sorting
list and on a certain condition.
15. ........................ bases on building a heap tree from the data set, and then it removes the
greatest element from the tree and adds it to the end of the sorted list.

13.7 Summary

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 an insertion sort, all the keys in a given list are assumed to be in random order before
sorting.

Selection sort, also called naive (selection) sort, is an in-place comparison sort.
Selection sort first finds the smallest number in the array and exchanges it with the element
from the first position, then it finds the second smallest number and exchanges it with the
element from the second position, and so on until the entire list is sorted.
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.
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.
Radix sort is a non-comparative integer sorting algorithm that sorts data with integer
keys by grouping keys by the individual digits which share the same significant position
and value.
Hashing is the solution when we want to search an element from a large collection of data.
A hash function helps in connecting a key to the index of the hash table. The key can be a
number or string.

LOVELY PROFESSIONAL UNIVERSITY 245