5. Järjestäminen

Järjestäminen (sorting) on klassinen algoritmiikan ongelma, jossa lista alkioita tulee järjestää suuruusjärjestykseen. Moderneissa ohjelmointikielissä on valmiita tapoja järjestämiseen, kuten Pythonin metodi sort ja funktio sorted.

Järjestämiseen on olemassa tehokkaita algoritmeja, joiden aikavaativuus on \(O(n \log n)\). Tämän ansiosta järjestämistä voidaan käyttää osana tehokasta algoritmia. Usein ideana on järjestää ensin algoritmille annetut tiedot ja käsitellä niitä sitten järjestystä hyödyntäen.

Järjestäminen Pythonissa

Pythonissa listassa on metodi sort, joka järjestää sen sisällön:

numbers = [4, 2, 1, 2, 5, 4, 5, 2]
numbers.sort()
print(numbers) # [1, 2, 2, 2, 4, 4, 5, 5]

Pythonissa on myös funktio sorted, joka palauttaa listan järjestettynä:

numbers = [4, 2, 1, 2, 5, 4, 5, 2]
print(sorted(numbers)) # [1, 2, 2, 2, 4, 4, 5, 5]

Näissä tavoissa erona on, että metodi sort muuttaa olemassa olevaa listaa, kun taas funktio sorted palauttaa uuden listan.

Metodi sort ja funktio sorted on toteutettu tehokkaasti, ja niiden aikavaativuus on \(O(n \log n)\).

Esimerkki: Pienin ero

Tehtävä

Voimme ratkaista tämän tehtävän tehokkaasti järjestämisen avulla, koska järjestämisen jälkeen listassa ovat vierekkäin luvut, joiden välillä on pienin ero. Tämän ansiosta pienin ero voidaan löytää helposti käymällä läpi lista vasemmalta oikealle ja vertaamalla joka kohdassa vierekkäisiä lukuja.

Yllä olevassa esimerkissä lista järjestettynä on \([1,4,11,13,19,25,33,40]\) ja luvut \(11\) ja \(13\) ovat vierekkäin.

Seuraava funktio min_diff toteuttaa algoritmin:

def min_diff(numbers):
    numbers = sorted(numbers)
    n = len(numbers)
    result = numbers[1] - numbers[0]
    for i in range(2, n):
        result = min(result, numbers[i] - numbers[i - 1])
    return result

Algoritmi järjestää ensin listan ajassa \(O(n \log n)\) ja käy sitten läpi kaikki vierekkäiset luvut silmukalla ajassa \(O(n)\), joten algoritmin aikavaativuus on \(O(n \log n)\).

Huomaa, että voisimme käyttää funktion alussa myös listan metodia sort:

def min_diff(numbers):
    numbers.sort()
    ...

Tässä on kuitenkin ongelmana, että parametrina annetun listan järjestäminen heijastuu myös funktion min_diff kutsukohtaan. Tämä ei ole toivottava ilmiö, koska funktion ei pitäisi muuttaa listan sisältöä. Seuraavat koodit havainnollistavat asiaa:

Käytössä sort

numbers = [25, 1, 11, 19, 33, 13, 4, 40]
print(min_diff(numbers)) # 2
print(numbers) # [1, 4, 11, 13, 19, 25, 33, 40]

Käytössä sorted

numbers = [25, 1, 11, 19, 33, 13, 4, 40]
print(min_diff(numbers)) # 2
print(numbers) # [25, 1, 11, 19, 33, 13, 4, 40]

Kun käytössä on metodi sort, funktion min_diff kutsuminen järjestää sivuvaikutuksena listan numbers. Kun käytössä on funktio sorted, lista numbers ei muutu, koska funktio sorted luo uuden järjestetyn listan.

Yleensä hyvä valinta on käyttää funktiota sorted, jolloin järjestäminen ei aiheuta sivuvaikutuksia.

Hajautus vs. järjestäminen

Monessa tehtävässä on kaksi mahdollisuutta tehokkaan ratkaisun luomiseen: hajautus tai järjestäminen. Tarkastellaan esimerkkinä tehtävää, jonka ratkaisimme aiemmin hajautuksen avulla:

Tehtävä

Ratkaisimme tehtävän aiemmin hajautuksen avulla näin:

Algoritmi 1

def count_distinct(numbers):
    seen = set()
    for x in numbers:
        seen.add(x)
    return len(seen)

