CC4 - F - QUEUES & SORTING Flashcards
1
Q
- is a special type of LinkedList.
- It is a FIFO (First-in, First-out) data structure.
A
Queue
2
Q
Describe the Queue
A
- (x) middle removal
- (/) head deletion
- (/) end insertion
3
Q
3 main operations of Queue
A
- EnQueue
- DeQueue
- Peek
4
Q
adds an element to the end of the queue;
A
Enqueue
5
Q
removes the first element in the queue;
A
dequeue
6
Q
returns the first element without removing it, just like in a stack.
A
peek
7
Q
- 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
A
Queue
8
Q
- 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)
A
Queue ADT
9
Q
Queue operations
A
- oEnQueue(x)
- DeQueue()
- Front()
- IsEmpty()
10
Q
T/F Array based vs. Linked Queues
All member functions for both the array-based and linked queue implementations require different time
A
Flase: constant time
11
Q
T/F Array based vs. Linked Queues
The space comparison issues are the same as for the equivalent stack implementations.
A
true
12
Q
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.
A
False: one queue is to one array
13
Q
- 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
A
Searching
14
Q
- If items are sorted then we can divide and conquer
- dividing your work in half with each step
ogenerally a good thing
A
Searching in a Sorted List
15
Q
– The data collection to be sorted is kept in the main memory.
A
Internal Sorting
16
Q
– The sorting of data stored on secondary devices. Data is sorted in the main memory and written back to the secondary device.
A
External Sorting
17
Q
- Simplest iterative algorithm but slowest
- No. of comparison = n-1 (n = no. of elements)
A
Bubble Sort
18
Q
- Easy to understand
- Easy to implement
- No demand for large amounts of memory
- Once sorted, data is available for processing
A
(/) Bubble sort
19
Q
- Sorting takes a long time
A
(x) Bubble sort
20
Q
Best-case O(n)
Worse-case O(n^2) – reverse sorted
A
Bubble sort
21
Q
- Slightly better performance
- Efficient than bubble sort
A
Selection Sort
22
Q
- O(n^2) – both best- and worse-case complexity
A
Selection Sort
23
Q
- 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.
A
(/) Selection Sort
24
Q
- 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
A
(x) Selection Sort
25
**Bubble Sort vs Selection Sort**
how it sorts elements
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.
26
**Bubble Sort vs Selection Sort**
worse- and best-case complexity
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***.
27
**Bubble Sort vs Selection Sort**
un/stable algorithm
* **Bubble sort** is a ***stable*** algorithm, in contrast,
* **selection sort** is ***unstable***.
28
**Bubble Sort vs Selection Sort**
speed & efficiency
* **Selection sort** algorithm is ***fast and efficient***
* **bubble sort** which is ***very slow and inefficien***t.
29
- Simple sorting algorithm
- Array is virtually split into a sorted and unsorted part
**Insertion Sort**
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.
**Insertion Sort**
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.
**(/) Insertion Sort**
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**
**(x) Insertion Sort**
33
**Implementation of Insertion Sort**
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.
34
-Divide and conquer algorithm
-Merge() function – merging 2 halves
**Merge Sort**
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**
**(/) Merge Sort**
36
* Requires **extra space »N**
* requires more space than other sort.
* is **less efficient than other sort**
**(x) Merge Sort**
