Sorting

Question 1

Average fast runtime for an algorithm:

Answer 1

O(N log N)

Question 2

Sort

Answer 2

Method for reorganizing a large number of items into a specific order

Question 3

Search

Answer 3

Process of finding the required information from a collection of items stored as elements in the computer memory.

Question 4

Selection sort

Answer 4

Effective and efficient sort algorithm based on comparison operations.

Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)

Question 5

Insertion Sort

Answer 5

sort in c is the simple sorting algorithm that virtually splits the given array into sorted and unsorted parts, then the values from the unsorted parts are picked and placed at the correct position in the sorted part.

Best Case: O(n)
Average Case: O(n^2)
Worst Case: O(n^2)

Question 6

Shell Sort

Answer 6

Sorting algorithm that is highly efficient and based on the insertion sort algorithm. This algorithm avoids large shifts, as in insertion sort, where the smaller value is on the far right and must be moved to the far left.

Best Case: O(nlog n)
Average Case: O(nlog n)
Worst Case: O(n^2)

Question 7

Quicksort

Answer 7

Quicksort is a highly efficient sorting technique that divides a large data array into smaller ones. A vast array is divided into two array, one containing values smaller than the provided value, say pivot, on which the partition is based. The other contains values greater than the pivot value.

Best Case: O(Nlog N)
Average Case: O(Nlog N)
Worst Case: O(n^2)

Question 8

Merge Sort

Answer 8

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.

Best Case: O(Nlog N)
Average Case: O(Nlog N)
Worst Case: O(N*log N)

Question 9

Radix Sort

Answer 9

Stable sorting subroutine-based integer sorting algorithm.

Best Case: O(a(n+b))
Average Case: O(p*(n+d))
Worst Case: O(n^2)

Question 10

Heap sort

Answer 10

Comparison based sorting technique based on the binary heap data structure.

Best Case: O(Nlog N)
Average Case: O(Nlog N)
Worst Case: O(N*log N)

Question 11

Topological Sort

Answer 11

A linear ordering of its vertices such that for every directed edge, uv from vertex u to vertex v, u comes before v in the ordering.

Question 12

Bubble Sort

Answer 12

Works by repeatedly swapping the adjacent elements if they are in the wrong order.

Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)

Question 13

Bucket Sort

Answer 13

Best Case: O(n + k)
Average Case: O(n + k)
Worst Case: O(n^2)