5. Järjestäminen

Järjestäminen (sorting) on klassinen algoritmiikan ongelma, jossa tehtävänä on järjestää annetut alkiot suuruusjärjestykseen. Järjestämiseen on kehitetty tehokkaita algoritmeja, jotka toimivat ajassa \(O(n \log n)\).

Tässä luvussa näemme, miten järjestämistä voi käyttää Pythonissa ja mitä hyötyä siitä voi olla tehokkaiden algoritmien toteuttamisessa. Tutustumme myös järjestämisen teoriaan ja muutamaan yleiseen järjestämisalgoritmiin.

Järjestäminen Pythonissa

Pythonissa listan sisältö voidaan järjestää metodilla sort:

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

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

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

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

Metodi sort ja funktio sorted toimivat tehokkaasti ajassa \(O(n \log n)\), minkä ansiosta niitä voidaan käyttää tehokkaiden algoritmien toteuttamisessa.

Esimerkki: Pienin ero

Tehtävä

Järjestetyssä listassa pienin ero on aina kahden vierekkäisen luvun välillä. Niinpä voimme ratkaista tehtävän tehokkaasti järjestämällä listan ja käymällä läpi kaikki vierekkäin olevat luvut. Esimerkiksi lista \([4,1,7,3,9]\) on järjestettynä \([1,3,4,7,9]\), jolloin pienimmän eron tuottavat luvut \(3\) ja \(4\) ovat vierekkäin.

Seuraava funktio min_diff toteuttaa algoritmin:

def min_diff(numbers):
    numbers = sorted(numbers)

    result = numbers[1] - numbers[0]
    for i in range(2, len(numbers)):
        result = min(result, numbers[i] - numbers[i - 1])

    return result

Algoritmi järjestää ensin listan kutsumalla funktiota sorted ja selvittää sitten muuttujaan result pienimmän eron kahden vierekkäisen luvun välillä.

Listan järjestäminen vie aikaa \(O(n \log n)\) ja vierekkäisten lukujen vertaileminen vie aikaa \(O(n)\), joten algoritmin aikavaativuus on \(O(n \log n)\).

Sivuvaikutusten välttäminen

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

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

Tässä olisi kuitenkin ongelmana, että funktio aiheuttaisi sivuvaikutuksen, koska parametrina annetun listan järjestäminen heijastuisi 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 = [4, 1, 7, 3,9]
print(min_diff(numbers)) # 1
print(numbers) # [1, 3, 4, 7, 9]

Käytössä sorted

numbers = [4, 1, 7, 3,9]
print(min_diff(numbers)) # 1
print(numbers) # [4, 1, 7, 3,9]

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. Niinpä parempi ratkaisu on toteuttaa funktio alkuperäisellä tavalla käyttäen funktiota sorted.

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, len(numbers)):
        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 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 algoritmin tehokkuuteen, lisätään listalle satunnaisia lukuja väliltä \(1 \dots k\), missä \(k\) vaihtelee. Tämän avulla voidaan tutkia, miten lukujen suuruus 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:

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.sort()

    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 aikojen 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, joka käy listan läpi vasemmalta oikealle ja siirtää kunkin alkion oikeaan kohtaan listan alkuosassa.

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

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.

Yleisessä tapauksessa ei ole mahdollista luoda järjestämisalgoritmia, jonka aikavaativuus olisi tehokkaampi kuin \(O(n \log n)\). Tämä voidaan todistaa määrittämällä alaraja sille, montako kahden alkion vertailua algoritmissa tulee olla pahimmassa tapauksessa.

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.

Tässä cmp on toteutettu niin, että se palauttaa lausekkeen a - b arvon, minkä ansiosta se järjestää alkiot pienimmästä suurimpaan.

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ä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 = [2, 11, 1, 3];
numbers.sort();
console.log(numbers); // [1, 11, 2, 3]

Tässä järjestettävänä on kokonaislukuja sisältävä lista, mutta luku 11 menee järjestykseen ennen lukua 2. Syynä tähän on, että metodi sort käsittelee alkioita oletuksena merkkijonoina, jolloin 11 on pienempi kuin 2. Metodille voi kuitenkin antaa seuraavasti vertailufunktion lukujen järjestämistä varten:

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