Voimme ratkaista tehtävän myös toisella tavalla järjestämisen avulla. Koska järjestetyssä listassa yhtä suuret luvut ovat peräkkäin, voimme käydä järjestetyn listan läpi ja kasvattaa laskuria aina luvun vaihtuessa.

Tässä on järjestämistä käyttävä algoritmi:

Algoritmi 2

def count_distinct(numbers):
    numbers = sorted(numbers)    
    result = 1
    for i in range(1, n):
        if numbers[i] != numbers[i - 1]:
            result += 1
    return result

Hajautusta käyttävä algoritmi vie aikaa \(O(n)\) ja järjestämistä käyttävä algoritmi vie aikaa \(O(n \log n)\), mutta miten nopeita algoritmit ovat käytännössä?

Tehdään seuraavaksi testi, joka vertailee algoritmien tehokkuutta. Koska molemmat algoritmit ovat tehokkaita, toteutetaan testi niin, että listan koko on aina suuri (\(n=10^7\)). Koska listalla olevien lukujen suuruus saattaa vaikuttaa tehokkuuteen, luodaan lista niin, että jokainen luku on satunnainen luku väliltä \(1 \dots k\). Tämän avulla voimme tutkia, miten \(k\):n muuttuminen vaikuttaa tehokkuuteen.

Testikoneella tulokset ovat seuraavat:

Tässä tapauksessa vaikuttaa, että hajautusta käyttävä algoritmi on tehokkaampi. Se on myös koodiltaan yksinkertaisempi, koska silmukassa riittää lisätä listan luvut set-rakenteeseen eikä vertailla vierekkäisiä lukuja keskenään.

Lisää järjestämisestä

Käänteinen järjestäminen

Parametri reverse muuttaa järjestämisen suunnan käänteiseksi:

numbers = [2, 4, 3, 5, 6, 1, 8, 7]
numbers.sort(reverse=True)
print(numbers) # [8, 7, 6, 5, 4, 3, 2, 1]

Moniosaiset alkiot

Jos järjestettävät alkiot ovat tupleja tai listoja, järjestys on ensisijaisesti ensimmäisen alkion mukaan, toissijaisesti toisen alkion mukaan, jne.

Esimerkiksi listassa olevat parit järjestyvät näin:

pairs = [(3, 5), (1, 3), (1, 2), (2, 4)]
pairs.sort()
print(pairs) # [(1, 2), (1, 3), (2, 4), (3, 5)]

Alkioiden vertailutapa

Parametrilla key voidaan määritellä funktio, joka muuttaa alkioita ennen kuin niitä vertaillaan toisiinsa. Parametria voidaan käyttää esimerkiksi näin:

numbers = [4, -1, 6, 2, -7, 8, 3, -5]
numbers.sort(key=abs)
print(numbers) # [-1, 2, 3, 4, -5, 6, -7, 8]

Tässä funktiona on abs eli itseisarvo, minkä seurauksena luvut järjestetään suuruuden mukaan välittämättä niiden etumerkistä.

Oma luokka

Pythonissa luokan olioita voidaan järjestää, kun luokkaan on toteutettu riittävästi metodeita olioiden vertailua varten. Esimerkiksi riittää, että on toteutettu metodit __eq__ ja __lt__, jolloin olioita voidaan vertailla operaattoreiden == ja < avulla. Seuraava koodi havainnollistaa asiaa:

class Location:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

    def __lt__(self, other):
        return (self.x, self.y) < (other.x, other.y)

    def __repr__(self):
        return str((self.x, self.y))

locations = []
locations.append(Location(1, 4))
locations.append(Location(4, 5))
locations.append(Location(2, 2))
locations.append(Location(1, 2))

locations.sort()

print(locations) # [(1, 2), (1, 4), (2, 2), (4, 5)]

Esimerkki: Ravintola

Tehtävä

Tällaisessa tehtävässä hyvä lähestymistapa on tarkastella tapahtumia aikajärjestyksessä. Tapahtumia on kahdenlaisia: asiakas saapuu ravintolaan tai asiakas lähtee ravintolasta. Jokaisen tapahtuman yhteydessä asiakkaiden määrä kasvaa tai vähenee yhdellä.

Esimerkin tapauksessa tapahtumat ovat:

Tämän ansiosta voimme ratkaista tehtävän tehokkaasti muodostamalla ensin asiakkaita vastaavat tapahtumat ja järjestämällä ne aikajärjestykseen. Tämän jälkeen voimme käydä läpi tapahtumat ja pitää yllä asiakkaiden määrää laskurissa.

