Sorting

Question 1

downside of most most worst-case sorting algorithms that do optimally well in the worst-case

Answer 1

(notably heap sort and merge sort), do not take existing order within their input into account,

Question 2

how to rectify mergesort not taking into account existing order of its input?

Answer 2

by checking if the last element of the lefthand group is less than (or equal) to the first element of the righthand group, in which case a merge operation may be replaced by simple concatenation – a modification that is well within the scope of making an algorithm adaptive.

Question 3

list 8 adaptive sort algorithms

Answer 3

adaptive heap sort, adaptive merge sort, patience sort,[1] Shellsort, smoothsort, splaysort, straight insertion sort, and Timsort.

Question 4

why are adaptive sorting algorithms attractive?

Answer 4

because nearly sorted sequences are common in practice

Question 5

adaptive sort

Answer 5

A sorting algorithm falls into the adaptive sort family if it takes advantage of existing order in its input. It benefits from the presortedness in the input sequence – or a limited amount of disorder for various definitions of measures of disorder – and sorts faster. Adaptive sorting is usually performed by modifying existing sorting algorithms.

Question 6

Permutation

Answer 6

permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word “permutation” also refers to the act or process of changing the linear order of an ordered set.

Question 7

How many permutations are there in a set of n elements?

Answer 7

n!

Question 8

technically a permutation of set S is defined as what

Answer 8

a bijection from S to itself.[2][3] That is, it is a function from S to S for which every element occurs exactly once as an image value

Question 9

The collection of all permutations of a set form what?

Answer 9

a group called the symmetric group of the set, where the group operation is the composition (performing two given rearrangements in succession), which results in another rearrangement

Question 10

k-permutation

Answer 10

the number of arrangements of k items from n objects

Question 11

How to denote a k permutation

Answer 11

It can be written as nPk (which reads “n permute k”)

Question 12

nPk is equal to?

Answer 12

n(n−1)⋯(n−k+1)

aka
n!/(n−k)!

Question 13

Insertion sort

Answer 13

InsertionSort(A) //[0, n-1]

For (i = 0 to ) 
  let j = i + 1
  while (j> 0 && A[j] > A[j-1]) 
    swap(A, j, j-1)
    j—