Sorting Algorithms in Depth Preparation Notes

  • Classification of Data

    • Importance of considering stability in sorting algorithms.
    • Stable sorting retains the order of duplicate elements; Unstable does not.
    • Example of stability: Contest predicting jars of pennies, where ties may occur.
    • Ties are sorted based on original timestamps for stability.

  • Sorting Techniques Overview

    • Five different sorting techniques will be discussed.
    • Importance of understanding the difference between selection sort, insertion sort, and others.

  • Selection Sort

    • A sorting technique for arranging elements in ascending order.
    • In each pass, the smallest element is selected and placed in the first available position.
    • Example:
    • Given list: [36, 10, 12, 24, 6]
    • First pass selects 6, swaps with 36, resulting in [6, 10, 12, 24, 36].
    • It continues finding the minimum for subsequent passes.
    • Complexity of Selection Sort:
    • Each element is compared with all other elements.
    • Total comparisons in worst case: N2N^2, where N is the number of elements.
    • Total comparisons = N - 1 + N - 2 + … + 1 = rac{N(N-1)}{2}

  • Bubble Sort

    • Elements are compared in pairs, and larger elements