[DSA] Sorting Algorithms

Basic Sorting Algorithms

1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Merge Sort

5. Quick Sort

6. Shell Sort

Bubble Sort

• Simple comparison-based algorithm

• Repeatedly swaps adjacent elements if they are in the wrong order

Selection Sort

• Selects the minimum (or maximum) and places it in the correct position

Insertion Sort

• Builds the sorted array one item at a time

Merge Sort

• Divide-and-conquer algorithm

• Recursively divides arrays and merges sorted halves

Quick Sort

• Divide-and-conquer algorithm

• Uses a pivot to partition the array

Shell Sort

• Generalization of insertion sort

• Sorts elements far apart first

Bubble Sort

• Concept: compare adjacent elements, and swap them if they’re in the wrong order. Repeat the process until the list is sorted.

Selection Sort

• Concept: find the smallest (or largest) element and move it to its correct position in the sorted part of the array.

Insertion Sort

• Concept: Build the sorted list one element at a time by inserting each new item into the correct position.

Merge Sort

• Concept: A divide-and-conquer algorithm.

• Divide the array into halves back together.

Quick Sort

• Concept: Also a divide-and-conquer algorithm.

• Choose a pivot, partition elements into smaller or larger than the pivot

• Recursively sort each side

Shell Sort

• A generalized insertion sort.

• Starts by comparing elements far apart, then reduces the gap.

• Final pass is a normal insertion sort with small gaps.

What is “Gap = 3”