Python sorting algorithm

21. Sorting Algorithm

Article table of contents

• • 21. Sorting Algorithms
  • • 21.1 Algorithm Stability
    • 21.2 Classification
    • • 21.2.1 Stable Sorting Algorithm
      • 21.2.2 Unstable sorting algorithm
    • 21.3 Bubble Sort
    • • 21.3.1 Code Implementation
      • 21.3.2 Time Complexity
    • 21.4 Selection Sort
    • • 21.4.1 Code Implementation
      • 21.4.2 Time Complexity
    • 21.5 Insertion Sort
    • • 21.5.1 Code Implementation
      • 21.5.2 Time Complexity
    • 21.6 Quick Sort
    • • 21.6.1 Code Implementation
      • 21.6.2 Time Complexity

21.1 Algorithm Stability

Assuming that there are multiple records with the same keyword in the sequence of records to be sorted, if the relative order of these records remains unchanged after sorting, the sorting algorithm is said to be stable; otherwise, it is said to be unstable.stable

21.2 Classification

21.2.1 Stable Sorting Algorithm

• Bubble Sort
• Insertion Sort
• Merge Sort
• Radix sort

21.2.2 Unstable sorting algorithm

• Selection Sort
• Quick Sort
• Hill Sort
• Heapsort

21.3 Bubble Sort

21.3.1 Code Implementation

21.3.2 Time Complexity

• Worst

  • O(n2)

• Optimal

  • O(n)

21.4 Selection Sort

21.4.1 Code Implementation

21.4.2 Time Complexity

• Optimal

  • O(n2)

• Worst

  • O(n2)

21.5 Insertion Sort

21.5.1 Code Implementation

21.5.2 Time Complexity

• Optimal

  • O(n)

• Worst

  • O(n2)

21.6 Quick Sort

21.6.1 Code Implementation

21.6.2 Time Complexity

• Optimal

  • O(nlogn)

• Worst

  • O(n2)