Seuraavassa funktiossa listat arrivals ja departures sisältävät asiakkaiden saapumisajat ja lähtöajat. Esimerkin tapauksessa arrivals on [6, 3, 6, 1, 2] ja departures on [8, 7, 9, 5, 8].

def max_customers(arrivals, departures):
    events = []
    for time in arrivals:
        events.append((time, 1))
    for time in departures:
        events.append((time, 2))
        
    events = sorted(events)
    
    counter = 0
    result = 0
    for event in events:
        if event[1] == 1:
            counter += 1
        if event[1] == 2:
            counter -= 1
        result = max(result, counter)
        
    return result

Funktio luo listan events, johon lisätään jokaista asiakasta kohden kaksi tapahtumaa pareina. Asiakkaan saapumisaika lisätään muodossa (time, 1) ja asiakkaan lähtöaika muodossa (time, 2). Sitten funktio järjestää listan, minkä seurauksena tapahtumat järjestyvät niiden ajan mukaan.

Tapahtumien järjestämisen jälkeen lista events käydään läpi ja muuttuja counter pitää yllä asiakkaiden määrää. Muuttujaan result tallennetaan muuttujan counter suurin arvo tapahtumien käsittelyn aikana.

Tuloksena oleva algoritmi muodostuu kolmesta osasta. Tapahtumien luominen vie aikaa \(O(n)\), koska jokaisesta asiakkaasta muodostetaan kaksi tapahtumaa. Tapahtumien järjestäminen vie aikaa \(O(n \log n)\) ja tapahtumien läpikäynti vie aikaa \(O(n)\). Niinpä koko algoritmin aikavaativuus on \(O(n \log n)\).

Miten järjestäminen toimii?

Järjestämisalgoritmille annetaan lista alkioita ja sen tehtävänä on saada alkiot suuruusjärjestykseen. Yleensä lähtökohtana on, että algoritmi voi vertailla alkioita toisiinsa sekä vaihtaa alkioiden paikkoja listalla.

Yksinkertaiset järjestämisalgoritmit perustuvat vierekkäisten alkioiden vaihtamiseen keskenään ja niiden aikavaativuus on \(O(n^2)\). Yksi tällainen algoritmi on lisäysjärjestäminen (insertion sort), joka käy listan läpi vasemmalta oikealle ja siirtää kunkin alkion oikeaan kohtaan listan alkuosassa.

Vain vierekkäisiä alkioita käsittelevä järjestämisalgoritmi ei voi koskaan olla tehokas, koska tarvittava vaihtojen määrä voi olla suuri. Esimerkiksi jos lista on käänteisessä järjestyksessä, tarvitaan luokkaa \(n^2\) vaihtoa. Yleisemmin tarvittava vierekkäisten alkioiden vaihtojen määrä on yhtä suuri kuin listan inversioiden määrä. Inversio tarkoittaa listalla olevaa alkioparia, jotka ovat väärässä järjestyksessä.

Järjestämiseen on olemassa myös tehokkaita algoritmeja, joiden aikavaativuus on \(O(n \log n)\). Yksi tällainen algoritmi on lomitusjärjestäminen (merge sort), joka järjestää ensin listan vasemman ja oikean puoliskon erikseen ja yhdistää sitten järjestetyt puoliskot kokonaiseksi järjestetyksi listaksi. Algoritmi toimii rekursiivisesti niin, että se järjestää myös puoliskot vastaavalla tavalla, jne.

Pythonin käyttämä järjestämisalgoritmi on Timsort, jossa on sekä lisäysjärjestämisen että lomitusjärjestämisen piirteitä. Algoritmin aikavaativuus on \(O(n \log n)\), ja se on suunniteltu niin, että se on erityisen tehokas monissa käytännössä vastaan tulevissa tilanteissa.

Järjestämisen toiminnan tutkiminen

Seuraava koodi havainnollistaa, mitä Python tekee järjestäessään listan sisällön:

import functools

def cmp(a, b):
    print("compare", a, b)
    return a - b

numbers = [4, 1, 3, 2]
numbers.sort(key=functools.cmp_to_key(cmp))
print(numbers)

Kun metodia sort kutsutaan yllä olevalla tavalla, se vertailee listalla olevien alkioiden järjestystä kutsumalla funktiota cmp. Funktio cmp saa parametreina alkiot a ja b ja sen tulee palauttaa

• negatiivinen arvo, jos a on pienempi kuin b,
• positiivinen arvo, jos a on suurempi kuin b, ja
• nolla, jos a ja b ovat yhtä suuria.

