इंसर्शन सॉर्ट की समय जटिलता
- सर्वोत्तम स्थिति: O(n) - जब सरणी पहले से क्रमबद्ध हो
- औसत/सबसे खराब स्थिति: O(n²)
विशेष पैटर्न वाली सरणी के लिए समय जटिलता
सरणी: 6, 5, 8, 7, 10, 9, ... i, i-1
यहां प्रत्येक जोड़ी स्वैप है। इंसर्शन सॉर्ट प्रत्येक जोड़ी को एक ऑपरेशन में ठीक कर देगा। इसलिए समय जटिलता O(n) होगी।
इंसर्शन सॉर्ट कोड
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int element = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > element) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = element;
}
}