Сортирање је један од најважнијих проблема у рачунарству. Алгоритми сортирања су међу најпроучаванијим и најзначајнијим алгоритмима. Алгоритми сортирања су подједнако важни и као самосталне процедуре, али и као полазни корак у решавању тежих проблема. Њихова широка примена условила је развој великог броја алгоритама сортирања са различитим карактеристикама. Најчешће примене сортирања су:
Да бисмо могли исправно да користимо алгоритме сортирања, морамо добро да разумемо њихова својства. Алгоритме сортирања можемо поделити по неколико критеријума од којих су најважнија следећ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
);
}
return niz;
}
// помоћни метод за штампање ученика
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);
}Класе су референтни типови, па додела у линији 15 представља само копирање референце, а не целог објекта. Асимптотски, временска сложеност и једног и другог решења је . Међутим, друго решење је у пракси ефикасније, јер су му констатне значајно ниже.
Дат је низ природних бројева дужине . Сви елементи низа су природних бројеви мањи од . Написати програм који сортира дати низ бројева.
Улаз: У првој линији стандардног улаза се уноси природан број (), а затим се у следећих линија уноси један по један елемент низа. Елементи низа су природни бројеви мањи од .
Излаз: На стандардни излаз исписати сортирани низ.
Очигледно је да задатак можемо решити у једној линији позивањем уграђеног метода за сортирање низова. Временска сложеност таквог решења биће , Међутим, задатак се може решити и у линеарном времену.
Да бисмо решили задатак у линеарном времену, потребно је да пажљиво погледамо опис података на улазу. Бројеви који чине наш низ су у ограниченом и малом опсегу. Због тога можемо да искористимо пресликавање, тј. можемо да направимо нови низ у којем ћемо сачувати колико пута се која вредност јавила у полазном низу. Након што вредности пребројимо потребно је само да пресложимо наш полазни низ.
Описани поступак представља добро познати алгоритам сортирања пребројавањем (енгл. 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 - Користимо га као помоћни низ референци у који ћемо само да упишемо полазне објекте, али у сортираном редоследу.Просторна сложеност приказаног решења је такође линеарна.
Дат је низ природних бројева. Имплементирати програм који их сортира алгоритмом вишеструког разврставања (енгл. radix sort).
Улаз: Са стандардног улаза се уноси број (), а затим природних бројева између и (сваки у посебном реду).
Излаз: На стандардни излаз исписати те бројеве у неопадајућем редоследу.
Као и до сада, задатак бимо могли да урадимо применом уграђеног алгоритма за сортирање низова. Временска сложеност решења би у том случају била . Задатак међутим можемо да решимо и у линеарној сложености.
Опсег бројева у низу је огроман, па не можемо да користимо сортирање пребројавањем, јер бисмо морали да направимо помоћни низ counts чија је дужина једнака опсегу бројева. Међутим, можемо да применимо сортирање разврставањем (енгл. radix sort).
Главна идеја сортирања разврставањем је врло једноставна. Уместо да сортирамо цео низ одједном према вредностима елемената, можемо да применимо вишеструко сортирање елемената низа према вредности цифара на различитим позицијама. Прво ћемо да сортирамо елементе низа према цифри јединице, затим према цифри десетице и тако даље док не исцрпимо све цифре највећег броја. Да би овај алгоритам вишеструког сортирања иоле имао смисла, потребно је да помоћни алгоритам којим вршимо сортирање по цифрама буде стабилан и ефикасан.
Стабилност је важна, јер редослед који смо направили према цифрама ниже тежине, мора остати исти када радимо сортирање према цифрама више тежине. Када бисмо нарушили тај редослед, не бисмо добили сортирани низ. С обзиром да сортирамо према цифрама, опсег могућих вредности је мали, па као помоћни алгоритам можемо да користимо сортирање пребројавањем, које је и ефикасно и стабилно.
// помоћни алгоритам за сортирање по цифри d
static void counting_sort(ref int niz, int d) {
// бројимо појављивања цифре 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];
// сортирамо низ према цифри d уз помоч кумулативних збирова
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;
}
// ако није, додајемо га у речник са бројем гласова 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);
// на почетку је дужина најдужег растућег подниза узастопнох
// бројева једнака 0
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;
}Иако користи речник, временска сложеност овог решења је врло висока. Разлог неефикасности крије се у унутрашњој петљи која је обележена жутом бојом. Речник омогућава врло ефикасне операције додавања елемената, али проблем се крије у броју тих операција које ћемо извршити. Прецизније за сваки од интервала, ми извршавамо додавања тачака у времену. Сложеност конструкције речника ће бити , што је лошије од решења које користи сортирање догађаја. Из овог примера је битно приметити да коришћење ефикасне структуре не значи увек ефикаснији и бржи алгоритам.