Sorting Algorithms

Question 1

What is sorting?

Answer 1

• Determines how the data should be arranged in a specific order
• Taking an unordered collection and making it an ordered one
• Important due to
  
  • Optimised data searching to a high level
  • Readable data
• Dictionary + music tracks

Question 2

What is in place sorting?

Answer 2

• Program does not require any extra space
  
  • May store temp elements
• Sorting happens in the data structure in itself
• BUBBLE SORT

Question 3

What is non-in-plave sorting?

Answer 3

• Program requires extra space
• More than or equal to the elements being sorted
• MERGE SORT

Question 4

What is bubble sort?

Answer 4

• Compares adjacent array elements
  
  • Exchanging out of order values
• Larger values bubble up to the top of the array
  
  • Smaller values sink to the bottom
  • Keeps repeating until sorted
• $O(n^2)$ - SHIT TIME COMPLEXITY

Question 5

What is the psudocode for bubble sort?

Answer 5

Question 6

What is refined bubble sort?

Answer 6

• Checks if there is a need to sort
• Bubble up is less
• Allows for range of time complexity

Question 7

What is Merge Sort?

Answer 7

• Divide and conquer algorithm
• Keep halving until sub array only contains one element
• Merge sub problem solutions together
  
  • Compare
  • Remove smallest element
  • Put into result array
• Continue until result array is completed

Question 8

What is the psudocode for merge sort?

Answer 8