Metodi sort muuttaa listan alkioiden järjestystä funktion cmp perusteella. Funktio cmp tulostaa kaikki tekemänsä vertailut, mikä antaa tietoa metodin sort tekemistä vertailuista. Koodin tulostus on seuraava:

compare 1 4
compare 3 1
compare 3 4
compare 3 1
compare 2 3
compare 2 1
[1, 2, 3, 4]

Tämä tarkoittaa, että metodi sort vertailee ensin lukuja 1 ja 4, sitten lukuja 3 ja 1, jne. Kuuden vertailun jälkeen metodi on saanut listan järjestykseen.

Järjestämisen alaraja

On mahdollista osoittaa, että \(O(n \log n)\) on paras mahdollinen aikavaativuus yleiskäyttöiselle järjestämisalgoritmille. Tässä oletuksena on, että algoritmi vertailee alkioita toisiinsa ja muuttaa sen perusteella niiden järjestystä.

Tarkastellaan tilannetta, jossa algoritmille annetaan \(n\) alkion lista, jossa jokainen luku väliltä \(1 \dots n\) esiintyy tasan kerran. Listan alkiot voivat olla \(n!\) eri järjestyksessä, ja kussakin tapauksessa algoritmin tulee toimia eri tavalla, jotta lista tulee järjestykseen.

Kun algoritmi vertailee kahta alkiota toisiinsa, tämä antaa algoritmille tietoa, jota se voi käyttää järjestämisessä. Tarkastellaan tilannetta, jossa \(n=3\) ja algoritmi ei ole vielä tehnyt vertailuja. Koska algoritmilla ei ole vielä tietoa listasta, algoritmin näkökulmasta lista voi olla mikä tahansa seuraavista:

Oletetaan sitten, että algoritmi vertailee listan kahta ensimmäistä alkiota toisiinsa ja saa tietää, että ensimmäinen alkio on suurempi kuin toinen alkio. Tämän perusteella algoritmi pystyy rajaamaan tilannetta niin, että lista on jokin seuraavista:

Jotta algoritmi toimii oikein, sen täytyy päästä vertailuja tekemällä tilanteeseen, jossa on vain yksi mahdollinen lista ja algoritmi voi järjestää sen oikealla tavalla. Listojen määrä alussa on \(n!\) ja jokaisen vertailun jälkeen ainakin puolet listoista voi jäädä jäljelle. Niinpä tarvitaan ainakin \(\log_2(n!)\) vertailua, ennen kuin algoritmi on saanut varmasti riittävästi tietoa listasta. Tästä saadaan alaraja

eli algoritmin täytyy tehdä luokkaa \(n \log n\) vertailua.

Huomaa, että järjestäminen voi olla mahdollista toteuttaa tehokkaammin, jos sen riittää toimia vain tietyn tyyppisillä alkioilla. Jos esimerkiksi alkiot ovat pieniä kokonaislukuja, järjestäminen on mahdollista toteuttaa ajassa \(O(n)\). Yksi tällainen algoritmi on laskemisjärjestäminen (counting sort).

Järjestäminen muissa kielissä

Eri ohjelmointikielissä on valmiita menetelmiä järjestämiseen. Kielten välillä on eroja siinä, mihin algoritmeihin järjestäminen perustuu, mutta yleensä valmiit menetelmät ovat tehokkaita ja ne on toteutettu hyvin.

C++:ssa on saatavilla funktio std::sort, jolle annetaan parametrina iteraattori järjestettävän välin alkuun ja loppuun. Funktiota voidaan käyttää seuraavasti:

std::vector<int> numbers;
...
std::sort(numbers.begin(), numbers.end());

Javassa voidaan käyttää luokan Collections metodia sort:

ArrayList<Integer> numbers = new ArrayList<>();
...
Collections.sort(numbers);

JavaScriptissa taulukon metodi sort järjestää sen sisällön. Metodin käyttäminen voi kuitenkin aiheuttaa yllätyksiä:

numbers = [1, 2, 3, 11, 12, 13];
numbers.sort();
console.log(numbers); // [1, 11, 12, 13, 2, 3]

Syynä tähän on, että metodi sort käsittelee alkioita oletuksena merkkijonoina, minkä vuoksi esimerkiksi 11 on pienempi kuin 2. Metodille voi kuitenkin antaa seuraavasti vertailufunktion lukujen järjestämistä varten:

numbers = [1, 2, 3, 11, 12, 13];
numbers.sort((a, b) => a - b);
console.log(numbers); // [1, 2, 3, 11, 12, 13]