Sorting Flashcards
is an efficient sorting technique based on the >heap data structure.
heap sort
is a nearly-complete binary tree where the parent node could either be minimum
or maximum.
The
heap
The heap with minimum root node is called ______- and the root node
with maximum root node is called __________
min heap
max heap
Build a binary heap from the input array.
Build heap
Extract the maximum element
from the heap and add it to the sorted region.
extract maximum
Heapify the remaining elements of the heap
to maintain the heap property.
Heapify
The time complexity of heap sort is
O(n log n)
Heap sort is a __________
sorting algorithm, meaning it preserves the relative order of
elements with equal keys.
stable
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.
Heap operations
a process of creating a heap from an array.
heapify
process to insert an element in existing heap time complexity
O(log N).
Insertion:
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).
Deletion:
to check or find the most prior element in the heap, (max or min
element for max and min heap).
Peek:
The most popular kind of heap sort, arranges the elements of
the array in ascending order.
Max heap sort:
With a _____________, the array is arranged in ascending order.
Min heap sort:
a simple sorting algorithm that builds the final
sorted array one item at a time by comparisons.
insertion sort
It is much less
efficient on large lists than more advanced algorithms such as
quicksort, heapsort, or merge sort.
insertion sort
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
insertion sort
Insertion sort is also ___________-, i.e., it
is appropriate for data sets that are ___________. Lastly,
it is an___________sorting algorithm and a _____________ sorting algorithm.
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.
insertion sort best average, worst case time complexity
O(n)
O(n^2)
O(n^2)
It is efficient for small data sets or nearly sorted
data
insertion sort
is adaptive in nature, i.e. it is
appropriate for data sets that are already
partially sorted
Insertion sort
insertion sort memory space
constant amount of additional memory space
It works well with data sets that have been sorted
in a significant way.
insertion sort
insertion sort ___________- the relative order of elements
with the same key
does not affect
Advantages of insertion sort
simple implementation, stability, good
performance, simplicity, in-place and online
nature
Disadvantages of insertion sort
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
The best-case scenario for
insertion sort occurs when
the
input array is already sorted or
nearly sorted.
The average-case scenario for
insertion sort assumes a
more
random or unpredictable order
of elements in the input array
The worst-case scenario for
insertion sort occurs when the
input array is
sorted in reverse
order, meaning the elements are
arranged in descending order
In
this situation, insertion sort is
the least efficient, as it requires
a maximum number of
comparisons and swaps.
sorted in reverse
order
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)
BINARY INSERTION sort
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:)
BINARY INSERTION sort
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.
Recursive Insertion Sort
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
Insertion Sort on a linked list
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.
Double-Ended Insertion Sort: or Double Ended Queue
It can sort the elements as soon as it receives them.
insertion sort
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.
QuickSort
Quicksort, a widely used sorting algorithm, developed by
Tony Hoare in 1959
Tony Hoare later improved and published the algorithm in The __________ and an updated version in __________ in the Communications of the Association for Computing Machinery.
Computer Journal in 1962
ALGOL
contributed to the analysis of Quicksort, resolving pivot selection issues and deriving the expected number of comparisons and swaps.
Robert Sedgewick’s
made further improvements to the algorithm, including a pivot scheme called “pseudomedian of nine”
Jon Bentley and Doug McIlroy
Quicksort compact partitioning scheme attributed to
Nico Lomuto.
developed an “AntiQuicksort” function that can intentionally make Quicksort perform poorly under specific conditions.
McIlroy
one of the most efficient sorting algorithms.
quicksort
is one of the most popular sorting algorithms that uses nlogn comparisons to sort an array of n elements in a typical situation.
Quicksort
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 _._______
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.
Partition is done recursively on __________ of the pivot after it is placed in its correct position.
each side
Advantages quicksort
Efficiency
In-place sorting
Good for Random Data
Disadvantages quicksort
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
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
merge sort
s a recursive algorithm that continuously splits
the array in half until it cannot be divided
merge sort
APPLICATIONS OF
MERGE SORT:
sorting large datasets
external sorting
custom sorting
ADVANTAGES OF
MERGE SORT
stability
guaranteed worst case performance
parallelizable
disadvantages merge sort
space complexity
not in place
not always optimal for small datasets
works by examining each set of adjacent
elements in the string, from left to right, switching their
positions if they are out of order.
bubble sort
Bubble sort advantages
Simplicity, No Additional Memory, Stable
Sort
bubble sorrt disadvantages
Poor Performance, No Benefit from the
Presorted Data, Not Suitable for Modern
Applications
