Module 5: Sorting Algorithms

Sorting

_______ is a basic building block that many other algorithms are built upon.

Sorting

_______ is one of the most thoroughly studied algorithms in computer science.

Searching, Selection, Duplicates, Distribution

These range of problems are done much faster if the list is sorted.

Selection

For example, finding the kth-largest or smallest value, or finding the median value of the list, is much easier when the values are in ascending or descending order

Distribution

For example, finding the element that appears most or least often is relatively straightforward with a sorted list

time, space

The efficiency of any sorting algorithm is determined by the ____ complexity and _____ complexity of the algorithm.

Time complexity

_______ refers to the time taken by an algorithm to complete its execution with respect to the size of the input.

O

Big-O notation

Ω

Omega notation

Θ

Theta notation

Space complexity, auxiliary memory, input

_______ refers to the total amount of memory used by the algorithm for a complete execution. It includes both the ______ and the _____.

auxiliary memory

The _______ is the additional space occupied by the algorithm apart from the input data.

auxiliary memory

Usually, _______ is considered for calculating the space complexity of an algorithm.

Bubble sort
Selection sort
Insertion sort
Shell sort
Quick sort
Merge sort
Heap sort
Counting sort
Radix sort

Different Sorting Algorithms

Bubble sort

_____ is one of the most straightforward sorting algorithms.

Bubble sort

_____ is a simple sorting algortihm that works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.

largest

Bubble sort’s name comes from the way the algorithm works: With every new pass, the _____ element in the list “bubbles up” toward its correct position.

Bubble sort

______ consists of making multiple passes through a list, comparing elements one by one, and swapping adjacent items that are out of order.

Selection sort

_______ is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

minimum, beginning

The selection sort algorithm sorts an array by repeatedly finding the _____ element (considering ascending order) from unsorted part and putting it at the ______.

insertion sort

Like bubble sort, the______ algorithm is straightforward to implement and understand

Insertion sort

it builds the sorted list one element at a time by comparing each item with the rest of the list and inserting it into its correct position

small

Basically, Insertion sort is efficient for ____ data values

adaptive

Insertion sort is _____ in nature, i.e. it is appropriate for data sets which are already partially sorted.

first, second

In insertion sort, the ____ element in the array is assumed to be sorted. Take the ____ element and store it separately in key.

Shell sort

It is a sorting algorithm that is an extended version of insertion sort.

insertion

Shell sort has improved the average time complexity of _____ sort.

comparison-based, in-place sorting

Shell sort, similar to insertion sort, is a ______ and _______ algorithm

Shell sort

It allows the movement and swapping of far-away elements as well.

Shell sort, interval

______ first sorts the elements that are far away from each other, then it subsequently reduces the gap between them. This gap is called as _____

Quick sort

_______ is a sorting algorithm based on the divide and conquer approach

Quick sort

_____ is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays.

O(n2)

Quick sort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are _____, respectively

Merge Sort

______ is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm.

Ο(n log n)

Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being _____, it is one of the most respected algorithms

Merge sort

______ first divides the array into equal halves and then combines them in a sorted manner

Divide and Conquer technique

Using the ________, we divide a problem into sub-problems. When the solution to each sub-problem is ready, we 'combine' the results from the sub-problems to solve the main problem

Heap sort, arrays, trees

______ is a popular and efficient sorting algorithm in computer programming. Learning how to write the heap sort algorithm requires knowledge of two types of data structures - _____ and _____

heap

Heap sort works by visualizing the elements of the array as a special kind of complete binary tree called a _____

heap, sorted

The concept of heap sort is to eliminate the elements one by one from the ____ part of the list, and then insert them into the ____ part of the list.

in-place

Heap sort is the _____ sorting algorithm

complete, two, last, left

A heap is a _____ binary tree, and the binary tree is a tree in which the node can have the utmost ___ children. A complete binary tree is a binary tree in which all the levels except the ____ level, i.e., leaf node, should be completely filled, and all the nodes should be ___-justified

insertion, merge

The heap sort algorithm is the combination of two other sorting algorithms: _____ sort and _____ sort.

constant

Heap sort’s similarities with insertion sort include that only a _____ number of array elements are stored outside the input array at any time

O(n log n)

The time complexity of the heap sort algorithm is _____, similar to merge sort

Counting sort

______ is a sorting technique that is based on the keys between specific ranges

Counting sort

This sorting technique doesn't perform sorting by comparing elements. It performs sorting by counting objects having distinct key values like hashing

range, number of objects to be sorted, negative

Counting sort is effective when ____ is not greater than _______. It can be used to sort the _____ input values

Radix sort

______ is the linear sorting algorithm that is used for integers

digit by digit, least, most

In Radix sort, _____ sorting is performed that is started from the ____ significant digit to the ____ significant digit.