DCSN04C midterms Flashcards
is used to rearrange a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.
Sorting Algorithm
refers to rearrangement of a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.
Sorting
uses constant space for producing the output (modifies the given array only) or copying elements to a temporary storage.
In-place Sorting
is when all the data is placed in the main memory or internal memory.
Internal Sorting
is when all the data that needs to be sorted cannot be placed in memory at a time, the sorting is
External Sorting
When two same items appear in the same order in sorted data as in the original array called
Stable sorting
When two same data appear in the different order in sorted data it is called
Unstable sorting
a measure of how long it takes to run an algorithm, is used to categorize sorting algorithms.
Time Complexity
This is the amount of extra space (apart from input array) needed to sort.
Auxiliary Space
A sorting algorithm is said to be stable if the relative order of equal elements is preserved after sorting.
Stability
is one that does not require additional memory to sort the data.
In-Place Sorting
is one that takes advantage of pre-existing order in the data to improve performance.
Adaptive sorting
Sorting is often a crucial step in search algorithms like binary search and Ternary Search.
Searching Algorithms
Sorting data makes it easier to search, retrieve, and analyze.
Data management
Sorting data in databases improves query performance
Database optimization
Sorting is used to prepare data for training machine learning models.
Machine learning
Sorting helps in identifying patterns, trends, and outliers in datasets.
Data Analysis
Sorting algorithms are used in operating systems for tasks like task scheduling, memory management, and file system organization.
Operating Systems
is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
Selection sort
is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm.
Merge Sort
Given a list, take the current element and insert it at the appropriate position of the list, adjusting the list every time you insert. It is similar to arranging the cards in a Card game.
Insertion Sort
is a fundamental concept in computer science used for storing and managing data in a specific order. It follows the principle of “First in, First out” (FIFO), where the first element added to the queue is the first one to be removed.
Queue Data Structure
A queue is a linear data structure that follows the _____ principle. It operates like a line where elements are added at one end (rear) and removed from the other end (front).
First-In-First-Out (FIFO)
Adds an element to the rear of the queue.
Enqueue (Insert)
Removes and returns the element from the front of the queue.
Dequeue (Delete)
Returns the element at the front of the queue without removing it.
Peek
Checks if the queue is empty.
Empty
Checks if the queue is full.
Full
we iterate over all the elements of the array and check if it the current element is equal to the target element.
Sequential Search/Linear Search
is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.
Bubble Sort
is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. Then, you pick a card from the unsorted group and put it in the right place in the sorted group.
Insertion sort
is a sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the input array into smaller subarrays and sorting those subarrays then merging them back together to obtain the sorted array.
Merge sort
is a comparison-based sorting algorithm. It sorts an array by repeatedly selecting the smallest (or largest) element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire array is sorted.
Selection Sort
is a comparison-based sorting algorithm. It sorts an array by repeatedly selecting the smallest (or largest) element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire array is sorted.
Selection Sort
