ఇవి మూడు సరళమైన O(n²) సరిపోల్చే సార్టింగ్ అల్గోరిథమ్లు. అవి పెద్ద ఇన్పుట్ల కోసం నెమ్మదిగా ఉన్నాయి కానీ అర్థం చేసుకోవడానికి సులభమైనవి మరియు సార్టింగ్ యొక్క మెకానిక్ను నేర్పడానికి ఉపయోగపడతాయి.
ఇవి మూడు సరళమైన O(n²) సరిపోల్చే సార్టింగ్ అల్గోరిథమ్లు. అవి పెద్ద ఇన్పుట్ల కోసం నెమ్మదిగా ఉన్నాయి కానీ అర్థం చేసుకోవడానికి సులభమైనవి మరియు సార్టింగ్ యొక్క మెకానిక్ను నేర్పడానికి ఉపయోగపడతాయి.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to place
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift bigger elements right
j -= 1
arr[j + 1] = key # drop key into the gap
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| సార్ట్ | ఉత్తమ | చెత్త | స్థిరమైన | ఇన్-ప్లేస్ |
|---|---|---|---|---|
| బబుల్ | O(n) | O(n²) | అవును | అవును |
| సెలెక్షన్ | O(n²) | O(n²) | లేదు | అవును |
| ఇన్సర్షన్ | O(n) | O(n²) | అవును | అవును |
ఇన్సర్షన్ సార్ట్ చిన్న లేదా దాదాపు సార్ట్ చేసిన శ్రేణుల కోసం నిజమైన వేగవంతమైనది మరియు హైబ్రిడ్ సార్టింగ్ లోపల ఉపయోగించబడుతుంది. పెద్ద సార్ట్ చేయని డేటాపై మూడింటిని నివారించండి — బదులుగా O(n log n) సార్టింగ్ను ఉపయోగించండి.
ఈ సార్టింగ్లు మీరు ఆధునిక అల్గోరిథమ్లను చేపట్టే ముందు విరామాలు, స్వాపులు మరియు స్థిరత కోసం సహజానికి నిర్మిస్తాయి.
ఇన్సర్షన్ సార్ట్ చిన్న సబ్రేలకు ప్రోడక్షన్ సార్టింగ్ (టిమ్సార్ట్ వంటివి) లోపల ప్రత్యేకంగా కనిపిస్తుంది.
అవి ఎందుకు O(n²) అని తెలుసుకోవడం O(n log n) సార్టింగ్కి జంపు అర్థవంతంగా చేస్తుంది.