செருகும் வரிசைப்படுத்தல் நேர சிக்கலானது

பின்வரும் எண்களைக் கவனியுங்கள்:

50 60 30 10 80 70 20 40

இந்தப் பட்டியல் ஏறுவரிசையில் வரிசைப்படுத்தப்பட்டால், அது:

10 20 30 40 50 60 70 80

இது இறங்கு வரிசையில் வரிசைப்படுத்தப்பட்டால், அது:

80 70 60 50 40 30 20 10

செருகும் வரிசை என்பது ஒரு வரிசையாக்க அல்காரிதம் ஆகும், இது பட்டியலை ஏறுவரிசையில் அல்லது இறங்கு வரிசையில் வரிசைப்படுத்தப் பயன்படுகிறது. இந்த கட்டுரை ஏறுவரிசையில் வரிசைப்படுத்துவது பற்றி மட்டுமே கூறுகிறது. இந்த ஆவணத்தில் கொடுக்கப்பட்டுள்ள அதே தர்க்கத்தையே இறங்கு வரிசையில் வரிசைப்படுத்துவது. இந்த கட்டுரையின் நோக்கம் செருகும் வகையை விளக்குவதாகும். நிரலாக்கமானது C இல் பின்வரும் எடுத்துக்காட்டில் செய்யப்படுகிறது. ஒரு அணிவரிசையைப் பயன்படுத்தி செருகும் வரிசை இங்கே விளக்கப்பட்டுள்ளது.

செருகும் வரிசைக்கான அல்காரிதம்

வரிசைப்படுத்தப்படாத பட்டியல் கொடுக்கப்பட்டுள்ளது. அதே பட்டியலைப் பயன்படுத்தி பட்டியலை ஏறுவரிசையில் வரிசைப்படுத்துவதே இதன் நோக்கம். வரிசைப்படுத்தப்படாத வரிசையை அதே வரிசையைப் பயன்படுத்தி வரிசைப்படுத்துவது இடத்தில் வரிசைப்படுத்துவதாகக் கூறப்படுகிறது. பூஜ்ஜிய அடிப்படையிலான அட்டவணைப்படுத்தல் இங்கே பயன்படுத்தப்படுகிறது. படிகள் பின்வருமாறு:

• • பட்டியல் ஆரம்பத்தில் இருந்து ஸ்கேன் செய்யப்படுகிறது.
  • ஸ்கேனிங் நடந்து கொண்டிருக்கும் போது, ​​அதன் முன்னோடியை விட குறைவான எந்த எண்ணும் அதன் முன்னோடியுடன் மாற்றப்படும்.
  • மாற்றுவது சாத்தியமில்லாத வரை, இந்த ஸ்வாப்பிங் பட்டியலில் தொடர்கிறது.
  • ஸ்கேனிங் முடிவை அடையும் போது, ​​வரிசையாக்கம் முடிந்தது.

செருகும் வரிசை விளக்கம்

நேர சிக்கலைக் கையாளும் போது, ​​பொதுவாகக் கருத்தில் கொள்ளப்படும் மோசமான நிலை இதுவாகும். முந்தைய பட்டியலுக்கான மோசமான ஏற்பாடு:

80 70 60 50 40 30 20 10

பூஜ்ஜியத்திலிருந்து 7 வரையிலான குறியீடுகளுடன் எட்டு உறுப்புகள் உள்ளன.

குறியீட்டு பூஜ்ஜியத்தில், ஸ்கேனிங் 80 க்கு செல்கிறது. இது ஒரு இயக்கம். இந்த ஒரு இயக்கம் ஒரு செயல்பாடு. இதுவரை மொத்தம் ஒரு செயல்பாடு உள்ளது (ஒரு இயக்கம், ஒப்பீடு இல்லை மற்றும் இடமாற்று இல்லை). இதன் விளைவு:

| 80 70 60 50 40 30 20 10

குறியீட்டு ஒன்றில், 70 க்கு ஒரு இயக்கம் உள்ளது. 70 உடன் ஒப்பிடும்போது 80. 70 மற்றும் 80 மாற்றப்பட்டது. ஒரு இயக்கம் ஒரு செயல்பாடு. ஒரு ஒப்பீடு என்பது ஒரு செயல்பாடு. ஒரு இடமாற்று என்பதும் ஒரு செயல்பாடுதான். இந்த பிரிவு மூன்று செயல்பாடுகளை வழங்குகிறது. இதுவரை மொத்தம் நான்கு செயல்பாடுகள் உள்ளன (1 + 3 = 4). முடிவு பின்வருமாறு:

70 | 80 60 50 40 30 20 10

