Іріктеу сұрыпталуы және көпіршікті сұрыптау алгоритмдері

Мен бірнеше сұрыптау алгоритмін түсінуге тырысамын, бірақ көпіршікті сұрыптау мен кірістіру сұрыптау алгоритміндегі айырмашылықты көруге тырысамын.

Мен білемін, екеуі де O (n 2 ), бірақ менің ойымша, көпіршікті сұрыптау әр жиі үшін массивтің ең жоғарғы мәнін көбейтеді, ал кірістіру сұрыптауы ең төменгі мәнді әр өтуге арналған. Олар бірдей нәрсені істемейді, бірақ әртүрлі бағыттарда емес пе?

Кірістіру сұрыпталымы үшін салыстыру/әлеуетті своптар саны нөлден басталады және әрбір рет (яғни 0, 1, 2, 3, 4, ..., n) басталады, бірақ бұл мінез-құлықты көпіршікті түрде сұрыптау үшін, бірақ соңында сұрыптау (яғни, n, n-1, n-2, ... 0), себебі көпіршікті сұрыптау соңғы элементтермен салыстыру қажет емес.

Мұның бәрі үшін, әдетте, жалпыға ортақ енгізудің жақсы болуы туралы консенсус бар. Неліктен біреу маған айтады?

Edit: I'm primarily interested in the differences in how the algorithms work, not so much their efficiency or asymptotic complexity.

54
Бұл басқа жерде жақсы құжатталған: қараңыз, мысалы, en.wikipedia.org/wiki/Sorting_algorithm . Мұнда мұнда қайталанудың пайдасы жоқ және жақсы жауап кеңеюде болады.
қосылды автор Bathsheba, көзі

10 жауаптар

Іріктеуді сұрыптау

i кейін, бірінші i элементтері қайталанады.

Әрбір иерархияда келесі элемент дұрыс орынға жеткенше сұрыпталған секциясынан жыпылықтайды:

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

4 сұрыпталған бөлікке бұқтырылған

Псевдокод:

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

Көпіршікті сұрыптау

i кейін i элементтері ең үлкен болып табылады және оларды реттейді.

Әрбір иерархияда максимум табу үшін unsorted бөлімінен өтіңіз.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

5 сұрыпталмаған секциядан бұқтырылған

Псевдокод:

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

Сыртқы ілмектердің біреуінде ешқандай своптар жасалмаса, әдеттегі іске қосу ертерек тоқтатылады (бұл массив сұрыпталған).

Айырмашылық

In Іріктеуді сұрыптау elements are bubbled into the sorted section, while in Көпіршікті сұрыптау the maximums are bubbled out of the unsorted section.

89
қосылды
Плюс 1 айқындық үшін, дидактикалық мән және әрбір алгоритмнің негізгі циклдік инварианты үшін. Өкінішке орай, күрделіліктің салыстыруы ( n функциясы ретінде көрінеді), дегенмен, оны қабылданғаннан гөрі жақсы жауап деп санаймын, өйткені осыдан айырмашылықты қараңыз.
қосылды автор Honza Zidek, көзі
Менің ойымша, бұл ең жақсы жауап :)
қосылды автор Adelin, көзі
Рахмет, бұл өте анық! Менің ойымша, ең маңызды нәрсе, бұл break Insertion Sort ішіндегі мәлімдемесі әр иераратты ертерек тоқтатуы мүмкін дегенді білдіреді, яғни ол сұрыпталған бөлімде өз позициясын тапқан кезде. Көпіршікті сұрыптау сұрыпталмаған бөлімдегі ең үлкен элемент сұрыпталған бөлімге жеткенше алмастыруды жалғастыруды талап етеді, сондықтан ешқашан ертерек тоқтатылмайды. Бұл фантастикалық қорытынды болса да, +1
қосылды автор Miguel, көзі
@tom, тері, бәрі жақсы. Көп рақмет
қосылды автор Karoly, көзі
Сұрағым бар ма, сіз неге сіз өзіңіздің элементіңізді Сценарийлік Pseudo кодының әрбір қадамында ауыстырып отырсыз? егер (a [j-1]> a [j]), онда [j] = a [j-1] ELSE, егер (j-1) e) = e; үзіліс; , Онда е - зат сұрыптау қажет. Осы шешіммен бұрын сұрыпталған элементтерді ауыстырып, оларды көшіруге болмайды. Сізге түсініктеме беруді күтемін, себебі мен аздап шатастырып жатырмын.
қосылды автор Karoly, көзі
@Karoly, менің нұсқамды таңдадым, себебі ол қарапайым. Сенің сәл тезірек, сіз оны көрсететін жақсы. Wikipedia екі нұсқаны сипаттайды.
қосылды автор tom, көзі

