Алгоритъм за разбъркване на масива
За пореден път срещнах проста, но интересна задача - да смесвам наличните стойности в даден масив.
Понякога тази задача се формулира и като запълване на масив с неповтарящи се стойности в произволен ред. Но не е разумно да се напише алгоритъм, който ще генерира произволно число и след това да се провери дали тази стойност ще се повтори с вече попълнени елементи. Би било много по-правилно просто да смесите дадения масив. Нещо повече, това ще позволи да не се усложнява процесът на избор на приемливи стойности, като се наблюдава уникалността на всяка стойност или като се вземе предвид появата на всяка стойност определен брой пъти.
В резултат на това задачата се свежда само до смесване на съществуващата последователност, независимо от първоначалния й състав и подреждане.
Най-простото решение би било да се извършат N операции за замяна на два елемента в цикъл, чиито индекси се избират на случаен принцип. Стойността на N определя качеството на такова смесване - колкото повече замествания, толкова по-добър е резултатът. Недостатъкът на този метод е, че някои елементи от масива (особено ако е голям) могат да останат на първоначалните си места. Същият недостатък ще бъде възможността за многократно преместване на един и същ елемент от масив. В резултат на това нерационално увеличаване на броя на замените все още не води до 100% висококачествено разместване на всички елементи.
Следният алгоритъм е по-добър както по отношение на преместването на всички елементи, така и по броя на операциите за смесване:
- изберете произволен елемент от масива;