குறியீட்டு இரண்டில், 60 க்கு ஒரு இயக்கம் உள்ளது. 60 80 உடன் ஒப்பிடப்படுகிறது, பின்னர் 60 மற்றும் 80 ஆகியவை மாற்றப்படுகின்றன. 60 என்பது 70 உடன் ஒப்பிடப்படுகிறது, பின்னர் 60 மற்றும் 70 ஆகியவை மாற்றப்படுகின்றன. ஒரு இயக்கம் ஒரு செயல்பாடு. இரண்டு ஒப்பீடுகள் இரண்டு செயல்பாடுகள். இரண்டு பரிமாற்றங்கள் இரண்டு செயல்பாடுகள். இந்த பிரிவு ஐந்து செயல்பாடுகளை வழங்குகிறது. இதுவரை மொத்தம் ஒன்பது செயல்பாடுகள் உள்ளன (4 + 5 = 9). முடிவு பின்வருமாறு:

60 70 | 80 50 40 30 20 10

குறியீட்டு மூன்றில், 50 க்கு ஒரு இயக்கம் உள்ளது. 50 80 உடன் ஒப்பிடப்படுகிறது, பின்னர் 50 மற்றும் 80 மாற்றப்படும். 50 என்பது 70 உடன் ஒப்பிடப்படுகிறது, பின்னர் 50 மற்றும் 70 ஆகியவை மாற்றப்படுகின்றன. 50 60 உடன் ஒப்பிடப்படுகிறது, பின்னர் 50 மற்றும் 60 மாற்றப்படுகிறது. ஒரு இயக்கம் ஒரு செயல்பாடு. மூன்று ஒப்பீடுகள் மூன்று செயல்பாடுகள். மூன்று பரிமாற்றங்கள் மூன்று செயல்பாடுகள். இந்த பிரிவு ஏழு செயல்பாடுகளை வழங்குகிறது. இதுவரை மொத்தம் பதினாறு செயல்பாடுகள் உள்ளன (9 + 7 = 16). முடிவு பின்வருமாறு:

50 60 70 | 80 40 30 20 10

குறியீட்டு நான்கில், 40 க்கு ஒரு இயக்கம் உள்ளது. 40 80 உடன் ஒப்பிடப்படுகிறது, பின்னர் 40 மற்றும் 80 ஆகியவை மாற்றப்படுகின்றன. 40 70 உடன் ஒப்பிடப்படுகிறது, பின்னர் 40 மற்றும் 70 மாற்றப்படுகின்றன. 40 60 உடன் ஒப்பிடப்படுகிறது, பின்னர் 40 மற்றும் 60 மாற்றப்படுகின்றன. 40 ஐ 50 உடன் ஒப்பிடப்படுகிறது, பின்னர் 40 மற்றும் 50 மாற்றப்படுகின்றன. ஒரு இயக்கம் ஒரு செயல்பாடு. நான்கு ஒப்பீடுகள் நான்கு செயல்பாடுகள். நான்கு பரிமாற்றங்கள் நான்கு செயல்பாடுகள். இந்த பிரிவு ஒன்பது செயல்பாடுகளை வழங்குகிறது. இதுவரை மொத்தம் இருபத்தைந்து செயல்பாடுகள் உள்ளன (16 + 9 = 25). முடிவு பின்வருமாறு:

40 50 60 70 80 | 30 20 10

குறியீட்டு ஐந்தில், 30 க்கு ஒரு இயக்கம் உள்ளது. 30 80 உடன் ஒப்பிடப்படுகிறது, பின்னர் 30 மற்றும் 80 ஆகியவை மாற்றப்படுகின்றன. 30 70 உடன் ஒப்பிடப்படுகிறது, பின்னர் 30 மற்றும் 70 மாற்றப்படுகின்றன. 30 என்பது 60 உடன் ஒப்பிடப்படுகிறது, பின்னர் 30 மற்றும் 60 ஆகியவை மாற்றப்படுகின்றன. 30 ஐ 50 உடன் ஒப்பிடப்படுகிறது, பின்னர் 30 மற்றும் 50 மாற்றப்படுகின்றன. 30 40 உடன் ஒப்பிடப்படுகிறது, பின்னர் 30 மற்றும் 40 மாற்றப்படுகின்றன. ஒரு இயக்கம் ஒரு செயல்பாடு. ஐந்து ஒப்பீடுகள் ஐந்து செயல்பாடுகள். ஐந்து பரிமாற்றங்கள் ஐந்து செயல்பாடுகள். இந்த பிரிவு பதினொரு செயல்பாடுகளை வழங்குகிறது. இதுவரை மொத்தம் முப்பத்தாறு செயல்பாடுகள் உள்ளன (25 + 11 = 36). முடிவு பின்வருமாறு:

30 40 50 60 70 80 | 20 10