Итерациядағы көпіршікті сұрыпта сізде n-1 ішкі итерациялары бар (n ^ 2)/2, бірақ кірістіру сұрыптауында i-ші қадамда максимум i иерациялары бар, бірақ i/2 орташа, бұрынғы элемент үшін дұрыс орын тапқаннан кейін. Сонымен, сізде (0-ден n-ға дейін)/2, яғни (n ^ 2)/4 барлығы;

Міне, сондықтан кірістіру сұрыптау көпіршікті сұрыптауға қарағанда жылдамырақ.

28
қосылды
Ал, сіз негіздерін түсінемін деп болжауға болады. Мен қалаған нәрсені салыстыру едім және бұл өте жақсы. Мәселен идея мынада, бұл кірістіру сұрыптау iith элементінің төмендеуіне әкеліп соқтырады, ал көпіршікті сұрыптау оны көпіршікке апарады, кірістіру сұрыптары ең төменгі деңгейге түсіп кетуіне әкелмейді, бұл жай ғана дұрыс орынға түседі қазірдің өзінде сұрыпталған бөлім. Осылайша, ол аз салыстырулар/своптар. Сол дұрыс па?
қосылды автор Miguel, көзі
жақсы, бірақ алгоритмдердің айырмашылығын түсіндірмейді.
қосылды автор UmNyobe, көзі
иә, бірақ ОР әлі де механизмдерді айыра алмайтындай көрінеді
қосылды автор UmNyobe, көзі
Ия, бұл дұрыс.
қосылды автор sasha.sochka, көзі
Алгоритмді түсіндіру вебте барлық жерде, менің ойымша.
қосылды автор sasha.sochka, көзі

Тағы бір айырмашылық, мен мұнда көрмедім:

Bubble sort has 3 value assignments per swap: you have to build a temporary variable first to save the value you want to push forward(no.1), than you have to write the other swap-variable into the spot you just saved the value of(no.2) and then you have to write your temporary variable in the spot other spot(no.3). You have to do that for each spot - you want to go forward - to sort your variable to the correct spot.

кірістіру сұрыптау көмегімен сіз айнымалы мәнді уақытша айнымалы бойынша сұрыптап, айнымалы мәніңізге дұрыс нүктеге жеткенде, барлық айнымалы мәндерді бұл нүктенің алдында 1 орынға кері қойыңыз. Бұл 1-ге тең мәнді тағайындауды етеді. Соңында өзіңіздің уақытша айнымалы мәнді жазыңыз.

Бұл да әлдеқайда арзан тапсырмаларды жасайды.

Бұл ең жылдам жылдамдық пайдасы емес, бірақ, менің ойымша, бұл туралы айтуға болады.

Менің ойымша, мен түсіндім, егер жоқ болса, өкініштісі, мен британдық емеспін

13
қосылды
«және содан кейін барлық айнымалы мәндерді сол нүктенің алдында 1 орын артқа қойыңыз» - және деректерді ауыстыру үшін тапсырмалар жүктемесін қажет етпейді ме? (деректер бір-бірімен байланыста сақталатын болса, байланыстырылған тізім болмаса)
қосылды автор Mark K Cowan, көзі
@MarkKCowan, иә, мұнда кірістіру сұрыптауы жоғарыда аталған пайдаланушы ретінде белгілеу үшін 'орынға' тағайындауды береді. Негізінен, кірістіру сортты ішкі циклде бір тағайындау арқылы жазуға болады, ал көпіршіктердің ішкі циклде 3 тағайындалуы бар.
қосылды автор JSQuareD, көзі

