Question

1.

Which is the best sorting algorithm for larger arrays if all the items can not fit in main memory?

		selection sort
		insertion sort
		quicksort
		Merge sort

2.

Which sorting algorithm sorts items without comparing them?

		quick sort
		radix sort
		merge sort
		Insertion sort

3

What is the average running time for quicksort?

		O(n2)
		O(logn)
		O(nlogn)
		O(n)
		O(n2logn)

4. Examine the steps of the following algorithm and write the name of the algorithm described in the blank provided:

1. Recursively divide an array into two equal halves.
2. Once the array can no longer be subdivided, put the halves back together; while doing so, sort the halves into a temporary array.
3. Copy the temporary array back into the original array.

		quick sort
		radix sort
		insertion sort
		shell sort
		Merge Sort

5. In the quicksort algorithm, why is the insertion sort algorithm used when the list becomes small?

		Quicksort will not work on arbitrarily small lists.
		Insertion sort is more efficient when the list is small.
		Using insertion sort ensures a stable sort.
		Quicksort cannot partition smaller arrays

Answer 1

1)Which is the best sorting algorithm for larger arrays if all the items can not fit in main memory?

Ans) Merge sort

Explanation: for example you have to sort 1 GB of data with only 100 MB of available main memory. in this case this is the most appropriate algoritham is this merge sort

2)Which sorting algorithm sorts items without comparing them?

Ans)radix sort

Explanation: non-comparison based sorting algorithms like Radix Sort, Counting Sort, and Bucket Sort

3)What is the average running time for quicksort?

Ans)O(n log n)

Explanation: worst case - o(n2)

best case - o(n)

4. Examine the steps of the following algorithm and write the name of the algorithm described in the blank provided:

Ans)Merge Sort

Explanation:

1. Recursively divide an array into two equal halves.
2. Once the array can no longer be subdivided, put the halves back together; while doing so, sort the halves into a temporary array.
3. Copy the temporary array back into the original array.

5) In the quicksort algorithm, why is the insertion sort algorithm used when the list becomes small?

Ans)Insertion sort is more efficient when the list is small.

explanation : more than quick sort insertion sort is best when list size is small