Searching and Sorting

Searching

Boolean search: does the element belong to the set ("yes-no") vs. place search if "place" is defined (index).
Linear search.
Binary search (bisection of interval).
Hashtable: hash function (hashcode), collision, collision handling schemes, separate chaining, open addressing, linear probing, double hashing.
Running time of different operations for different methods.

Sorting

Abstract properties - time complexity and space complexity, average and worst case, running time in practice, ease of programming.
Stable and unstable methods.
"Slow" methods - quadratic: insertion sort
"Quick" general methods - nlogn: quicksort (unstable), merge sort (extra memory), binary insertion sort (homework!), heapsort (discussed later). Divide and conquer strategies.
Special methods: counting sort, radix sort, bucket sort.

Otsimine ja järjestamine

Otsimise ülesanne

Tuvastada etteantud elemendi kuuluvus etteantud struktuuri.
Tulemuseks võib sõltuvalt ülesandest olla: tõeväärtus (kuulub-ei kuulu), "asukoht" struktuuris (või signaal mittekuulumise kohta), element ise vms.
Meie näidetes üritame leida elemendi asukohta.

Kahendotsimine (Binary Search)

"Lõigu poolitamine" matemaatikas. On rakendatav kahel eeltingimusel:

vaadeldav struktuur on järjestatud

elemendid on indekseeritavad

O(log n)

def bsearch(arr, value):
    n = len(arr)
    if n == 0:
        return -1
    if value > arr[n - 1]:
        return -1
    left = 0
    right = len(arr)
    while left <= right:
        mid = int((left + right) / 2)
        x = arr[mid]
        if value == x:
            return mid
        else:
            if value > x:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Paisktabel

Lugeda vastav peatükk õpikust!

Võtmed, võtmeruum, paisktabel, paiskfunktsioon, kollisioonid, välisahelad, lahtine adresseerimine, topeltpaiskamine

Lisamine ja otsimine: O(1)

Järjestamismeetodid

Abstraktne keerukus, konkreetne keerukus (keskmine, halvim), mäluvajadus, algoritmi lihtsus, stabiilsus, ...

"Aeglased" meetodid: O(n²)

lihtne pistemeetod

mullimeetod

valikumeetod

"Kiired" meetodid: O(nlogn)

kahendpistemeetod

Shelli meetod

kiirmeetod (Hoare'i meetod)

kuhjameetod

ühildusmeetod

Erimeetodid (kitsendustega): O(n)

loendamismeetod

positsioonimeetod

kimbumeetod

Vaata ka www.sorting-algorithms.com

Naiivseid meetodeid:

SyntaxEditor Code Snippet

def bubblesort(arr):
    if len(arr) < 2:
        return
    unsorted = True
    while unsorted:
        unsorted = False
        for i in range(1, len(arr)):
            if arr[i-1] > arr[i]:
                unsorted = True
                tmp = arr[i-1]
                arr[i-1] = arr[i]
                arr[i] = tmp


def selectionsort(arr):
    if len(arr) < 2:
        return
    for m in range(0, len(arr) - 1):
        minind = m
        minel = arr[m]
        for i in range(m+1, len(arr)):
            if arr[i] < arr[minind]:
                minind = i
                minel = arr[i]
        arr[m+1:minind+1] = arr[m:minind]
        arr[m] = minel

Pistemeetod (Insertion Sort):

Jada jagatakse "järjestatud osaks" (algselt tühi) ja "järjestamata osaks" (algselt kogu jada).
Järjestatud osa pikkust suurendatakse järjekordse elemendi paigutamisega õigele kohale järjestatud osas.

  SyntaxEditor Code Snippetdef insertionsort(arr):
    if len(arr) < 2:
        return
    for i in range(1, len(arr)):
        b = arr[i]
        j = i - 1
        while j >= 0:
            if arr[j] <= b:
                break
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = b

Kahendpistemeetod:

"Õige" koht leitakse kahendotsimisega: O(nlogn), kui "pistmine" oleks O(1)

SyntaxEditor Code Snippet

def binsertionsort(arr):
    if len(arr) < 2:
        return
    for i in range(1, len(arr)):
        b = arr[i]
        left = 0
        right = i
        while left < right:
            mid = int((left + right) / 2)
            if b < arr[mid]:
                right = mid
            else:
                left = mid + 1
        arr[left+1:i+1] = arr[left:i]
        arr[left] = b

Ühildusmeetod (Merge Sort):

"Jaga ja valitse" : jagatakse kogu aeg pooleks (kuni pikkus < 2), pooled ühendatakse lineaarse keerukusega ühildamise abil, kasutatakse lisamälu mahuga O(n)

SyntaxEditor Code Snippet

def mergesort(arr, left, right):
    if len(arr) < 2 or (right - left) < 2:
        return
    k = int((left + right)/2)
    mergesort(arr, left, k)
    mergesort(arr, k, right)
    merge(arr, left, k, right)


def merge(arr, left, k, right):
    if len(arr) < 2 or (right - left) < 2 or k <= left or k >= right:
        return
    tmp = [0] * (right - left)
    n1 = left
    n2 = k
    m = 0
    while True:
        if n1 < k and n2 < right:
            if arr[n1] > arr[n2]:
                tmp[m] = arr[n2]
                n2 += 1
            else:
                tmp[m] = arr[n1]
                n1 += 1
            m += 1
        else:
            if n1 >= k:
                tmp[m:] = arr[n2:right]
            else:
                tmp[m:] = arr[n1:k]
            break
    arr[left:right] = tmp[:]

Kiirmeetod (Quicksort):

(Osa)jada jagatakse kaheks lühemaks osajadaks nii, et ükski element esimeses osas ei oleks suurem ühestki elemendist teises osas. Siis võib kummagi osa sorteerida eraldi (nad on sõltumatud). "Jaga ja valitse"

SyntaxEditor Code Snippet

def quicksort(arr, left, right):
    if (right - left) < 2:
        return
    x = arr[int((left + right) / 2)]
    i = left
    j = right - 1
    while i < j:
        while arr[i] < x:
            i += 1
        while arr[j] > x:
            j -= 1
        if i > j:
            break
        tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        i += 1
        j -= 1
    if left < j:
        quicksort(arr, left, j + 1)
    if i < right - 1:
        quicksort(arr, i, right)

J. Pöial