SEARCHING AND SORTING Flashcards

1
Q

Briefly describe selection sort

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a pass in selection sort?

A

A pass is one complete execution of the inner loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Briefly describe insertion sort

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Briefly describe linear/selection search

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Briefly describe the performance of the linear/selection search

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How does linear search differ from binary search?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly