4-Sorting algorithms (selection - insertion - bubble - Quick )

Question 1

Goal of sorting ?

Answer 1

The goal of sorting is to rearrange the elements of S ( a sequence {s1,s2,s3,…,sn} of n>=0 elements drawn from a universe U ) and produce another sequence S’ such that elements of S appear in order

Question 2

What does it mean to say “in order”?

Answer 2

Given a relation, eg. < :

• It has to be a total order (simple order)
• For all pairs of elements (i,j), exact one of the following is true: i i

Question 3

What is a stable sort?

Answer 3

When it preserves the relative order of the items with duplicated keys on the list

Question 4

Advantages of a stable sort:

Answer 4

• more efficient in practice
• in general, easier to be parallelised
• allow multi-key sort to be easily implemented by combining multiple runs the sorting algorithm.

Question 5

How does selection sort work ?

Answer 5

selection sort orders a list of elements by finding the

index of the maximum element (selecting the element) and putting it in its place in the list

Question 6

Characteristics of selection sort ?

Answer 6

• It is a simple algorithm
• it is inefficient for large values of n, where n is the size of the list.
• Can be easily implemented on linked lists

Question 7

Write down the Selection sort algorithm.

Answer 7

void selectionSort(int list[]) {
 \_\_\_\_int last = list.length;
 \_\_\_\_int maxPos;
 \_\_\_\_while (last > 0) {
 \_\_\_\_\_\_\_\_maxPos = findMax(list,last+1);
 \_\_\_\_\_\_\_\_swap(list,maxPos,last);
 \_\_\_\_\_\_\_\_last--;
 \_\_\_\_}
}

Question 8

WORST CASE selection sort

Answer 8

theta(n^2)

Question 9

Explain Insertion Sort :

Answer 9

The idea here is that we get an element and insert it in the position it belongs.

Used frequently when we want to generate another list with the elements
sorted

It can be also done in place, that is, without requiring an extra list

After each outer loop interaction one element in the list has been placed in his final location

Question 10

What performance do elementary algorithms have ?

Answer 10

Theta(n^2)

Question 11

Examples of elementary algorithms:

Answer 11

Insertion and selection sort

Question 12

Write an insertion sort algorithm :

Answer 12

void insertionSort(int list[]) {
 \_\_\_\_int pos = list.length-1;
 \_\_\_\_while (pos > 0) {
\_\_\_\_\_\_\_\_ indexNew = pos – 1;
 \_\_\_\_\_\_\_\_valueNew = list[indexNew];
\_\_\_\_\_\_\_\_\_while ((indexNew < list.length-1) &amp;&amp; 
\_\_\_\_\_\_\_\_\_\_\_\_(valueNew > list[indexNew+1])) {
 \_\_\_\_\_\_\_\_\_\_\_\_list[indexNew] = list[indexNew+1];
\_\_\_\_\_\_\_\_\_\_\_\_ indexNew++;
 \_\_\_\_\_\_\_\_}
 \_\_\_\_list[indexNew] = valueNew;
\_\_\_\_ pos--;
}

Question 13

Is insertion sort stable ?

Answer 13

dunno google it

Question 14

Is selection sort stable ?

Answer 14

dunno google it

Question 15

Bubble Sort:

Answer 15

Bubble sort is one of the simplest algorithms for sorting a list but also one of the slowest.

Theoretically speaking it has the same efficiency of selection sort

Question 16

Write a Bubble sort algorithm :

Answer 16

void bubbleSort(int list[]) {
 \_\_\_\_for (int i = list.length-1; i>0; i--){
 \_\_\_\_\_\_\_\_for (int pos = 0; pos < i; pos++) {
\_\_\_\_\_\_\_\_\_\_\_\_ if (list[pos] > list[pos+1]) {
 \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_swap(list,pos,pos+1);
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}
\_\_\_\_\_\_\_\_\_\_\_\_}
\_\_\_\_}
}

Question 17

Write a Bubble sort algorithm :

Answer 17

void bubbleSort(int list[]) {
 \_\_\_\_for (int i = list.length-1; i>0; i--){
 \_\_\_\_\_\_\_\_for (int pos = 0; pos < i; pos++) {
\_\_\_\_\_\_\_\_\_\_\_\_ if (list[pos] > list[pos+1]) {
 \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_swap(list,pos,pos+1);
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}
\_\_\_\_\_\_\_\_\_\_\_\_}
\_\_\_\_}
}

Question 18

Bubble sort Worst case :

Answer 18

THETA(n^2)

Question 19

Is bubble sort stable ?

Answer 19

dunno

Question 20

Quick sort average performance?

Answer 20

nlogn

Question 21

Explain Quick sort

Answer 21

It was invented by the English Scientist C.A.R. Hoare in 1961.

It is a divide and conquer algorithm.

This means that it conforms to the basic idea of:
• Solving the subproblems recursively
• And then combining the solution into a solution for the larger instance

Question 22

Who is Hoare?

Answer 22

Hoare is principal scientist at Microsoft Research in the UK

Question 23

Why is Quick sort one of the most popular sorting algorithms ?

Answer 23

• it is not difficult to implement

* it works well in a variety of situations – it is a good general purpose algorithm

Question 24

Advantages of Quicksort ?

Answer 24

• It is in-place and uses only a small stack as auxiliary structure (if recursion is used the stack is implicit)
• It works in O(n log n) in the average case

Question 25

Drawbacks of Quicksort?

Answer 25

• It is recursive (i.e. more costly)
• Implementation is more complicated without recursion
• It takes O(n2) in the worst case
• It is fragile.

Question 26

Steps of quicksort:

Answer 26

• Divide the list to be sorted into into two smaller sublists.

Conquer the smaller sublists either by calling the recursion for them or solving them with a straightforward approach if they are small enough

Combine the sorted lists of the subproblems into the solution for the large (original) problems

Question 27

What does it mean that quick sort is fragile ?

Answer 27

Difficult to improve or change because it might make the algorithm slower