Sorting Algorithms

Question 1

Sorting definition (1)

Answer 1

1.) Arranging elements in a collection in increasing or decreasing order based on certain properties.

Question 2

Why is sorting important (3)

Answer 2

1. ) Some algorithms require sorted lists.
2. ) To normalise and standardise data.
3. ) To make searching easier.

Question 3

Classification of sorting algorithms (4)

Answer 3

1. ) Time complexity.
2. ) Stability.
3. ) Memory usage.
4. ) Recursion

Question 4

Bubble/Ripple sort (3)

Answer 4

1. ) Brute force.
2. ) Stable.
3. ) In place.

Question 5

Bubble/Ripple how (3)

Answer 5

1. ) Compares adiacent elements in an array.
2. ) If out of order swaps them, else go on.
3. ) Continues until no swaps happen in one full pass.

Question 6

Bubble/Ripple | Big O (2)

Answer 6

1. ) Best: O(n)

2. ) Worst/Average: O( n^2 )

Question 7

Merge sort (1)

Answer 7

1.) Divide and conquer.

Question 8

Merge sort how (2)

Answer 8

1. ) Divide list in n sub lists of 1 element.

2. ) Reunite sublists recursively, placing each element in the right order.

Question 9

Merge | Big O (1)

Answer 9

1.) O( n log(n) )

Question 10

Quicksort/Partition-Exchange sort (2)

Answer 10

1. ) Divide and conquer

2. ) In-place

Question 11

Quicksort how (5)

Answer 11

1. ) Select a pivot.
2. ) Scan array from two ends.
3. ) From left, it looks for elements bigger than the pivot. From right it looks for elements smaller than the pivot.
4. ) When it finds a element to swap it waits for the other side to find one and then swaps.
5. ) Repeat step 1 until one element left in the list.

Question 12

Quicksort Big O (2)

Answer 12

1. ) Best/Average: O( n log(n) )

2. ) Worst: O ( n^2 )

Question 13

Memory usage (1)

Answer 13

An algorithm is defined as in-place if it doesn’t require the creation of temporary memory spaces.

Question 14

What is Stability (1)

Answer 14

A stable algorithm will maintain the original order of two entries with the same value of the property.