Sorting Algorithms

• Sorting is the operation of arranging the records of a table into some sequential order according to an ordering criterion.
• A simple sorting algorithm typically consists of two operations:

  • Compare operation
  • Swap operation
• Advantages of Sorting:

  • Data searching can be optimised
  • Improve readability
  • Processing of data is performed in a defined order
• Sorting is classified into 2 variants:

  • In-place sorting
  • Not-in-place sorting
• In-place sorting is an algorithm that does not need extra space and produces an output in the same memory that contains the data by transforming the inputted data.
• The 4 sorting algorithms are:

  • Bubble sort
  • Insertion sort
  • Quick sort
  • Merge sort
• Input the correct sorting algorithms:

  A) Insertion Sort

  B) Merge Sort

  C) Quick Sort

  D) Bubble Sort

  
• Time Complexity of Bubble Sort:

  Best Case: O( N )

  Average Case: O( N^2 )

  Worst Case: O( N^2 )
• Time Complexity of Insertion Sort:

  Best Case: O( N )

  Average Case: O( N^2 )

  Worst Case: O( N^2 )
• Time Complexity of Quick Sort:

  Best Case: O( N log_2 N )

  Average Case: O( N log_2 N )

  Worst Case: O( N^2 )
• Time Complexity of Merge Sort:

  Best Case: O( N log_2 N )

  Average Case: O( N log_2 N )

  Worst Case: O( N log_2 N )