Кірістіру сұрыптауының басты артықшылығы - ол онлайн алгоритмі. Бастапқыда барлық мәндердің болуы міндетті емес. Бұл желіден немесе кейбір сенсордан алынған деректермен жұмыс істеген кезде пайдалы болуы мүмкін.

I have a feeling, that this would be faster than other conventional n log(n) algorithms. Because the complexity would be n*(n log(n)) e.g. reading/storing each value from stream (O(n)) and then sorting all the values (O(n log(n))) resulting in O(n^2 log(n))

Керісінше, ағынның мәндерін оқу үшін O (n) және O (n) мәндерін дұрыс орынға қою үшін, O (n ^ 2) ғана. Басқа артықшылығы - құндылықтарды сақтау үшін аралық сақтағыштардың қажеті жоқ, оларды соңғы орынға сұрыптау.

6
қосылды
Егер деректерді кезек-кезекке айналдыру массивді сканерлеуден өзгеше болса, онда сіз әлдеқайда тиімді түрде сұрыптауға болады. мысалы, элементтерді екілік ағашқа оларды қабылдаған кезде кірістіріңіз. Бұл сізге O (n log (n)) жолдың әрбір қадамында сұрыпталған жинақ үшін орындалатын жалпы жұмыс. (Кез-келген нүктеде кез-келген ретпен өту O (m) ). Егер сізге тек сұрыпталған нәтиже қажет болса, бірақ деректерді тасымалдау уақытын сұрыптау есептелуін қайталағысы келсе, Heap жақсы болуы мүмкін. (Орнына кірістіру-сұрыптау сияқты).
қосылды автор Peter Cordes, көзі
Қалай болғанда да, көпіршіктеу сұрыптамасы да, кірістіру-сұрыптау үшін де O (f (n)) күрделі класс үшін жеткілікті үлкен проблемалар мөлшері бар.
қосылды автор Peter Cordes, көзі
Түзету: Үйірме бұл үшін жақсы емес. Сұрыптау жұмыстарының көпшілігін сұрыпталған тәртіпте элементтерді алып тастаған кезде жасайды, сондықтан өсім өте арзан. Мұнда мақсат - соңғы элементтің уақыты келгенде орындалатын жұмыстардың көпшілігін алу.
қосылды автор Peter Cordes, көзі
Қалай болғанда да, сіз n кірістірулеріне сұрыпталған массивді сақтау керек болса, онда шын мәнінде ол ең жоғарғы сұрыпталған бір элемент бар сұрыпталған жиынды сұрыптау үшін қандай алгоритмнің жақсы екеніне байланысты қайнайды. Сұрыптау алгоритмдерінің көбі O (n log (n)) O (n) болып табылады, сондықтан сізге қажет sum (M = 1..n, O (M * log (M))) жұмыс істейді. Бұл шынымен O (n ^ 2 log (n)) болар еді, бірақ дұрыс таңдау алгоритмі O (n ^ 2) болады. Дегенмен, кірістіру-сұрыптау бұл үшін ең тиімді болып табылады.
қосылды автор Peter Cordes, көзі

Көпіршікті сұрыптау желіде емес (ол қанша элементті білмей, кіріс ағындарын сұрыптау мүмкін емес), себебі ол сұрыпталған элементтердің жаһандық максимумын бақыламайды. Егер элемент салынған болса, сіз ең басынан бастап бұралуды бастауыңыз керек

6
қосылды

Жақсы көпіршікті сұрыптау үлкен сандар тізімінен жоғарғы k элементтерін іздеген кезде ғана кірістіруді сұрыптаудан жақсы яғни көпіршікті сұрыптаулардан кейін, сіз k элементтерін табасыз. Содан кейін итерациядан кейін сұрыптау кезінде, ол тек қана элементтердің сұрыпталуына кепілдік береді.

3
қосылды

Әрине, екеуі де O (N ^ 2). Жасырын тұрақты мәндер Insertion сұрыптауында әлдеқайда аз. Қарапайым тұрақтыдар орындалатын қарабайыр әрекеттердің нақты санына сілтеме жасайды.

