SEARCHING AND SORTING

Question 1

Briefly describe selection sort

Answer 1

• Selection sort swaps the current element with the lowest element from the remaining elements in the list.
• Selection Sort does not swap each time it finds elements out of position.
• Selection sort makes a complete pass while searching for the next item to swap.
• At the end of a pass once the item is located, one swap is made.

Question 2

What is a pass in selection sort?

Answer 2

A pass is one complete execution of the inner loop

Question 3

Briefly describe insertion sort

Answer 3

• The insertion sort first selects an item and moves items up or down based on the comparison to the selected item.
• The idea is to get the selected item in proper position by shifting items around in the list.

Question 4

Briefly describe linear/selection search

Answer 4

• The Linear Search searches through a list sequentially (one element at time) looking for a match.
• The index position of a match is returned if found or -1 is returned if no match is found.
• It must go through the entire list in order to determine if there is no match.

Question 5

Briefly describe the performance of the linear/selection search

Answer 5

• The Linear/Sequential Search works fine if the array is relatively small (a few hundred elements). However, if the array is large, it could become slow.
• Average number of elements searched is n/2, where n is the array length.
• This search method works fine when the array is sorted or even when it is not sorted.

Question 6

Give the big o notation of Linear Search, Merge Sort ,Binary Search, Quick Sort

Answer 6

Quick-O(n2)
Merge Sort- O(nlogn)
Binary-O(log N)
Linear-O(N)

Question 7

What is the difference between Selection Sort and Insertion Sort algorithms?

Answer 7

insertion sort performs sorting by exchanging an element at a time with the partially sorted array while selection sort performs sorting by selecting the smallest element from the remaining elements and exchanging it with the element in the correct location.

Question 8

In terms of sorting algorithms what do we mean when we say the algorithm is a stable sort? Support your answer by three examples of such algorithms

Answer 8

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort.

Question 9

How does linear search differ from binary search?

Answer 9

Linear search is a search that finds an element in the list by searching the element sequentially until the element is found in the list. On the other hand, a binary search is a search that finds the middle element in the list recursively until the middle element is matched with a searched element.

Time complexity

Question 10

Explain the concept of divide and conquer as applied in Quicksort, Merge sort and
Radix sort algorithms

Answer 10

This paradigm, divide-and-conquer, breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem.