Sorting

Question 1

is an efficient sorting technique based on the >heap data structure.

Answer 1

heap sort

Question 2

is a nearly-complete binary tree where the parent node could either be minimum
or maximum.

Answer 2

The
heap

Question 3

The heap with minimum root node is called ______- and the root node
with maximum root node is called __________

Answer 3

min heap

max heap

Question 4

Build a binary heap from the input array.

Answer 4

Build heap

Question 5

Extract the maximum element
from the heap and add it to the sorted region.

Answer 5

extract maximum

Question 6

Heapify the remaining elements of the heap
to maintain the heap property.

Answer 6

Heapify

Question 7

The time complexity of heap sort is

Answer 7

O(n log n)

Question 8

Heap sort is a __________
sorting algorithm, meaning it preserves the relative order of
elements with equal keys.

Answer 8

stable

Question 9

can be used to efficiently implement priority queues because
they allow us to insert, delete, and find the element with the highest priority in
logarithmic time.

Answer 9

Heap operations

Question 10

a process of creating a heap from an array.

Answer 10

heapify

Question 11

process to insert an element in existing heap time complexity
O(log N).

Answer 11

Insertion:

Question 12

deleting the top element of the heap or the highest priority
element, and then organizing the heap and returning the element with time
complexity O(log N).

Answer 12

Deletion:

Question 13

to check or find the most prior element in the heap, (max or min
element for max and min heap).

Answer 13

Peek:

Question 14

The most popular kind of heap sort, arranges the elements of

the array in ascending order.

Answer 14

Max heap sort:

Question 15

With a _____________, the array is arranged in ascending order.

Answer 15

Min heap sort:

Question 16

a simple sorting algorithm that builds the final
sorted array one item at a time by comparisons.

Answer 16

insertion sort

Question 17

It is much less
efficient on large lists than more advanced algorithms such as
quicksort, heapsort, or merge sort.

Answer 17

insertion sort

Question 18

t iterates, consuming one input element each repetition,
and grows a sorted output list. At each iteration, it
removes one element from the input data, finds the location it
belongs within the sorted list, and inserts it there

Answer 18

insertion sort

Question 19

Insertion sort is also ___________-, i.e., it
is appropriate for data sets that are ___________. Lastly,
it is an___________sorting algorithm and a _____________ sorting algorithm.

Answer 19

Insertion sort is also adaptive in nature, i.e., it
is appropriate for data sets that are already partially sorted. Lastly,
it is an in-place sorting algorithm and a stable sorting algorithm.

Question 20

insertion sort best average, worst case time complexity

Answer 20

O(n)

O(n^2)

O(n^2)

Question 21

It is efficient for small data sets or nearly sorted
data

Answer 21

insertion sort

Question 22

is adaptive in nature, i.e. it is
appropriate for data sets that are already
partially sorted

Answer 22

Insertion sort

Question 23

insertion sort memory space

Answer 23

constant amount of additional memory space

Question 24

It works well with data sets that have been sorted
in a significant way.

Answer 24

insertion sort

Question 25

insertion sort ___________- the relative order of elements with the same key

Answer 25

does not affect

Question 26

Advantages of insertion sort

Answer 26

simple implementation, stability, good performance, simplicity, in-place and online nature

Question 27

Disadvantages of insertion sort

Answer 27