குறியீட்டு ஆறில், 20 க்கு ஒரு இயக்கம் உள்ளது. 20 80 உடன் ஒப்பிடப்படுகிறது, பின்னர் 20 மற்றும் 80 ஆகியவை மாற்றப்படுகின்றன. 20 என்பது 70 உடன் ஒப்பிடப்படுகிறது, பின்னர் 20 மற்றும் 70 ஆகியவை மாற்றப்படுகின்றன. 20 ஆனது 60 உடன் ஒப்பிடப்படுகிறது, பின்னர் 20 மற்றும் 60 ஆகியவை மாற்றப்படுகின்றன. 20 ஐ 50 உடன் ஒப்பிடப்படுகிறது, பின்னர் 20 மற்றும் 50 மாற்றப்படுகின்றன. 20 40 உடன் ஒப்பிடப்படுகிறது, பின்னர் 20 மற்றும் 40 மாற்றப்படுகின்றன. 20 ஆனது 30 உடன் ஒப்பிடப்படுகிறது, பின்னர் 20 மற்றும் 30 ஆகியவை மாற்றப்படுகின்றன. ஒரு இயக்கம் ஒரு செயல்பாடு. ஆறு ஒப்பீடுகள் ஆறு செயல்பாடுகள். ஆறு பரிமாற்றங்கள் ஆறு செயல்பாடுகள். இந்த பிரிவு பதின்மூன்று செயல்பாடுகளை வழங்குகிறது. இதுவரை மொத்தம் நாற்பத்தொன்பது செயல்பாடுகள் உள்ளன (36 + 13 = 49). முடிவு பின்வருமாறு:

20 30 40 50 60 70 80 | 10

குறியீட்டு ஏழில், 10 க்கு ஒரு இயக்கம் உள்ளது. 10 80 உடன் ஒப்பிடப்படுகிறது, பின்னர் 10 மற்றும் 80 ஆகியவை மாற்றப்படுகின்றன. 10 ஐ 70 உடன் ஒப்பிடப்படுகிறது, பின்னர் 10 மற்றும் 70 ஆகியவை மாற்றப்படுகின்றன. 10 60 உடன் ஒப்பிடப்படுகிறது, பின்னர் 10 மற்றும் 60 ஆகியவை மாற்றப்படுகின்றன. 10 ஐ 50 உடன் ஒப்பிடப்படுகிறது, பின்னர் 10 மற்றும் 50 ஆகியவை மாற்றப்படுகின்றன. 10 30 உடன் ஒப்பிடப்படுகிறது, பின்னர் 10 மற்றும் 40 மாற்றப்படுகின்றன. 10 30 உடன் ஒப்பிடப்படுகிறது, பின்னர் 10 மற்றும் 30 ஆகியவை மாற்றப்படுகின்றன. 10 என்பது 20 உடன் ஒப்பிடப்படுகிறது, பின்னர் 10 மற்றும் 20 ஆகியவை மாற்றப்படுகின்றன. ஒரு இயக்கம் ஒரு செயல்பாடு. ஏழு ஒப்பீடுகள் ஏழு செயல்பாடுகள். ஏழு பரிமாற்றங்கள் ஏழு செயல்பாடுகள். இந்த பிரிவு பதினைந்து செயல்பாடுகளை வழங்குகிறது. இதுவரை மொத்தம் அறுபத்து நான்கு செயல்பாடுகள் உள்ளன (49 + 15 = 64). முடிவு பின்வருமாறு:

10 20 30 40 50 60 70 80 10 |

வேலை முடிந்தது! 64 அறுவை சிகிச்சைகள் ஈடுபட்டன.

64 = 8 x 8 = 8 ^{இரண்டு}

செருகும் வரிசைக்கான நேரச் சிக்கலானது

செருகும் வரிசையுடன் வரிசைப்படுத்த n உறுப்புகள் இருந்தால், முன்பு காட்டப்பட்டபடி, அதிகபட்ச செயல்பாடுகள் n2 ஆக இருக்கும். செருகும் வரிசை நேர சிக்கலானது:

ஓ(என் ^{இரண்டு} )

இது Big-O குறியீட்டைப் பயன்படுத்துகிறது. பிக்-ஓ குறியீடு O உடன் பெரிய எழுத்தில் தொடங்குகிறது, அதைத் தொடர்ந்து அடைப்புக்குறிக்குள். அடைப்புக்குறிக்குள் அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகளுக்கான வெளிப்பாடு உள்ளது.

C இல் குறியீட்டு முறை

ஸ்கேன் ஆரம்பத்தில், முதல் உறுப்பு அதன் நிலையை மாற்ற முடியாது. நிரல் அடிப்படையில் பின்வருமாறு:

insertionSort() செயல்பாடு வரையறை விவரிக்கப்பட்டுள்ளபடி அல்காரிதத்தைப் பயன்படுத்துகிறது. போது-லூப்பிற்கான நிபந்தனைகளைக் கவனியுங்கள். இந்த திட்டத்திற்கான பொருத்தமான சி முக்கிய செயல்பாடு:

முடிவுரை

செருகும் வரிசைக்கான நேர சிக்கலானது பின்வருமாறு கொடுக்கப்பட்டுள்ளது:

ஓ(என் ^{இரண்டு} )

மோசமான நேர நேர சிக்கலானது, சராசரி வழக்கு நேர சிக்கலானது மற்றும் சிறந்த சந்தர்ப்ப நேர சிக்கலானது பற்றி வாசகர் கேள்விப்பட்டிருக்கலாம். செருகும் வரிசைப்படுத்தும் நேர சிக்கலின் இந்த மாறுபாடுகள் எங்கள் வலைத்தளத்தின் அடுத்த கட்டுரையில் விவாதிக்கப்படும்.