Question

Type your ideas/definitions/examples into the message field to the following discussion prompt:

Discussion Topic: Assume that you are given an unsorted array that contains 100 items, and you have been asked to write/propose an efficient searching algorithm. Which algorithm would you choose and why? What are the possible trad-offs of the selected algorithm if the array size is increased (e.g., 9000 items)?

Answer 1

We have multiple sorting algorithms that could be used to sort an array including

1)Bubble sort

2)Merge Sort

3) Insertion sort

4)Radix Sort

5)Heap sort

6) Selection sort

But one of the most prominently used sorting algorithm is quicksort, quicksort works on divide and conquer strategy,it selects a specific element as an pivot,thereby divides and array into two sun arrays ,the recursive call is made to function where these arrays are passed as parameter and at the end all sorted subarrays are combined to finally produce sorted array.

The library function in Java,python and c which performs sorting use quicksort.

Worst case complexity of quick sort: O(n^2) which is equipment to best case complexity of bubble sort

Best case complexity of quick sort: O(n logn)

Space Complexity of quick sort O(log n) which is better then space Complexity of merge sort O(n).

Hence keeping time complexity, space Complexity and worst case performance into consideration quick sort is considered to be a best sorting algorithm compared to other sorting algorithms.

In case if number of elements increases from 100 to 9000 ,running time or time complexity remains same but space incurred by algorithm would slightly increase.

In certain cases Selection sort may work better than quick sort but still in most of the cases quick sort is preferred.

Please Up-Vote if you find this answer helpful !!