Сорттоо – an objectтерде аткарылуучу иш-аракеттердин же аракеттердин негизги түрлөрүнүн бири. Бала кезинде да балдарды иргеп, ой жүгүртүүсүн өрчүтүүгө үйрөтүшөт. Компьютерлер жана программалар да четте калbyte. Алгоритмдердин көп түрдүүлүгү бар. Мен алардын эмне экенин жана кантип иштешин карап чыгууну сунуштайм. Андан тышкары, бир күнү сизден интервьюда булардын бири жөнүндө сурашсачы?
Материалдар:
L совпадёт с
Киришүү
Элементтерди сорттоо - иштеп чыгуучу көнүшү керек болгон алгоритмдердин категорияларынын бири. Эгер бир кезде мен окуп жүргөндө информатикага анчалык маани берилбесе, азыр мектепте сорттоо алгоритмдерин ишке ашырып, түшүнүшү керек. Негизги алгоритмдер, эң жөнөкөйлөрү цикл аркылуу ишке ашырылатfor
. Албетте, элементтердин жыйнагын, мисалы, массивди иреттөө үчүн, бул коллекцияны кандайдыр бир жол менен басып өтүшүңүз керек. Мисалы:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Бул codeдун бөлүгү жөнүндө эмне айта аласыз? int i
Бизде индекстин маанисин ( ) 0дөн массивдин акыркы элементине өзгөрткөн цикл бар . Чынында, биз жөн гана массивдин ар бир элементин алып, анын мазмунун басып чыгарабыз. Массивдеги элементтер канчалык көп болсо, codeдун аткарылышы ошончолук көп убакытты талап кылат. Башкача айтканда, эгерде n элементтердин саны болсо, анда n=10 болгондо программаны аткаруу n=5ке караганда 2 эсе көп убакытты талап кылат. Биздин программада бир цикл болгондо, аткаруу убактысы сызыктуу көбөйөт: элементтер канчалык көп болсо, аткаруу ошончолук узак болот. Жогорудагы codeдун алгоритми сызыктуу убакытта (n) иштейт экен. Мындай учурларда, "алгоритмдин татаалдыгы" O(n) деп айтылат. Бул белги "чоң О" же "ассимптотикалык жүрүм-турум" деп да аталат. Бирок сиз жөн гана "алгоритмдин татаалдыгын" эстей аласыз.
Эң жөнөкөй сорттоо (Bubble Sort)
Ошентип, бизде массив бар жана аны кайталай алабыз. Абдан жакшы. Келгиле, эми аны өсүү тартибинде иреттөөгө аракет кылалы. бул биз үчүн эмнени билдирет? Бул эки элементтин берилгендигин билдирет (мисалы, a=6, b=5), эгерде а bдан чоң болсо (эгерде a > b болсо) а менен бди алмаштыруу керек. Индекс боюнча жыйнак менен иштөөдө бул биз үчүн эмнени билдирет (массивдегидей)? Бул, эгерде a индекси бар элемент b индекси бар элементтен чоң болсо, (массив[a] > массив[b]), мындай элементтерди алмаштыруу керек. Орундарды алмаштыруу көбүнчө своп деп аталат. Жерди алмаштыруунун ар кандай жолдору бар. Бирок биз жөнөкөй, түшүнүктүү жана эстеп калууга оңой codeду колдонобуз:private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Эми биз төмөнкүлөрдү жаза алабыз:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Көрүнүп тургандай, элементтер чындап эле ордун алмаштырган. Биз бир элементтен баштадык, анткени... эгерде массив бир эле элементтен турса, 1 < 1 туюнтмасы чындыкка кайтарылbyte жана ошентип биз массивдин бир элементи бар же аларсыз болгон учурларынан өзүбүздү коргойбуз жана code жакшыраак көрүнөт. Бирок биздин акыркы массив баары бир иреттелген эмес, анткени... Баарын бир өтмөктө иреттөө мүмкүн эмес. Биз башка циклди кошууга туура келет, анда биз сорттолгон массивге ээ болмоюнча бир-бирден өтүүлөрдү жасайбыз:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Ошентип, биздин биринчи сорттоо иштеди. while
Мындан ары кайталоонун кереги жок деп чечмейинче, тышкы циклде ( ) кайталайбыз . Демейки боюнча, ар бир жаңы итерациядан мурун, биз массивибиз иреттелген деп ойлойбуз жана мындан ары итерациялоону каалабайбыз. Ошондуктан, биз элементтерди ырааттуулук менен карап чыгып, бул божомолду текшеребиз. Бирок элементтер иштебей калса, биз элементтерди алмаштырып, элементтердин азыр туура тартипте экенине ишенбей турганыбызды түшүнөбүз. Ошондуктан, биз дагы бир итерацияны аткаргыбыз келет. Мисалы, [3, 5, 2]. 5 үчтөн көп, баары жакшы. Бирок 2 5тен аз. Бирок, [3, 2, 5] дагы бир өтүүнү талап кылат, анткени 3 > 2 жана аларды алмаштыруу керек. Циклдин ичинде цикл колдонгондуктан, алгоритмибиздин татаалдыгы жогорулайт экен. n элемент менен n * n болот, башкача айтканда O(n^2). Бул татаалдык квадраттык деп аталат. Биз түшүнгөндөй, канча итерация керек болорун так биле албайбыз. Алгоритмдин татаалдыгынын көрсөткүчү татаалдыктын өсүү тенденциясын көрсөтүү максатында кызмат кылат, эң начар учур. Элементтердин саны n өзгөргөндө иштөө убактысы канчага көбөйөт. Булбул сорттоо эң жөнөкөй жана эффективдүү эмес түрлөрдүн бири. Аны кээде "акылсыз сорттоо" деп да коюшат. Тиешелүү материал:
Тандоо сорттоо
Дагы бир түрү - тандоо сорту. Ал ошондой эле квадраттык татаалдыкка ээ, бирок бул жөнүндө кийинчерээк. Ошентип, идея жөнөкөй. Ар бир өтүү эң кичине элементти тандап, аны башына жылдырат. Бул учурда, ар бир жаңы өтүүнү оңго жылдыруу менен баштаңыз, башкача айтканда, биринчи өтүүнү - биринчи элементтен, экинчи өтүүнү - экинчиден. Ал мындай болот:int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Бул сорттоо туруксуз, анткени окшош элементтер (элементтерди сорттогон мүнөздөмөнүн көз карашынан алганда) алардын абалын өзгөртө алат. Жакшы мисал Wikipedia макаласында келтирилген: Сорттоо_боло-тандоо . Тиешелүү материал:
Insertion Sort
Кыстаруу сортунун да квадраттык татаалдыгы бар, анткени бизде циклдин ичинде дагы цикл бар. Ал тандоо сортунан эмнеси менен айырмаланат? Бул сорттоо "туруктуу" болуп саналат. Бул бирдей элементтер алардын тартибин өзгөртпөйт дегенди билдирет. Биз сорттоочу мүнөздөмөлөр боюнча бирдей.int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Retrieve the value of the element
int value = array[left];
// Move through the elements that are before the pulled element
int i = left - 1;
for (; i >= 0; i--) {
// If a smaller value is pulled out, move the larger element further
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the pulled element is larger, stop
break;
}
}
// Insert the extracted value into the freed space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Тиешелүү материал:
Shuttle Sort
Жөнөкөй сорттордун арасында дагы бир түрү бар - челнок сорттоо. Бирок мен «шаттл» сортун жактырам. Менимче, биз космостук кемелер жөнүндө сейрек сүйлөшөбүз, ал эми шаттл көбүрөөк чуркоо. Демек, челноктордун космоско кандайча учурулганын элестетүү оңой. Бул алгоритм менен байланыш бар. Алгоритмдин маңызы эмнеде? Алгоритмдин маңызы – биз солдон оңго карай кайталайбыз жана элементтерди алмаштырууда, алмаштырууну кайталоо керекпи же жокпу, көрүү үчүн артта калган бардык башка элементтерди текшеребиз.int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Тиешелүү материал:
Shell сорттоо
Дагы бир жөнөкөй сорт - Shell сорту. Анын маңызы көбүктүү сортко окшош, бирок ар бир итерацияда бизде салыштырылып жаткан элементтердин ортосунда ар кандай боштук бар. Ар бир кайталоо эки эсеге кыскарат. Бул жерде бир мисал ишке ашыруу болуп саналат:int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a difference between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right pointer until we can find one that
// there won't be enough space between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Тиешелүү материал:
Бириктирүү сорту
Көрсөтүлгөн жөнөкөй түрлөрүнөн тышкары, татаал түрлөрү бар. Мисалы, бириктирүү сорту. Биринчиден, рекурсия жардамга келет. Экинчиден, биздин татаалдыгыбыз көнүп калгандай квадраттык болбой калат. Бул алгоритмдин татаалдыгы логарифмдик. O(n log n) катары жазылган. Келгиле, муну кылалы. Биринчиден, сорттоо ыкмасына рекурсивдүү чалуу жазалы:public static void mergeSort(int[] source, int left, int right) {
// Choose a separator, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Execute this function recursively for the two halves (if we can split(
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Эми ага негизги аракетти кошолу. Бул жерде ишке ашыруу менен биздин суперметоддун мисалы болуп саналат:
public static void mergeSort(int[] source, int left, int right) {
// Choose a separator, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Execute this function recursively for the two halves (if we can split(
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the desired size
int[] buffer = new int[right - left + 1];
// Starting from the specified left border, go through each element
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use the delimeter to point to the element from the right side
// If delimeter > right, then there are no unadded elements left on the right side
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Келгиле, мисалды чакыруу менен иштетели mergeSort(array, 0, array.length-1)
. Көрүнүп тургандай, маани иргеле турган бөлүмдүн башталышын жана аягын көрсөтүүчү массивди киргизүү катары кабыл алганыбызга байланыштуу. Сорттоо башталганда, бул массивдин башталышы жана аягы. Андан кийин бөлүүчүнү эсептейбиз - бөлүүчүнүн орду. Эгерде бөлүүчү 2 бөлүккө бөлүнсө, анда бөлүүчү массивди бөлгөн бөлүмдөрдүн рекурсивдүү сорттоо деп атайбыз. Биз кошумча буфердик массивди даярдайбыз, анда биз сорттолгон бөлүмдү тандайбыз. Андан кийин курсорду иргеле турган аймактын башына коюп, өзүбүз даярдаган бош массивдин ар бир элементин аралап, аны эң кичине элементтер менен толтура баштайбыз. Курсор көрсөткөн элемент бөлүүчү көрсөткөн элементтен кичине болсо, биз бул элементти буфердик массивге жайгаштырабыз жана курсорду жылдырабыз. Болбосо, бөлгүч көрсөткөн элементти буфердик массивге жайгаштырабыз жана бөлгүчтү жылдырабыз. Бөлгүч сорттолгон аймактын чегинен чыгып кеткенде же биз бүт массивди толтурганда, көрсөтүлгөн диапазон сорттолгон болуп эсептелет. Тиешелүү материал:
Саноо сорттоо жана Радикс сорттоо
Дагы бир кызыктуу сорттоо алгоритми Counting Sort болуп саналат. Бул учурда алгоритмдик татаалдык O(n+k) болот, мында n – элементтердин саны, ал эми k – элементтин максималдуу мааниси. Алгоритмде бир көйгөй бар: биз массивдеги минималдуу жана максималдуу маанилерди бorшибиз керек. Бул жерде эсептөө сортунун үлгүсү:public static int[] countingSort(int[] theArray, int maxValue) {
// Array with "counters" ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// In the corresponding cell (index = value) we increase the counter
for (int num : theArray) {
numCounts[num]++;
}
// Prepare array for sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// go through the array with "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// go by the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Биз түшүнгөндөй, биз алдын ала минималдуу жана максималдуу баалуулуктарды билүү үчүн абдан ыңгайсыз болуп саналат. Анан дагы бир алгоритм бар - Radix Sort. Мен бул жерде алгоритмди визуалдык түрдө гана көрсөтөм. Ишке ашыруу үчүн материалдарды караңыз:
Java Quick Sort
Ооба, десерт үчүн - белгилүү алгоритмдердин бири: тез сорттоо. Анын алгоритмдик татаалдыгы бар, башкача айтканда, бизде O(n log n) бар. Бул сорт Хоар сорту деп да аталат. Кызыгы, алгоритмди Хоар СССРде жүргөндө ойлоп тапкан, ал Москва университетинде компьютердик котормочулук боюнча бorм алып, орусча-англисче сүйлөшмө түзүүдө. Бул алгоритм Javaдагы Arrays.sort программасында татаалыраак ишке ашырууда да колдонулат. Collections.sort жөнүндө эмне айтууга болот? Мен сизди өз көзүңүз менен көрүүнү сунуштайм, алар "капоттун астында" кандайча сорттолот. Ошентип, code:public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right while element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker until element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check if you don't need to swap elements pointed to by markers
if (leftMarker <= rightMarker) {
// The left marker will only be less than the right marker if we have to swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Move markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively for parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Бул жерде баары абдан коркунучтуу, ошондуктан биз аны чечебиз. Киргизүү массивинин int[]
булагы үчүн биз эки маркерди койдук, сол (L) жана оң (R). Биринчи жолу чакырылганда алар массивдин башына жана аягына дал келет. Андан кийин, колдоочу элемент аныкталат, ака pivot
. pivot
Андан кийин, биздин милдетибиз азыраак маанилерди солго pivot
, чоңун оңго жылдыруу . Бул үчүн, адегенде көрсөткүчтү L
андан чоңураак маанини тапканга чейин жылдырыңыз pivot
. Кичинекей маани табылбаса, андаpivot
. Потом двигаем указатель
R
пока не найдём меньшее, чем
pivot
meaning. Если меньшее meaning не нашли, то
R
совпадёт с
pivot
. Далее, если указатель
L
находится до указателя
R
or совпадает с ним, то пытаемся выполнить обмен элементов, если элемент
L
меньше, чем
R
. Далее
L
сдвигаем вправо на 1 позицию,
R
сдвигаем влево на одну позицию. Когда левый маркер
L
окажется за правым маркером
R
это будет означать, что обмен закончен, слева от
pivot
меньшие значения, справа от
pivot
— большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая sorting, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а
Pivot
по центру, т.е. число 6. Обведём его в круг. Под 4 напишем
L
, под 3 напишем
R
. 4 меньше чем 6, 2 меньше чем 6. Total,
L
переместился на положение
pivot
, т.к. по условию
L
не может уйти дальше, чем
pivot
. Напишем снова 4 2 6 7 3 , обведём 6 вкруг (
pivot
) и поставим под ним
L
. Теперь двигаем указатель
R
. 3 меньше чем 6, поэтому ставим маркер
R
на цифру 3. Так How 3 меньше, чем
pivot 6
выполняем
swap
, т.е. обмен. Запишем результат: 4 2 3 7 6 , обводим 6 вкруг, т.к. он по прежнему
pivot
. Указатель
L
на цифре 3, указатель
R
на цифре 6. Мы помним, что двигаем указатели до тех пор, пока
L
не зайдём за
R
.
L
двигаем на следующую цифру. Тут хочется разобрать два варианта: если бы предпоследняя цифра была 7 и если бы она была не 7, а 1.
Предпоследня цифра 1: Сдвинули указатель
L
на цифру 1, т.к. мы можем двигать
L
до тех пор, пока указатель
L
указывает на цифру, меньшую чем
pivot
. А вот
R
мы не можем сдвинуть с 6, т.к. R не мы можем двигать только если указатель
R
указывает на цифру, которая больше чем
pivot
.
swap
не делаем, т.к. 1 меньше 6. Записываем положение: 4 2 3 1 6, обводим
pivot 6
.
L
сдвигается на
pivot
и больше не двигается.
R
тоже не двигается. Обмен не производим. Сдвигаем
L
и
R
на одну позицию и подписываем цифру 1 маркером
R
, а
L
получается вне числа. Т.к.
L
вне числа — ничего не делаем, а вот часть 4 2 3 1 выписываем снова, т.к. это наша левая часть, меньшая, чем
pivot 6
. Выделяем новый
pivot
и начинаем всё снова )
Предпоследняя цифра 7: Сдвинули указать
L
на цифру 7, правый указатель не можем двигать, т.к. он уже указывает на pivot. т.к. 7 больше, чем
pivot
, то делаем
swap
. Запишем результат: 4 2 3 6 7, обводим 6 кружком, т.к. он
pivot
. Указатель
L
теперь сдвигается на цифру 7, а указатель
R
сдвигается на цифру 3. Часть от
L
до конца нет смысла сортировать, т.к. там всего 1 элемент, а вот часть от 4 до указателя
R
отправляем на сортировку. Выбираем
pivot
и начинаем всё снова ) Может на первый взгляд показаться, что если расставить много одинаковых с
pivot
значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, How такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая sorting не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до
pivot
до того, How другой элемент попал в часть до
pivot
при помощи обмена. Материал:
GO TO FULL VERSION