CC4 - F - QUEUES & SORTING

Question 1

• is a special type of LinkedList.
• It is a FIFO (First-in, First-out) data structure.

Answer 1

Queue

Question 2

Describe the Queue

Answer 2

• (x) middle removal
• (/) head deletion
• (/) end insertion

Question 3

3 main operations of Queue

Answer 3

• EnQueue
• DeQueue
• Peek

Question 4

adds an element to the end of the queue;

Answer 4

Enqueue

Question 5

removes the first element in the queue;

Answer 5

dequeue

Question 6

returns the first element without removing it, just like in a stack.

Answer 6

peek

Question 7

• an insertion must happen at one end that we call rear or tail of the queue and any removal must happen at the other end called
  front or end of the queue

Answer 7

Queue

Question 8

• A List or collection with the restriction that insertion can be performed at one end (rear) and deletion can be performed at the other end (front)

Answer 8

Queue ADT

Question 9

Queue operations

Answer 9

• oEnQueue(x)
• DeQueue()
• Front()
• IsEmpty()

Question 10

T/F Array based vs. Linked Queues

All member functions for both the array-based and linked queue implementations require different time

Answer 10

Flase: constant time

Question 11

T/F Array based vs. Linked Queues

The space comparison issues are the same as for the equivalent stack implementations.

Answer 11

true

Question 12

T/F Array based vs. Linked Queues

Unlike the array-based stack implementation, there is no convenient way to store one queues in the same array, unless items are always transferred directly from one queue to the other.

Answer 12

False: one queue is to one array

Question 13

• Given a list of data find the location of a particular value or report that value is not present
• linear search
• if items are unsorted, this approach is necessary

Answer 13

Searching

Question 14

• If items are sorted then we can divide and conquer
• dividing your work in half with each step
  ogenerally a good thing

Answer 14

Searching in a Sorted List

Question 15

– The data collection to be sorted is kept in the main memory.

Answer 15

Internal Sorting

Question 16

– The sorting of data stored on secondary devices. Data is sorted in the main memory and written back to the secondary device.

Answer 16

External Sorting

Question 17

• Simplest iterative algorithm but slowest
• No. of comparison = n-1 (n = no. of elements)

Answer 17

Bubble Sort

Question 18

• Easy to understand
• Easy to implement
• No demand for large amounts of memory
• Once sorted, data is available for processing

Answer 18

(/) Bubble sort

Question 19

• Sorting takes a long time

Answer 19

(x) Bubble sort

Question 20

Best-case O(n)
Worse-case O(n^2) – reverse sorted

Answer 20

Bubble sort

Question 21

• Slightly better performance
• Efficient than bubble sort

Answer 21

Selection Sort

Question 22

• O(n^2) – both best- and worse-case complexity

Answer 22

Selection Sort

Question 23

• The main advantage of the it is that it performs well on a small list.
• Because it is an in-place sorting algorithm, no additional temporary storage is required beyond what is needed to hold the original list.
• Its performance is easily influenced by the initial ordering of the items before the sorting process.

Answer 23

(/) Selection Sort

Question 24

• The primary disadvantage of the it is its poor efficiency when dealing with a huge list of items.
• It requiresn-squared number of steps for sorting n elements.
• Quick Sort is much more efficient than this

Answer 24

(x) Selection Sort

Question 25

Bubble Sort vs Selection Sort
how it sorts elements

Answer 25

In the bubble sort, each element and its adjacent element is compared and swapped if required.

On the other hand, selection sort works by selecting the element and swapping that element with the last element. The selected element could be largest or smallest depending on the order i.e., ascending or descending.

Question 26

Bubble Sort vs Selection Sort
worse- and best-case complexity

Answer 26

The worst-case complexity is same in both the algorithms, i.e., O(n^2)

but best complexity is different.
* Bubble sort takes an order of n time whereas
* selection sort consumes an order of n2 time.

Question 27

Bubble Sort vs Selection Sort
un/stable algorithm

Answer 27

• Bubble sort is a stable algorithm, in contrast,
• selection sort is unstable.

Question 28

Bubble Sort vs Selection Sort
speed & efficiency

Answer 28

• Selection sort algorithm is fast and efficient
• bubble sort which is very slow and inefficient.

Question 29

• Simple sorting algorithm
• Array is virtually split into a sorted and unsorted part

Answer 29

Insertion Sort

Question 30

To sort an array of size n in ascending order:

1.Iterate from arr[1] to arr[n] over the array.
2.Compare the current element (key) to its predecessor. [yung kasunod]
3.If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Answer 30

Insertion Sort

Question 31

• The main advantage of it is its simplicity.
• It also exhibits a good performance when dealing with a small list.
• It is an in-place sorting algorithm, so the space requirement is minimal.

Answer 31

(/) Insertion Sort

Question 32

• The disadvantage of it is that it does not perform as well as other, better sorting algorithms
• With n-squared steps required for every n element to be sorted, the insertion sort does not deal well with a huge list.
• It is particularly useful only when sorting a list of few items

Answer 32

(x) Insertion Sort

Question 33

Implementation of Insertion Sort

Answer 33

1. The first step is to create a method that takes in input the array to be sorted, sort arr as seen in line 3 in the code above.
2. The second step is to create an outer for loop which will iterate over each element of the array as shown in line 5.
3. The third step is to create a separate iterator, j which will check for the ascending order of elements in the list, as shown in line 7.
4. The fourth step is the inner while loop:
   * a. As shown in line 9 the while loop must satisfy two conditions: the value of j must be greater than 0, and the value at index j-1, must be greater than the value at index j.
   * b. If this condition holds true then, as shown from lines 11 to 14, the key is set to the value at index j.
   * c. Then the values at j and j-1 are swapped.
   * d.The value of j is reduced by 1 and the loop continues till one of the conditions breaks.
   This continues for every iteration of the outer for loop till that also breaks.

Question 34

-Divide and conquer algorithm
-Merge() function – merging 2 halves

Answer 34

Merge Sort

Question 35

• It can be applied to files of any size.
• Reading of the input during the run-creation step is sequential ==> Not much seeking.
• If heap sort is used for the in-memory part of the merge, its operation can be overlapped with I/O

Answer 35

(/) Merge Sort

Question 36

• Requires extra space»N
• requires more space than other sort.
• is less efficient than other sort

Answer 36

(x) Merge Sort