[Powered by Google Translate] [Пузырьковый сартавання]
[JACKSON Steinkamp HARVARD UNIVERSITY]
[Гэта CS50. CS50TV]
Bubble Сартаванне прыклад алгарытму сартавання -
гэта значыць, парадак сартавання набор элементаў у
ўзрастанні або па змяншэнні.
Напрыклад, калі вы хочаце адсартаваць масіў, які складаецца з лікаў
[3, 5, 2, 9], правільнае прымяненне пузырьковый сартавання вернецца
спарадкаваны масіў [2, 3, 5, 9] ў парадку ўзрастання.
Зараз, я збіраюся растлумачыць, у псевдокоде, як працуе алгарытм.
>> Скажам, мы сартаванне спіс з 5 лічбаў - 3, 2, 9, 6 і 5.
Алгарытм пачынаецца, гледзячы на ​​першыя два элемента, 3 і 2,
і праверкі, калі яны выйшлі з ладу ў адносінах адзін да аднаго.
Яны - 3 больш, чым 2.
Каб быць у парадку ўзрастання, яны павінны быць наадварот.
Такім чынам, мы памяняць іх месцамі.
Зараз спіс выглядае наступным чынам: [2, 3, 9, 6, 5].
>> Далей мы паглядзім на другі і трэці элементы, 3 і 9.
Яны ў правільным парадку адносна адзін аднаго.
Гэта значыць, 3 менш, чым 9, так што алгарытм не памяняць іх месцамі.
Далей, мы глядзім на 9 і 6. Яны выйшлі з ладу.
>> Такім чынам, нам трэба, каб памяняць іх месцамі, таму што 9 больш, чым 6.
Нарэшце, мы паглядзім на апошнія два цэлых ліку, 9 і 5.
Яны выйшлі з ладу, таму яны павінны быць замененыя.
Пасля першага поўнага праходу па спісе,
гэта выглядае так: [2, 3, 6, 5, 9].
Не дрэнна. Гэта амаль адсартаваны.
Але нам трэба запусціць праз спіс яшчэ раз, каб атрымаць яго цалкам адсартаваны.
Два менш, чым 3, таму мы не памяняць іх месцамі.
>> Тры складае менш за 6, так што мы не памяняць іх месцамі.
Шэсць перавышае 5. Мы памяняліся месцамі.
Шэсць менш, чым 9. Мы не памяняць.
Пасля другой праход, яна выглядае наступным чынам: [2, 3, 5, 6, 9]. Perfect.
Цяпер, давайце запішам яго ў псевдокоде.
У прынцыпе, для кожнага элемента ў спісе, мы павінны глядзець на гэта
і элемент непасрэдна ў сваім праве.
Калі яны не ў парадку адносна адзін аднаго - гэта значыць, калі элемент злева
больш, чым той, на правым - мы павінны памяняць месцамі два элемента.
>> Мы робім гэта для кожнага элемента спісу, і мы зрабілі адзін праход.
Цяпер мы проста павінны зрабіць скразной дастатковую колькасць разоў, каб пераканацца, што спіс
цалкам, правільна сартуюцца.
Але колькі разоў мы павінны прайсці праз спіс
гарантаваць, што мы зрабілі?
Ну, горшым выпадку, калі мы маем зусім адваротны спісу.
Тады яна прымае шэраг прайсці прахадныя роўна ліку
элементаў N-1.
Калі гэта не мае сэнсу, інтуітыўна, думаю просты выпадак - спіс [2, 1].
>> Гэта будзе ўзяць адзін праход, каб адсартаваць правільна.
[3, 2, 1] - У горшым выпадку ў тым, што з 3 элементы сартуюцца ў зваротным кірунку,
ён збіраецца ўзяць 2 ітэрацый для сартавання.
Пасля адной ітэрацыі, гэта [2, 1, 3].
Другі дае спарадкаваны масіў [1, 2, 3].
Такім чынам, вы ведаеце, ніколі не павінны ісці праз масіў, у агульным,
больш, чым N-1 раз, дзе п-лік элементаў у масіве.
Гэта называецца Bubble Сартаванне таму, што найбуйнейшыя элементы, як правіла, «бурбалка уверх"
справа даволі хутка.
На самай справе, гэты алгарытм мае вельмі цікавае паводзіны.
>> Пасля т ітэрацый праз увесь масіў,
правыя элементы м гарантавана
павінны быць адсартаваныя ў іх правільным месцы.
Калі вы хочаце ў гэтым пераканацца,
мы можам паспрабаваць яго на зусім адваротны спіс [9, 6, 5, 3, 2].
Пасля аднаго праходу праз увесь спіс,
[Гук пісьмовай форме]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
правы элемент 9 знаходзіцца ў належным месцы.
Пасля другой праход, 6 будзе мець "прапускаюць уверх", каб
другую справа месца.
Гэтыя два элемента справа - 6 і 9 - будзе ў іх правільных месцах
Пасля першых двух праход прахадныя.
>> Такім чынам, як мы можам выкарыстоўваць гэта, каб аптымізаваць алгарытм?
Ну, а пасля адной ітэрацыі па масіве
Мы на самой справе не трэба правяраць правы элемент
таму што мы ведаем, што гэта адсартаваныя.
Пасля двух ітэрацый, мы ведаем напэўна, самая правая з двух элементаў на месцы.
Так, у агульным, пасля да ітэрацый поўны масіў,
Праверка апошняга да элементаў з'яўляецца залішнім, так як мы ведаем,
яны ў патрэбным месцы ўжо.
>> Так што калі вы сартавання масіва з п элементаў,
на першай ітэрацыі - вы будзеце мець, каб адсартаваць усе элементы - першыя п-0.
На другі ітэрацыі, вы павінны глядзець на ўсе элементы, акрамя апошняга -
1. N-1.
Іншая аптымізацыя можа быць, каб праверыць, калі спіс ужо адсартаваны
пасля кожнай ітэрацыі.
Калі ён ужо адсартаваныя, мы не павінны зрабіць больш ітэрацый
па спісе.
Як мы можам гэта зрабіць?
Ну, калі мы не робім ніякіх свопов на прахадной частцы спісу,
ясна, што гэты спіс быў ужо адсартаваны, таму што мы не змяняць нічога.
Такім чынам, мы, безумоўна, не павінны сартаваць зноў.
>> Можа быць, вы маглі б ініцыялізаваць сцяг пераменная называецца "Не Сартаваць да
ілжывымі і змяніць яго на праўдзівы калі ў вас ёсць, каб абмяняць любыя элементы на
адна ітэрацыя па масіве.
Ці аналагічна, зрабіць сустрэчную падлічыць, колькі свопов вы робіце
на любой ітэрацыі.
У канцы ітэрацыі, калі не памяняць любой з элементаў,
Вы ведаеце, у спіс ужо адсартаваны, і ўсё гатова.
Bubble Сартаванне, як і іншыя алгарытмы сартавання, можа быць
пераробленыя, каб працаваць для любых элементаў, якія маюць замовы метадам.
>> Гэта значыць, пры наяўнасці двух элементаў у вас ёсць спосаб сказаць, калі першая
больш, роўна або менш, чым другі.
Напрыклад, вы можаце адсартаваць літары алфавіту, сказаўшы,
, Што <B, B <C, і г.д.
Ці вы можаце адсартаваць дні тыдня, дзе нядзелю лічыцца менш панядзелка
што менш, чым у аўторак.
>> Bubble Сартаванне зусім не вельмі эфектыўныя або хуткі алгарытм сартавання.
У найгоршым выпадку час працы ад батарэй Big O н ²
таму што вы павінны зрабіць п ітэрацый па спісе
праверка ўсіх п элементаў, кожны праход, пхп = п ².
Гэты час выканання азначае, што як лік элементаў, вы сартаванні павялічваецца,
час выканання павялічваецца квадратычна.
>> Але калі эфектыўнасць не з'яўляецца галоўнай клопатам вашай праграмы
або калі вы толькі сартаванне невялікага колькасці элементаў,
Вы маглі б знайсці Bubble Сартаванне карысна, таму што
гэта адзін з найпростых алгарытмаў сартавання, каб зразумець
і код.
Гэта таксама выдатны спосаб атрымаць вопыт працы з перакладам тэарэтычных
алгарытм ў рэальным кодзе функцыянавання.
Ну, вось і пузырьковый сартавання для вас. Дзякуй за прагляд.
CS50.TV