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