Question

Choice 1. You are the new software developer at work. You are brought into a meeting with clients that do not understand the idea of sorting data. Now you know, that you cannot use complex math to explain, but you can illustrate in diagrams. Basically, this group has been working with unsorted data and you must explain why their searches and reports will be so much faster with sorted data. You do not know anything specific about their data, but you want to sell them on the idea that their data should get sorted to quickly fulfill their current demands.

Illustrate how quicksort, insertion sort, and merge sort work. The idea of this is to show the clients that sorting is very common and beneficial.

Explain the following:

• Why sorting is beneficial to searching?
• How each sort works? What data type or structure does it work best on?
• The benefits or possible issues when the number of items being sorted increases (big 0, for non Big 0 people).
• Use for each sort a set of 9 numbers and diagram each set for each sort. So....that means you would have 3 sets of diagrams.
• Attach your files when you are finished.

Remember, you want to explain but not make it too complicated.

Answer 1

Insertion sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Merge Sort

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The "merge" function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Quick Sort

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.