inefficiency on large data sets its worst-case time complexity of O(n'2), and its modest memory usage not efficient with repeated elements, lacks scalability, and has limited parallelization potential

Question 28

The best-case scenario for insertion sort occurs when

Answer 28

the input array is already sorted or nearly sorted.

Question 29

The average-case scenario for insertion sort assumes a

Answer 29

more random or unpredictable order of elements in the input array

Question 30

The worst-case scenario for insertion sort occurs when the input array is

Answer 30

sorted in reverse order, meaning the elements are arranged in descending order

Question 31

In this situation, insertion sort is the least efficient, as it requires a maximum number of comparisons and swaps.

Answer 31

sorted in reverse order

Question 32

is a sorting algorithm which is similar to the insertion sort, but instead of using linear search to find the location where an element should be inserted, we use binary search. Thus, we reduce the comparative value of inserting a single element from O (N) to O (log N)

Answer 32

BINARY INSERTION sort

Question 33

It is a flexible algorithm, which means it works faster when the same given members are already heavily sorted, i.e., the current location of the feature is closer to its actual location in the sorted list (Variant of insertion sort:)

Answer 33

BINARY INSERTION sort

Question 34

is a variation of the traditional Insertion Sort algorithm that uses recursion to sort an array or list of elements. It shares the same basic principle with regular Insertion Sort, which involves dividing the list into a sorted and an unsorted part, but it uses a recursive function to achieve this rather than a loop.

Answer 34

Recursive Insertion Sort

Question 35

sorting algorithm that is used to sort the elements of a linked list in a specific order, typically in ascending or descending order. Instead of using array indices like in the traditional insertion sort for arrays, this variant of the algorithm operates on the linked structure by repeatedly removing nodes from the original list and inserting them into their correct position in a new, sorted linked list

Answer 35

Insertion Sort on a linked list

Question 36

is also a Queue data structure in which the insertion and deletion operations are performed at both the ends (front and rear). That means, we can insert at both front and rear positions and can delete from both front and rear positions. This variation works from both ends of the array simultaneously. It compares and swaps elements at both ends, reducing the number of shifts or swaps in some cases.

Answer 36

Double-Ended Insertion Sort: or Double Ended Queue

Question 37

It can sort the elements as soon as it receives them.

Answer 37

insertion sort

Question 38

is a sorting algorithm based on the divide and conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.

Answer 38

QuickSort

Question 39

Quicksort, a widely used sorting algorithm, developed by

Answer 39

Tony Hoare in 1959

Question 40

Tony Hoare later improved and published the algorithm in The __________ and an updated version in __________ in the Communications of the Association for Computing Machinery.

Answer 40

Computer Journal in 1962 ALGOL

Question 41

contributed to the analysis of Quicksort, resolving pivot selection issues and deriving the expected number of comparisons and swaps.

Answer 41

Robert Sedgewick's

Question 42

made further improvements to the algorithm, including a pivot scheme called "pseudomedian of nine"

Answer 42

Jon Bentley and Doug McIlroy

Question 43

Quicksort compact partitioning scheme attributed to

Answer 43

Nico Lomuto.

Question 44

developed an "AntiQuicksort" function that can intentionally make Quicksort perform poorly under specific conditions.

Answer 44

McIlroy

Question 45

one of the most efficient sorting algorithms.

Answer 45

quicksort

Question 46

is one of the most popular sorting algorithms that uses nlogn comparisons to sort an array of n elements in a typical situation.

Answer 46

Quicksort

Question 47

The key process in quicksort is a __________ which targets to place the chosen ________ at its correct position in the sorted array and put all the smaller elements to the ______- of the pivot and all greater elements on the _._______

Answer 47

The key process in quicksort is a partition() which targets to place the chosen pivot at its correct position in the sorted array and put all the smaller elements to the left of the pivot and all greater elements on the right.

Question 48

Partition is done recursively on __________ of the pivot after it is placed in its correct position.

Answer 48

each side

Question 49

Advantages quicksort

Answer 49

Efficiency In-place sorting Good for Random Data

Question 50

Disadvantages quicksort

Answer 50

unstable worst-case time complexity requires careful pivot selection performance degradation with sorted data suboptimal performance for equal elements difficult to implement for non-comparable data complexity in implementation

Question 51

defined as a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array

Answer 51

merge sort

Question 52

s a recursive algorithm that continuously splits the array in half until it cannot be divided

Answer 52

merge sort

Question 53

APPLICATIONS OF MERGE SORT:

Answer 53

sorting large datasets external sorting custom sorting

Question 54

ADVANTAGES OF MERGE SORT

Answer 54

stability guaranteed worst case performance parallelizable

Question 55

disadvantages merge sort

Answer 55

space complexity not in place not always optimal for small datasets

Question 56

works by examining each set of adjacent elements in the string, from left to right, switching their positions if they are out of order.

Answer 56

bubble sort

Question 57

Bubble sort advantages

Answer 57

Simplicity, No Additional Memory, Stable Sort

Question 58

bubble sorrt disadvantages

Answer 58

Poor Performance, No Benefit from the Presorted Data, Not Suitable for Modern Applications