Іріктеу сұрыптауы жақсы жұмыс істеу уақыты болғанда?

  1. Массив дерлік сұрыпталған - кірістіру сұрыптау көпіршікті сұрыптаудан гөрі бұл жағдайда аз операциялар жасайтынын ескеріңіз.
  2. Массив салыстырмалы түрде аз мөлшерде: элементтерді жылжытуға ағымдағы элементті орналастыру үшін сұрыптау. Бұл элементтер санының аз болған жағдайда көпіршікті сұрыптаудан әлдеқайда жақсы.

Кірістіру сұрыптауы көпіршікті сұрыптауға қарағанда әрдайым жақсы емес екенін ескеріңіз. Екі әлемнің ең жақсы жолын табу үшін, массив кішкентай өлшемі болса, кірістіру сұрыптауын пайдалануға болады және үлкенірек массивтер үшін сұрыптау (немесе скворк) болуы мүмкін.

1
қосылды
Егер элементтердің саны аз болса, көпіршікті сұрыптау қалай жақсы болады? Менің түсінуімше, IS-ге ауысу немесе BS-дегі айырбастау элементі элементтердің салыстырмалы емес (IS) немесе аз (BS) екендігіне байланысты болады. Егер дұрыс емес болса, мені түзетіңіз.
қосылды автор Mustafa, көзі

Енгізу сұрыптауы « элементті бірінші орынға (ең аз) қарап, келесі элементтерді ауыстыру арқылы бірнеше орынды іздеңіз және оны бірінші орында қойыңыз.» Жақсы. 2-ші ... «және т.б.

Көпіршікті сұрыптау басқаша түрде жұмыс істейді, ол « Мен дұрыс емес тәртіпте екі іргелес элементтерді тапқан кезде оларды ауыстырамын ».

1
қосылды
Бұл кірістіруді сұрыптауға көмектеседі, бірақ көпіршікті сұрыптау түсініктемесі нақты ілмектерді қамтымайды, сондықтан оларды шынымен салыстыра алмаймын. Мен кірістіруді сұрыптау тиімді түрде ереже бар. Мен дұрыс емес тәртіпте екі іргелес элементтерді тапқан кезде, оларды ауыстырамын , осылайша циклдар басқаша жұмыс істейді.
қосылды автор Miguel, көзі
О, иә, бұл шындық
қосылды автор Miguel, көзі
Бұл іріктеу сұрауы емес пе?
қосылды автор harold, көзі

Барлық жағдайларда, көпіршікті сұрыптау іс жүзінде пайдасыз. Іріктеу сұрыптау тым көп своптар болуы мүмкін жағдайларда, іріктеу сұрыптау пайдаланылуы мүмкін, себебі бұл своптың N уақытынан аз болатындығына кепілдік береді. Таңдау сұрыптау көпіршікті сұрыптауға қарағанда жақсы болғандықтан, көпіршікті сұрыптау қолданылмайды.

1
қосылды

Әрбір итерацияда своп саны

  • Кірістіру-сұрыптау әр иерацияда 1 айырбастаумен .
  • Bubble-sort әр иерархияда 0-ден n свопты құрайды.

Сұрыпталған бөлікке кіру және өзгерту

  • Сұрыпталған бөлікке сәйкес санның дұрыс орналасуын табу үшін кірістіру-сұрыптауға рұқсат (және қажет болған жағдайда өзгертулер).
  • Оңтайландырылғанда, Bubble-sort сұрыпталған нәрсеге кірмейді.

Онлайн немесе жоқ

  • Кірістіру-сұрыптау - онлайн. Бұл Интреди-сұрыптау тиісті орынға қойғанға дейін бір уақытта бір кірісті қабылдайды дегенді білдіреді. Тек қана іргелес кірістерді салыстырудың қажеті жоқ.
  • Bubble-sort онлайн емес. Ол бір уақытта бір кірісті басқармайды. Ол әрбір иерархияда кірістердің тобын (бар болса да) өңдейді. Bubble-sort әр иерархияда тек аралас кірістерді салыстырыңыз және ауыстырыңыз.
0
қосылды