Ішкі сұрыптау - Internal sort

Ан ішкі сұрыптау толығымен ішінде болатын кез-келген деректерді сұрыптау процесі болып табылады негізгі жад компьютердің Бұл сұрыпталатын мәліметтер негізгі жадта сақталатындай аз болған сайын мүмкін болады. Үлкен деректер жиынтығын сұрыптау үшін бір уақытта жадында тек қана мәліметтердің бір бөлігін сақтау қажет болуы мүмкін, өйткені олардың барлығы сәйкес келмейді. Қалған деректер, әдетте, қатты диск сияқты үлкенірек, бірақ баяуырақ ортада сақталады. Осы баяу тасымалдағышқа және одан деректерді кез-келген оқу немесе жазу сұрыптау процесін едәуір баяулатуы мүмкін. Бұл мәселенің әртүрлі мәні бар алгоритмдерді сұрыптау.

Кейбір ішкі сұрыптау алгоритмдеріне мыналар жатады:

  1. Көпіршікті сұрыптау
  2. Кірістіруді сұрыптау
  3. Жылдам сұрыптау
  4. Үймеде сұрыптау
  5. Радиус сұрыптау
  6. Таңдауды сұрыптау

Қарастырайық Bubblesort, онда көршілес жазбалар оларды дұрыс тәртіпке келтіру үшін ауыстырылады, осылайша жазбалар деректер кеңістігі арқылы жоғары және төмен «көпіршік» болып көрінеді. Егер мұны бөліктермен жасау керек болса, онда біз барлық жазбаларды 1-бөлікке сұрыптағаннан кейін, біз 2-ші бөлікке көшеміз, бірақ 1-ші жазбадағы кейбір жазбалар 2-ші бөлікке «көпіршік» жіберуі керек екенін білеміз. керісінше (яғни, 2-бөлімде 1-бөлікке жататын жазбалар, 2-ші немесе одан кейінгі бөліктерде болатын 1-ші жазбалар бар). Бұл бөлімдерді бірнеше рет оқуға және дискке жазуға мәжбүр етеді, өйткені жазбалар олардың арасындағы шекараны кесіп өтіп, өнімділіктің айтарлықтай нашарлауына әкеледі. Егер деректерді жадта бір үлкен бөлік ретінде сақтауға болатын болса, онда бұл өнімділікке жол берілмейді.

Екінші жағынан, кейбір алгоритмдер жұмыс істейді сыртқы сұрыптау жақсырақ. A Сұрыптауды біріктіру деректерді бөліктерге бөледі, басқа алгоритм бойынша бөліктерді сұрыптайды (мүмкін көпіршіктер немесе Жылдам сұрыптау ), содан кейін бөлшектерді екі-екіден біріктіреді, осылайша әрбір рекомбинацияланған бөлік ретімен орналасады. Бұл тәсіл дискідегі деректердің санын азайтады немесе оқиды және жазады және сұрыптаудың танымал әдісі болып табылады.