Сортирање је један од најважнијих проблема у рачунарству. Алгоритми сортирања су међу најпроучаванијим и најзначајнијим алгоритмима. Алгоритми сортирања су подједнако важни и као самосталне процедуре, али и као полазни корак у решавању тежих проблема. Њихова широка примена условила је развој великог броја алгоритама сортирања са различитим карактеристикама. Најчешће примене сортирања су:
Да бисмо могли исправно да користимо алгоритме сортирања, морамо добро да разумемо њихова својства. Алгоритме сортирања можемо поделити по неколико критеријума од којих су најважнија следећi:
У општем случају, временска сложеност алгоритама сортирања заснованих на упоређивању не може бити нижа од и то ћемо узети као доњу границу ефикасности сортирања. Примена линеарних алгоритама сортирања није могућа у општем случају, јер улазни проблем мора да задовољава одређене услове о којима ће бити речи касније.
Треба напоменути да алгоритми сортирања пате од замке великих константи, тј. врло често се дешава да асимптотски спорији алгоритам има боље перформансе од асимптотски бржег алгоритма на малим низовима. Због тога је већина алгоритама сортирања који се користе у пракси хибридна. Хибридне алгоритме ћемо детаљније разматрати када дођемо до технике подели па владај.
Да бисмо ефикасно користили алгоритме сортирања треба добро да разумемо њихове предности и мане, као и да добро разумемо проблем који решавамо. Неколико уобичајених сценарија коришћења алгоритама су следећи:
Програмски језик C# поседује уграђене методе којима се могу сортирати низови. У свим решењима које будемо писали, подразумева се примена уграђених метода сортирања. Низове у програмском језику C# можемо да сортирамо применом метода Array.Sort којем као аргумент прослеђујемо наш низ. Динамичке низове, тј. инстанце типа List<>, сортирамо позивањем метода Sort() над њима. Уграђене методе по дефиницији сортирају неопадајуће и нису стабилне.
Сортирање низа у програмском језику C# можемо постићи на следећи начин:
static void sortiraj_niz_neopadajuce(int[] niz) {
Array.Sort(niz);
}
static void sortiraj_listu_neopadajuce(List<int> niz) {
niz.Sort();
}Јасно је да сортирање не мора увек бити по вредности. На пример, шта ако желимо да сортирамо бројеве опадајуће по броју цифара, а у случају да имају исти број цифара, онда растуће по вредности. У том случају, морамо да “научимо” алгоритам сортирања како да упоређује вредности у низу/листи. Потребно је да напишемо прилагођени упоређивач (енгл. custom comparer) који ћемо проследити методу као анонимни метод написан уз помоћ ламбда израза.
static int broj_cifara(int x) {
int br = 0;
while (x > 0) {
br++;
x = x/10;
}
return x;
}
static void sortiraj_niz_neopadajuce(int[] niz) {
Array.Sort(niz, (x,y) => {
int bcx = broj_cifara(x);
int bcy = broj_cifara(y);
int diff = bcy.CompareTo(bcx);
if (diff != 0)
return diff;
return x.CompareTo(y);
});
}
static void sortiraj_listu_neopadajuce(List<int> niz) {
niz.Sort((x,y) => {
int bcx = broj_cifara(x);
int bcy = broj_cifara(y);
int diff = bcy.CompareTo(bcx);
if (diff != 0)
return diff;
return x.CompareTo(y);
});
}Други начин којим можемо да постигнемо исто ово јесте да не пишемо анонимни метод. Уместо тога, можемо да напишемо именовани компаратор за наше бројеве и само да га проследимо алгоритму сортирања.
static int broj_cifara(int x) {
int br = 0;
while (x > 0) {
br++;
x = x/10;
}
return x;
}
static int uporedi_brojeve(int x, int y) {
int bcx = broj_cifara(x);
int bcy = broj_cifara(y);
int diff = bcy.CompareTo(bcx);
if (diff != 0)
return diff;
return x.CompareTo(y);
}
static void sortiraj_niz_neopadajuce(int[] niz) {
Array.Sort(niz, uporedi_brojeve);
}
static void sortiraj_listu_neopadajuce(List<int> niz) {
niz.Sort(uporedi_brojeve);
}У оба случаја логика упоређивања је иста. Примитивне типове (int, double, bool) увек упоређујемо позивањем уграђеног метода CompareTo(). Када су подаци типа string у питању, уграђени метод CompareTo() их упоређује лексикографски. Дакле, ако желимо да упоредимо две променљиве примитивног типа написаћемо следеће x.CompareTo(y) и резултат ће бити следећи:
У случају да желимо упоређивање по неком нестандардном критеријуму морамо да обезбедимо прилагођени упоређивач. Повратна вредност прилагођеног упоређивача мора да буде сагласна са повратним вредностим уграђеног CompareTo() метода. У супротном, резултат сортирања неће бити онај који очекујемо.
Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.
Дат је низ такмичара, за сваког такмичара познато је његово име и број поена на такмичењу. Написати програм којим се сортира низ такмичара нерастуће по броју поена, а ако два такмичара имају исти број поена, онда их уредити по имену у неопадајућем поретку.
Улаз: У првој линији стандардног улаза налази се природан број (). У следећих линија налазе се редом елементи низа. За сваког такмичара, у једној линији, налазe се одвојени једним бланко симболом, његово име (дужине највише карактера) и број поена (природан број из интервала ) које је такмичар освојио.
Излаз: На стандардни излаз исписати елементе уређеног низа такмичара, за сваког такмичара у једној линији приказати његово име и број поена, одвојени једним бланко симболом.
Ради се о класичном задатку за вежбање сортирања. Задатак ћемо поделити у неколико фаза. Прво треба да дефинишемо тип података који ће представљати такмичара. За ту сврху можемо да креирамо нови тип података Takmicar који ће енкапсулирати податке о сваком такмичару.
class Takmicar {
public string Ime { get; set; }
public int Poeni {get; set; }
public Takmicar(string ime, int poeni) {
Ime = ime;
Poeni = poeni;
}
public override string ToString() {
return string.Format("{0}: {1}", Ime, Poeni)
}
}Затим, требају нам помоћне функције за учитавање и штампање такмичара.
static Takmicar[] ucitaj_takmicare() {
int n = int.Parse(Console.ReadLine());
Takmicar[] niz = new Takmicar[n];
for (int i = 0; i < niz.Length; i++) {
string[] linija = Console.ReadLine().Split(" ");
niz[i] = new Takmicar(
linija[0],
int.Parse(linija[1]);
);
}
}
static void stampaj_takmicare(Takmicar[] niz) {
for (int i = 0; i < niz.Length; i++)
Console.WriteLine(niz[i]);
}И на крају све то ћемо да спојимо у решење задатка
static void zad1() {
Takmicar[] niz = ucitaj_takmicare();
Array.Sort(niz, (x,y) => {
int diff = y.Poeni.CompareTo(x.Poeni);
if (diff != 0)
return diff;
return x.Ime.CompareTo(y.Ime);
});
stampaj_takmicare(niz);
}Главни део задатка, тј. само сортирање, радимо у линијама обележеним жутом бојом. Треба пажљиво испратити логику упоређивања:
Временска сложеност решења једнака је временској сложености алгоритма сортирања, тј. .
За сваки предмет који је на продају дата је шифра и цена. Купац има на располагању одређени износ динара и жели да купи што скупље предмете. Редом узима предмете почев од најскупљег, док има новца. Ако нема новца за најскупљи, узима најскупљи за који има новца. Приказати шифре предмета које купац купује и, ако му је остало, преостали износ новца.
Улаз: У првој линији стандардног улаза налази се износ новца (реалан број) који има купац, у другој број предмета, , а затим се, у свакo од следећих линији стандардног улаза, уносе шифра и цена (реалан број) предмета који су раздвојеним једним бланко карактером.
Излаз: У свакој линији стандарног излаза исписују се шифре и цене купљених предмета (раздвојене разма- ком), ако их има. У последњој линији приказује се преостали износ новца, ако постоји.
Као и у претходном задатку, прво ћемо дефинисати тип података Predmet којим ћемо представити предмете.
class Predmet {
public string Sifra { get; set; }
public double Cena {get; set; }
public Takmicar(string sifra, int cena) {
Sifra = sifra;
Cena = cena;
}
public override string ToString() {
return string.Format("{0} {1}", Sifra, Cena)
}
}У наставку би требало да дефинишемо помоћну функцију која би нам омогућила да учитамо низ предмета, али то ћемо препустити читаоцу за вежбу.
Задатак најлакше можемо решити ако прво сортирамо низ артикала опадајуће по цени. У тако сортираном низу треба да пронађемо први артикал за који корисник има новца, да од количине новца у поседу одузмемо вредност артикла, да прикажемо шифру изабраног артикла и да поступак наставимо од следеће позиције у низу, све док корисник има још новца на располагању.
static void zad2(Predmet[] niz, double x) {
// сортирамо низ опадајуће по цени
Array.Sort(niz, (x,y) => {
return y.Cena.CompareTo(x.Cena);
});
// бирамо предмете према описаном правилу
int i = 0;
while (i < niz.Length && x > 0) {
if (niz[i].Cena <= x) {
x -= niz[i].Cena;
Console.WriteLine(niz[i].Sifra);
}
i++;
}
// штампамо преостали износ новца, ако постоји
if (x > 0)
Console.WriteLine(x);
}Друга опција је да низ сортирамо растуће и да се кроз низ крећемо уназад, што препуштамо читаоцу за вежбу. Временска сложеност решења је једнака временској сложености сортирања, тј. .
Након такмичења из информатике позната је листа ученика са поенима (сваки ученик има различит број поена), међутим, није познат пласман (редни број сваког ученика). Напиши програм који за сваког ученика одређује пласман и исписује извештај о пласману, при чему су ученици приказани у истом редоследу као и у полазној листи са поенима.
Улаз: Са стандардног улаза уноси се број , а затим и подаци о ученика (за сваког ученика су у посебном реду дати име и број поена раздвојени размаком).
Излаз: На стандардни излаз за сваког ученика у посебном реду треба исписати име и пласман раздвојене размаком.
Задатак на први поглед делује једноставно, али у поставци постоји само један мали детаљ. Потребно је да одредимо пласман сваког ученика, тј. његове место у сортираном низу према поенима, али тај резултат треба да одштампамо у полазном редоследу са списка.
Једна идеја може бити да поред података о имену и броју поена уз сваког ученика енкапсулирамо и његов редни број на оригиналном списку, као и пласман ученика. Тада би најлакша идеја била следећа:
Као и до сада, потребно је да дефинишемо нови тип података Ucenik који ће енкапсулирати информације о ученицима. Затим, треба да напишемо помоћне методе за учитавање и штампање ученика.На крају треба да имплементирамо алгоритам описан малопре. Решење је у наставку:
class Ucenik {
public string Ime { get; set; }
public int Poeni { get; set; }
public int RedniBroj {get; set; }
public int Plasman { get; set; }
public Ucenik(string ime, int poeni, int redniBroj) {
Ime = ime;
Poeni = poeni;
RedniBroj = redniBroj;
Plasman = 0;
}
public override string ToString() {
return string.Format("{0} {1} {2}", Ime, Poeni, Plasman)
}
}
static Ucenik[] ucitaj_ucenike() {
int n = int.Parse(Console.ReadLine());
Ucenik[] niz = new Ucenik[n];
for (int i = 0; i < n; i++) {
string[] linija = Console.ReadLine().Split(" ");
niz[i] = new Ucenik(
linija[0],
int.Parse(linija[1]),
i
);
}
}
static void stampaj_ucenike(Ucenik[] niz) {
for (int i = 0; i < niz.Length; i++)
Console.WriteLine(niz[i]);
}
static void zad3() {
Ucenik[] niz = ucitaj_ucenike();
// сортирамо низ ученика опадајуће по броју поена
Array.Sort(niz, (x,y) => {
return y.Poeni.CompareTo(x.Poeni);
});
// иницијализујемо пласмане
for (int i = 0; i < niz.Length; i++)
niz[i].Plasman = i + 1;
// сортирамо низ растуће према редном броју
Array.Sort(niz, (x,y) => {
return x.RedniBroj.CompareTo(y.RedniBroj);
});
stampaj_ucenike(niz);
}Задатак можемо решити и само једним сортирањем. Уместо другог сортирања, можемо да искористимо трик са пресликавањем. Прецизније, након првог сортирања направићемо нови низ ученика. У тај низ ћемо на оригиналне позиције пресложити сортиране ученике.
static void zad3_efikasnije() {
Ucenik[] niz = ucitaj_ucenike();
// сортирамо низ ученика опадајуће по броју поена
Array.Sort(niz, (x,y) => {
return y.Poeni.CompareTo(x.Poeni);
});
Ucenik[] pomocni = new Ucenik[];
// иницијализујемо пласмане и слажемо низ према полазним
// редним бројевима
for (int i = 0; i < niz.Length; i++)
{
// иницијализација пласмана
niz[i].Plasman = i + 1;
// стављање уценика на оригинално место у низу
pomocni[niz[i].RedniBroj] = niz[i];
}
// резултат се налази у помоћном низу
stampaj_ucenike(pomocni);
}Класе су референтни типови, па додела у линији 19 представља само копирање референце, а не целог објекта Асимптотски, временска сложеност и једног и другог решења је . Међутим, друго решење је у пракси ефикасније, јер су му констатне значајно ниже.
Дат је низ природних бројева дужине . Сви елементи низа су природних бројеви мањи од . Написати програм који сортира дати низ бројева.
Улаз: У првој линији стандардног улаза се уноси природан број (), а затим се у следећих линија уноси један по један елемент низа. Елементи низа су природни бројеви мањи од .
Излаз: На стандардни излаз исписати сортирани низ.
Очигледно је да задатак можемо решити у једној линији позивањем уграђеног метода за сортирање низова. Временска сложеност таквог решења биће , Међутим, задатак се може решити и у линеарном времену.
Да бисмо решили задатак у линеарном времену, потребно је да пажљиво погледамо опис података на улазу. Бројеви који чине наш низ су у ограниченом и малом опсегу. Због тога можемо да искористимо пресликавање, тј. можемо да направимо нови низ у којем ћемо сачувати колико пута се која вредност јавила у полазном низу. Након што вредности пребројимо потребно је само да пресложимо наш полазни низ.
Описани поступак представља добро познати алгоритам сортирања пребројавањем (енгл. counting sort). Сортирање пребројавањем има три фазе:
Имплементација алгоритма је у наставку:
static int[] zad4(int[] niz){
// бројимо појављивања елемената
int[] counts = new int[100];
for (int i = 0; i < niz.Length; i++)
counts[niz[i]] ++;
// одређујемо кумулативне збирове
for (int i = 1; i < counts.Length; i++)
counts[i] += counts[i-1];
// реконструишемо сортирани низ
int[] rezultat = new int[niz.Length];
for (int i = niz.Length - 1; i >= 0; i--) {
int poz = --counts[niz[i]];
rezultat[poz] = niz[i];
}
return rezultat;
}Сортирање пребројавањем има следеће особине:
Сортирање пребројавањем користимо у следећим случајевима:
Државна комисија је направила списак свих такмичара у држави. Потребно је да се свакој општини дистри- буира списак такмичара са територије те општине, али тако да редослед остане исти какав је на полазном списку државне комисије.
Улаз: Са стандардног улаза прво се уноси пријављени број такмичара (), а затим се у следећих редова уносе информације о појединачним такмичарима. За сваког такмичара се уноси назив општине и шифра такмичара, раздвојене једним бланко карактером.
Излаз: На стандардни излаз исписати спискове за све општине, сваки у посебном реду. Општине су уређене лексикографски, растуће. Сваки списак почиње називом општине који је праћен знаком :. Након тога се наводе шифре свих такмичара раздвојене запетама (знацима ,). Иза сваког знака интерпункције (знака : и знака ,) наводи се по један размак.
Пажљивим читањем задатка уочавамо да морамо да сортирамо ученике према општинама, али да морамо да сачувамо полазни редослед такмичара. Одавде би се лако могло закључити да не можемо да користимо уграђене методе, јер оне нису стабилне. Међутим, постоји трик како то можемо да заобиђемо.
Стабилност значи да ће дупликат А и Б остати у истом релативном распореду након сортирања. То у преводу значи да ако је дупликат А био на мањем индексу у несортираном низу у односу на дупликат Б, онда њихови индекси морају задовољавати тај услов и након сортирања. Одатле, закључујемо да није довољно да користимо само вредност приликом упоређивања елемената низа, већ треба да упоређујемо и индексе. Ако су вредности једнаке, стабилност ћемо осигурати упоређивањем индекса.
Дакле, директно решење би било да сортирамо полазни низ по општинама узимајући у обзир позиције на списку, и затим да анализом суседних испишемо резултате. Као и до сада, креираћемо нови тип података којим ћемо енкапсулирати све значајне информације.
class Ucenik {
public string Opstina { get; set; }
public string Sifra { get; set; }
public int Indeks { get; set;}
public Ucenik(string opstina, string sifra, int indeks) {
Sifra = sifra;
Opstina = opstina;
Indeks = indeks;
}
public override string ToString() {
return string.Format("{0} {1}", Opstina, Sifra);
}
}
static Ucenik[] ucitaj_ucenike() {
int n = int.Parse(Console.ReadLine());
Ucenik[] niz = new Ucenik[n];
for (int i = 0; i < n; i++) {
string[] linija = Console.ReadLine().Split();
niz[i] = new Ucenik(
linija[0],
linija[1],
i
);
}
return niz;
}
static void stampaj_ucenike(Ucenik[] niz) {
Console.Write("{0}: {1}", niz[0].Opstina, niz[0].Sifra);
for (int i = 1; i < niz.Length; i++) {
if (niz[i].Opstina == niz[i-1].Opstina) {
Console.Write(", {0}", niz[i].Sifra);
}
else {
Console.WriteLine();
Console.Write("{0}: {1}", niz[i].Opstina, niz[i].Sifra);
}
}
Console.WriteLine();
}
static void zad5() {
Ucenik[] niz = ucitaj_ucenike();
Array.Sort(niz, (x,y) => {
int diff = x.Opstina.CompareTo(y.Opstina);
if (diff != 0)
return diff;
return x.Indeks.CompareTo(y.Indeks);
});
stampaj_ucenike(niz);
}Временска сложеност приказаног решења је , јер временска сложеност сортирања доминира.
Задатак можемо да решимо у истој временској сложености и без примене сортирања. Потребно је да приметимо да се задатак своди на упаривање облика кључ:вредност. У овом случају, кључ би био назив општине, а придружена вредност би била листа шифри ученика из те општине.
Уместо сортирања низа пријављних ученика, можемо да користимо сортирани речник, тј. генеричку колекцију SortedDictionary<>. За разлику од обичног речника, сортирани речник интерно чува податке сортиране по кључу. Сортирани речник је динамичка структура података заснована на самобалансирајућим бинарним стаблима претраге и гарантује најгору временску сложеност за све елементарне операције, при чему означава број кључева. Решење које користи сортирани речнике је у наставку:
static void zad5_recnik(){
SortedDictionary<string, List<string>> recnik = new SortedDictionary<string, List<string>>();
int n = int.Parse(Console.ReadLine());
for (int i 0; i < n; i++) {
string[] linija = Console.ReadLine().Split(" ");
if (recnik.ContainsKey(linija[0])) {
recnik[linija[0]].Add(linija[1]);
}
else {
List<string> sifre = new List<string>();
sifre.Add(linija[1]);
recnik.Add(string, sifre);
}
}
foreach (KeyValuePair<string, List<string>> kvp in recnik) {
Console.Write("{0}: ", kvp.Key);
for (int i = 0; i < kvp.Value.Count; i++) {
if (i > 0)
Console.Write(", ");
Console.Write("{0}", kvp.Value[i]);
}
Console.WriteLine()
}
}Временска сложеност решења које користи сортирани речник је такође . Приликом сваког додавања у речник, морамо да урадимо претрагу речника. Сложност једне претраге је , а такви претрага имамо , па ће укупна сложеност бити . Додавање шифре у листу је операција у константном времену, јер увек додајемо на крај листе. У решењу са сортирањем, посебну пажњу смо морали да посветимо стабилности алгоритма за сортирање, јер је основни захтев задатка био да редослед пријављених по општинама остане непромењен након сортирања. У решењу са сортираним речником смо тај услов испунили директно по конструкцији алгоритма. Шифре додајемо у листе оним редом којим се појављују на улазу, дакле, редослед ће остати непромењен и након конструкције речника.
Иако је решење са речником елегантније од решења са сортирањем низа, временска сложеност остаје непромењена. Међутим, задатак можемо да решимо и у линеарној сложености. Да бисмо то постигли, потребно је да искористимо алгоритам сортирања пребројавањем.
Алгоритам сортирања пребројавањем се може искористити само за природне бројеве ограниченог опсега. Да бисмо га применили овде потребно је да општине пресликамо у бројеве. Очекујемо да општина има много мање од броја пријављених ученика, па ће и опсег бројева које ћемо доделити општинама бити мали. За ово пресликавање можемо поново да искористимо речник на сличан начин као у претходном задатку.
class Ucenik {
public string Opstina { get; set; }
public string Sifra { get; set; }
public Ucenik(string opstina, string sifra) {
Sifra = sifra;
Opstina = opstina;
}
public override string ToString() {
return string.Format("{0} {1}", Opstina, Sifra);
}
}
static Ucenik[] ucitaj_ucenike() {
int n = int.Parse(Console.ReadLine());
Ucenik[] niz = new Ucenik[n];
for (int i = 0; i < n; i++) {
string[] linija = Console.ReadLine().Split();
niz[i] = new Ucenik(
linija[0],
linija[1],
);
}
return niz;
}
static void stampaj_ucenike(Ucenik[] niz) {
Console.Write("{0}: {1}", niz[0].Opstina, niz[0].Sifra);
for (int i = 1; i < niz.Length; i++) {
if (niz[i].Opstina == niz[i-1].Opstina) {
Console.Write(", {0}", niz[i].Sifra);
}
else {
Console.WriteLine();
Console.Write("{0}: {1}", niz[i].Opstina, niz[i].Sifra);
}
}
Console.WriteLine();
}
static void zad5() {
Ucenik[] niz = ucitaj_ucenike();
// прво пресликавамо општине у бројеве и одмах бројимо појављивања
SortedDictionary<string, int> counts = new SortedDictionary<string, int>();
for (int i = 0; i < niz.Length; i++) {
if (counts.ContainsKey(niz[i].Opstina)) {
counts[niz[i].Opstina] += 1;
}
else {
counts[niz[i].Opstina] = 1;
}
}
// одређујемо кумулативне збирове
int prethodnoUcenika = 0;
SortedDictionary<string, int> pozicije = new SortedDictionary<string, int>();
foreach (KeyValuePair<string, int> kvp in counts) {
prethodnoUcenika += kvp.Value;
pozicije[kvp.Key] = prethodnoUcenika;
}
// реконструкција сортираног низа
Ucenik[] rezultat = new Ucenik[niz.Length];
for (int i = niz.Length - 1; i >= 0; i++) {
int poz = --pozicije[niz[i].Opstina];
rezultat[poz] = niz[i];
}
stampaj_ucenike(rezultat);
}Временска сложеност приказаног решења је линеарна, али решење није ни близу елегенатно као претходно. Потребно нам је неколико помоћних структура података да бисмо обезбедили линеарну временску сложеност. Користимо следеће структуре података:
counts - Називе оштима користимо као индексе, док истовремено одређујемо број ученика у свакој општини.pozicije - Користимо га за одређивање кумулативноих збирова. Приметимо да приликом попуњавања овог речника пролазимо редом кроз речник counts. Речник counts је сортиран по кључу, па је поступак иницијализације речника pozicije еквивалентан инкременталном израчунавању кумулативних збирова у случају обичних низова.rezultat / Користимо га као помоћни низ референци у који ћемо само да упишемо полазне објекте, али у сортираном редоследу.Просторна сложеност приказаног решења је такође линеарна.
Дат је низ природних бројева. Имплементирати програм који их сортира алгоритмом вишеструког разврста- вања (RadixSort).
Улаз: Са стандардног улаза се уноси број (), а затим природних бројева између и (сваки у посебном реду).
Излаз: На стандардни излаз испиши те бројеве у неопадајућем редоследу.
Као и до сада, задатак бимо могли да урадимо применом уграђеног алгоритма за сортирање низова. Временска сложеност решења би у том случају била . Задатак међутим можемо да решимо и у линеарној сложености.
Опсег бројева у низу је огроман, па не можемо да користимо сортирање пребројавањем, јер бисмо морали да направимо помоћни низ counts чија је дужина једнака опсегу бројева. Међутим, можемо да применимо сортирање разврставањем (енгл. radix sort).
Главна идеја сортирања разврставањем је врло једноставна. Уместо да сортирамо цео низ одједном према вредностима елемената, можемо да применимо вишеструко сортирање елемената низа према вредности цифара на различитим позицијама. Прво ћемо да сортирамо елементе низа према цифри јединице, затим према цифри десетице и тако даље док не исцрпимо све цифре највећег броја. Да би овај алгоритам вишеструког сортирања иоле имао смисла, потребно је да помоћни алгоритам којим вршимо сортирање по цифрама буде стабилан и ефикасан.
Стабилност је важна, јер редослед који смо направили према цифрама ниже тежине, мора остати исти када радимо сортирање према цифрама више тежине. Када бисмо нарушили тај редослед, не бисмо добили сортирани низ. С обзиром да сортирамо према цифрама, опсег могућих вредности је мали, па као помоћни алгоритам можемо да користимо сортирање пребројавањем, које је и ефикасно и стабилно.
static void counting_sort(ref int niz, int d) {
int[] counts = new int[10];
for (int i = 0; i < niz.Length; i++)
counts[(niz[i] / d) % 10]++;
for (int i = 1; i < niz.Length; i++)
counts[i] += counts[i-1];
int[] rezultat = new int[niz.Length];
for (int i = niz.Length - 1; i >= 0; i--) {
int poz = --counts[(niz[i] / d) % 10];
rezultat[poz] = niz[i];
}
niz = rezultat;
}
static void radix_sort(ref int[] niz) {
int max = niz[0];
for (int i = 1; i < niz.Length; i++) {
if (niz[i] > max)
max = niz[i];
}
for (int d = 1; max/d > 0; d *= 10) {
counting_sort(ref niz, d);
}
}Приметимо да у листи аргумената имамо параметре који су обележени кључном речи ref. Та кључна реч само говори да позивајућа функција може да промени оригиналну вредност параметра. У нашем случају то ће значити да позивајућа функција мења низ на који показује његово име.
Временска сложеност алгоритма је . Ако највећи број у низу има цифара, тада ћемо пута применити сортирање пребројавањем које има сложеност , па ће укупна временска сложеност бити . Сортирање разврставањем има смисла користити када је . Просторна сложеност сортирања разврставањем је .
Претпоставимо да су интернет адресе представљене природним бројевима (IP адресе се, на пример, чувају у облику неозначених -битних бројева). Претраживач чува списак свих адреса које је корисник посетио током неког претходног периода. Корисник је многе адресе посећивао и више пута. Напиши програм који одрећује број различитих адреса које је корисник посетио.
Улаз: Са стандардног улаза се уноси број (), а затим и природних бројева (мањих од ), сваки у посебном реду.
Излаз: На стандардни излаз исписати број различитих адреса које је корисник посетио.
Очигледан начин како можемо да урадимо задатак јесте да низ IP адреса прво сортирамо и онда анализом суседних пребројимо различите. Решење је у наставку:
static int zad7(uint[] niz) {
Array.Sort(niz);
int brRazlicitih = 1;
for (int i = 1; i < niz.Length; i++) {
if (niz[i] != niz[i-1])
brRazlicitih++;
}
return brRazlicitih;
}Временска сложеност приказаног решења је , јер временска сложеност сортирања доминира. Анализу суседних радимо у једном пролази кроз низ, па је то ниже сложености од сортирања. Просторна сложеност решења је константна.
Осим сортирањем, задатак можемо да решимо и употребом одговарајуће структуре података. Приметимо да нама треба скуп различитих адреса. У те сврхе можемо да искористимо структуру података HashSet. Структура података HashSet је неуређена колекција која чува јединствене елементе, тј, не дозвољава дупликате. Због тога што је заснована на хеш табелема, структура података HashSet обезбеђује извршавање свих елементарних операција у константном времену.
Решење које користи HashSet је у наставку
static int zad7_efikasnije(uint[] niz) {
HashSet<uint> skup = new HashSet<uint>();
for (int i = 0; i < niz.Length; i++) {
if (skup.Contains(niz[i]) == false)
skup.Add(niz[i]);
}
return skup.Count;
}Временска сложеност приказаног решења је линеарна, тј. . Просторна сложеност је такође линеарна, јер у најгорем случају изграђујемо скуп који ће садржати све елементе почетног низа.
Ученици су гласали за председника одељенске заједнице. Напиши програм који одређује колико гласова је добио победник.
Улаз: Са стандардног улаза се учитава укупан број гласова (), а затим у наредних редова по једно име састављено од највише 20 слова енглеске абецеде.
Излаз: На стадардни излаз исписати број гласова који је добио победник (оно име које се најчшеће појавило на улазу).
Као и до сада задатак можемо решити сортирањем. Након што сортирамо гласове, потребно је да анализом суседних пребројимо дупликате. Дупликат са највећим бројем понављања ће бити победник.
static string zad8(string[] niz) {
Array.Sort(niz);
string pobednik = niz[0];
int maksGlasova = 1;
int trenutnoGlasova = 1;
for (int i = 1; i < niz.Length; i++) {
if (niz[i] == niz[i-1]) {
trenutnoGlasova += 1;
if (trenutnoGlasova > maksGlasova) {
maksGlasova = trenutnoGlasova;
pobednik = niz[i];
}
}
else {
trenutnoGlasova = 1;
}
}
return pobednik;
}Временска сложеност приказаног решења је , јер временска сложеност сортирања доминира. Анализу суседних радимо у једном пролази кроз низ, па је то ниже сложености од сортирања. Просторна сложеност решења је константна.
Други начин како можемо да решимо задатак је употребом речника. Из текста задатка се лако види да постоји упараивање облика кључ:вредност, тј. можемо упарити кандидата са бројем гласова које је освојио. Након што конструишемо речник, потребно је само да одредим кандидата са максималним бројем гласова.
static string zad8_efikasnije(string[] niz) {
Dictionary<string, int> glasovi = new Dictionary<string, int>();
for (int i = 0; i < niz.Length; i++) {
if (glasovi.ContainsKey(niz[i])) {
glasovi[niz[i]] += 1;
}
else {
glasovi.Add(niz[i], 1);
}
}
string pobednik = "";
int maksGlasova = -1;
foreach (KeyValuePair<string, int> kvp in glasovi) {
if (kvp.Value > maksGlasova) {
maksGlasova = kvp.Value;
pobednik = kvp.Key;
}
}
return pobednik;
}Временска сложеност решења је линеарна, као и просторна сложеност.
У низу целих бројева одредити најбројнији подскуп елемената који се могу уредити у низ узастопних целих бројева. На пример, за низ треба приказати . Ако има више таквих подскупова, приказати први (онај у којем су бројеви најмањи).
Улаз: У првој линији стандардног улаза уноси се број елемената низа (), а затим у следећих линија целобројни елементи низа .
Излаз: Најбројнији подскуп узастопних целих бројева (елемената датог низа) уређен у неопадајућем поретку.
С обзиром да се у задатку тражи било који подскуп бројева, тј. елементи не морају бити узастопни у полазном низу, можемо прво да сортирамо полазни низ. У овако сортираном низу треба да одредимо најдужи растући подниз узастопих бројева.
static int[] zad9(int[] niz) {
Array.Sort(niz);
int maksDuzina = 1;
int maksPocetak = niz[0];
int trenutnaDuzina = 1;
int pocetak = niz[0];
for (int i = 1; i < niz.Length; i++) {
if (niz[i] == niz[i-1] + 1) {
trenutnaDuzina++;
}
else {
if (trenutnaDuzina > maksDuzina) {
maksDuzina = trenutnaDuzina;
maksPocetak = trenutniPocetak;
}
trenutniPocetak = niz[i];
trenutnaDuzina = 1;
}
}
if (trenutnaDuzina > maksDuzina) {
maksDuzina = trenutnaDuzina;
maksPocetak = trenutniPocetak;
}
int[] rezultat = new int[maksDuzina];
for (int i = 0; i < maksDuzina; i++)
rezultat[i] = maksPocetak + i;
return rezultat;
}Временска сложеност приказаног решења је , јер временска сложеност сортирања доминира. Анализу суседних радимо у једном пролази кроз низ, па је то ниже сложености од сортирања. Просторна сложеност решења је константна.
Задатак можемо да урадимо и у линеарној сложености употребом структуре података HashSet<>. Да бисмо могли да решимо овај задатак у линеарној сложености, морамо да избацимо проверавање свих могућих бројева као кандидата за почетак растућег подниза. Проверавање свих бројева као кандидата за почетак растућег подниза води ка квадратном решењу.
Дакле, број може бити почетак растућег подниза само ако се у низу не налази његов претходник. Ако у низу нема претходника, онда треба да наставимо испитивање низа све док у низу постоји следбеник. Поред карактеризације првог елемента растућег подниза, кључно запажање је и то да нас не занима где се у низу налазе ти бројеви, већ само да ли постоје или не. Најефикаснији начин да то проверимо је управо употребом структуре података HashSet<>. Решење је у наставку:
static int[] zad9_efikasnije(int[] niz) {
// изграђујемо HashSet<> на основу низа бројева
HashSet<int> brojevi = new HashSet<int>(niz);
int maxDuzina = 0;
int maxPocetak = 0;
// у петљи проналазимо кандидате за почетак подниза
foreach (x in brojevi) {
// број је почетак растућег подниза, само ако нема претходника
if (brojevi.Contains(x-1) == false) {
int trenutniBroj = x;
int trenutnaDuzina = 1;
// све док се у скупу налази следбеник, увећавамо
// дужину растућег подниза и прелазимо на следећи број
while (brojevi.Contains(trenutniBroj + 1)) {
trenutniBroj++;
trenutnaDuzina++;
}
if (trenutnaDuzina > maxDuzina) {
maxDuzina = trenutnaDuzina;
maxPocetak = x;
}
}
}
int[] rezultat = new int[maksDuzina];
for (int i = 0; i < maksDuzina; i++)
rezultat[i] = maksPocetak + i;
return rezultat;
}Временска сложеност приказаног решења је линеарна, тј. . Просторна сложеност је такође линеарна. Закључак да се ради о линеарној временској сложености није очигледан и захтева пажљиво анализирање линија 10-30. Спољашња for петља ће сваки елемент скупа испитати тачно једном и за њега проверити да ли се ради о почетку најдужег растућег подниза у линији 13. Унутрашња while pетља у линији 20 проналази следбенике бројева који чине текући растући подниз узастопних бројева. Приметимо да та унутрашња петља сваки узастопни растући подниз у потпуности испитује тачно једном. Одавде закључујемо да се сваки елемент полазног низа може испитати највише два пута током рада алгоритма, једном као почетак узастопног подниза и други пут као члан узастопног подниза. Одавде и следи закључак о линеарној временској сложености.
Две речи су анаграми ако се једна може добити од друге само променом редоследа слова (на пример, трава и ватра). Напиши програм који у датом скупу речи проналази највећи број речи које су међусобни анаграми.
Улаз: Са стандардног улаза се уноси број речи (), а затим у наредних линија по једна реч полазног скупа (све речи се састоје само од малих слова енглеског алфабета и имају највише 200 карактера).
Излаз: На стандардни излаз исписати тражену величину највећег подскупа полазног скупа речи, у коме су све речи једна другој анаграми.
Да бисмо решили задатак потребно је да прво дамо одговор на питање шта значи да су две речи анаграми. Две речи су анаграми ако су сачињене од истих слова, тј. ако се пермутацијом слова једне речи може добити друга реч. Проверу да ли су две речи анаграми можемо да урадимо на два начина:
Сада, остаје да речи сортирамо и да анализом суседних одредимо дужину најдужег сегмента сачињеног од анаграма. С обзиром да нас занима само дужина најдужег сегмента анаграма, а не које конкретне речи га чине, можемо мало да уштедимо на временској сложености програма. Уместо да речи трансформишемо сваки пут када их упоређујемо, ефикасније је да речи трансформишемо унапред и да их тако трансформисане упоређујемо и сортирамо.
Прво ћемо приказати решење које сортира карактере унутар речи, затим тако трансформисане речи сортира и онда анализом суседних одређује најдужи сегмент анаграма.
static string sortiraj_po_karakterima(string rec)
{
char[] slova = rec.ToCharArray();
Array.Sort(slova);
return new string(slova);
}
static int zad10(string[] reci)
{
// прво трансфоримишемо речи
for (int i = 0; i < reci.Length; i++)
{
reci[i] = sortiraj_po_karakterima(reci[i]);
}
// сортирамо трансформисане речи
Array.Sort(reci);
// анализом суседних одређујемо најдужи сегмент анаграма
int trenutnaDuzina = 1;
int maksDuzina = 1;
for (int i = 1; i < reci.Length; i++)
{
if (reci[i].CompareTo(reci[i-1]) == 0) {
trenutnaDuzina++;
}
else {
if (trenutnaDuzina > maksDuzina) {
maksDuzina = trenutnaDuzina;
}
trenutnaDuzina = 1;
}
}
// провера да ли је најдужи сегмент на крају
if (trenutnaDuzina > maksDuzina)
{
maksDuzina = trenutnaDuzina;
}
return maksDuzina;
}Да бисмо одредили временски сложеност операција, морамо пажљиво да анализирамо извршене операције:
Из анализе операција, лако видимо да је укупна временска сложеност оваквог решења , тј. .
Другачија идеја којом се исто може решити овај задатак своди се на упоређивање низа бројача. Сваку реч ћемо трансформисати у низ који чува број појављивања сваког карактера. Након тога, сортирамо све те низове и затим их упоређујемо у кораку одређивања најдужег сегмента анаграма. Решење је у прилогу
static int uporedi_nizove(int[] niz1, int[] niz2) {
for (int i = 0; i < niz1.Length; i++)
{
if (niz1[i] < niz2[i])
return -1;
else if (niz1[i] > niz2[i])
return 1
}
return 0;
}
static int[] prebroj_slova(string rec) {
int[] broj = new int[26];
for (int i = 0; i < rec.Length; i++)
broj[rec[i] - 'a']++;
return broj;
}
static int zad10_2(string[] reci)
{
// прво трансфоримишемо речи
int[][] broj_slova = new int[reci.Length][];
for (int i = 0; i < reci.Length; i++)
{
broj_slova[i] = prebroj_slova(reci[i]);
}
// сортирамо трансформисане речи
Array.Sort(broj_slova, uporedi_nizove);
// анализом суседних одређујемо најдужи сегмент анаграма
int trenutnaDuzina = 1;
int maksDuzina = 1;
for (int i = 1; i < reci.Length; i++)
{
if (uporedi_nizove(broj_slova[i], broj_slova[i-1]) == 0) {
trenutnaDuzina++;
}
else {
if (trenutnaDuzina > maksDuzina) {
maksDuzina = trenutnaDuzina;
}
trenutnaDuzina = 1;
}
}
// провера да ли је најдужи сегмент на крају
if (trenutnaDuzina > maksDuzina)
{
maksDuzina = trenutnaDuzina;
}
return maksDuzina;
}Временска сложеност и овог решења је , тј. . Формалну анализу препуштамо читаоцу за вежбу.
Људи су долазили и одлазили са базена и за сваког посетиоца је познато време доласка и време одласка. Претпоставићемо да је човек на базену у периоду облика , тј. да се човек налази на базену у тренутку свог доласка , а да се не налази у тренутку свог одласка . Колико је људи највише било истовремено на базену?
Улаз: Са стандардног улаза се учитава број посетилаца ($1 n ), а затим у наредних редова време доласка и време одласка сваког посетиоца (мерење је веома прецизно, па се време представља природним бројевима мањим од милијарде), одвојене са по једним размаком.
Излаз: На стандардни излаз исписати тражени максимални број посетилаца у неком тренутку.
Ради се о класичном задатку који од нас тражи да извршимо анализу интервала. Трик који се најчешће користи у оваквим случајевима је увођење догађаја. Ако пажљиво прочитамо задатак, јасно је да се ради о низу интервала, што није ништа друго него неки низ тачака у времену. Те тачке у времену се разликују према томе да ли се ради о доласку или о одласку. Долазак је почетак интервала, а одлазак је крај интервала. Дакле, у овом случају догађај ће бити тренутак у времену обележен информацијом да ли се ради о доласку или о одласку.
Да бисмо решили задатак, потребно је да сортирамо по временима овако формирани низ догађаја. У случају да два догађаја имају исто време, тада ћемо сортирати према типу догађаја. Када се то деси, сматраћемо да је одлазак мањи од доласка, тј. да се мора наћи испред у сортираном низу. Овакав закључак има оправдање у текст задатка, јер време одласка подразумева да корисник више није на базену. Решење је у наставку:
class Dogadjaj {
public int Vreme {get;set;}
public bool Dolazak {get;set;}
public Dogadjaj(int v, bool d) {
Vreme = v;
Dolazak = d;
}
}
static int zad11() {
// конструкција листе догађаја
int n = int.Parse(Console.ReadLine());
List<Dogadjaja> dogadjaji = new List<Dogadjaj>();
for (int i = 0; i < n; i++) {
string[] linija = Console.ReadLine().Split(" ");
dogadjaji.Add(
new Dogadja(int.Parse(linija[0]), true)
);
dogadjaji.Add(
new Dogadja(int.Parse(linija[1]), false)
);
}
// сортирање листе догађаја према временима и типу
dogadjaji.Sort((x,y) => {
int diff = x.Vreme.CompareTo(y.Vreme);
if (diff != 0)
return diff;
return x.Dolazak.CompareTo(y.Dolazak);
});
// проласком кроз сортирани низ догађаја одређујемо
// нејвећи број посетилаца
int trenutno_korisnika = 0;
int maks_korisnika = 0;
foreach (Dogadjaj d in dogadjaji) {
if (d.Dolazak)
trenutno_korisnika += 1;
else
trenutno_korisnika -= 1;
if (trenutno_korisnika > maks_korisnika)
maks_korisnika = trenutno_korisnika;
}
return maks_korisnika;
}Временска сложеност решења једнака је временској сложености сотрирања, тј. биће тј. . Задатак се може решити и без увођења помоћног типа, али то остављамо читаоцу за вежбу.
Други начин како се задатак може решити је уз помоћ речника. Речник можемо да искористимо да директно мапирамо сваки сат са бројем корисника који су у том тренутку на базену. Дакле, ако нам корисник унесе интервал , ми ћемо у речнику да увећамо број посетилаца у тренуцима . На крају, остаје нам само да одредимо максимални број посетилаца једноставним проласком кроз елементе речника.
static int zad11_recnik() {
// конструкција листе догађаја
int n = int.Parse(Console.ReadLine());
Dictionary<int, int> recnik = new Dictionary<int,int>();
for (int i = 0; i < n; i++) {
string[] linija = Console.ReadLine().Split(" ");
int dolazak = int.Parse(linija[0]);
0nt odlazak = int.Parse(linija[1]);
for (int j = dolazak; j < odlazak; j++) {
int vrednost = 0;
recnik.TryGetValue(j, out vrednost);
recnik[j] = vrednost + 1;
}
}
// одређивање највећег броја посетилаца
int maks_korisnika = 0;
foreach (KeyValuePair<int,int> kvp in recnik) {
if (kvp.Value > maks_korisnika)
maks_korisnika = kvp.Value;
}
return maks_korisnika;
}Иако користи речник, временска сложеност овог решења је врло висока. Разлог неефикасности крије се у унутрашњој петљи која је обележена жутом бојом. Речник омогућава врло ефикасне операције додавања елемената, али проблем се крије у броју тих операција које ћемо извршити. Прецизније за сваки од интервала, ми извршавамо додавања тачака у времену. Сложеност конструкције речника ће бити , што је лошије од решења које користи сортирање догађаја. Из овог примера је битно приметити да коришћење ефикасне структуре не значи увек ефикаснији и бржи алгоритам.