Home / Algoritmalar / Jump Search Algoritması

Jump Search Algoritması

Jump Search tıpkı Binary Search Algoritması gibi sıralı dizi üzerine uygulanabilir. Jump Search’teki arama mantığı adından da anlaşılacağı üzere belirli aralıklarla atlayıp Lineer Search ile aranılan elemanı bulmayı hedefler. Şanslı bir atlamada ise direkt olarak aranılan sayı bulunmuş olur, Lineer Search’e gerek kalmaz.

Jump Search Algoritması

İçerik

Dediğimiz şeyi biraz daha aydınlatalım. mesela 16 elemanlı bir dizimiz var. Biz atlama adımını 4 olarak ayarladık. (keyfimize göre ayarlayabiliriz) biz 0. indisten başlar ve 0-4 4-8 8-12 12-16 diye diziyi kontrol ederiz. Temel kriter şudur, eğer şanslı isek aradığımız sayıyı atlama sırasında buluruz ve indisi return ederiz.u

Ancak şanslı değilsek ne yaparız? Önce şunu diyelim, 0. indisten 4. indise atladık, eğer 4. indisteki sayı aradığımız sayıdan küçükse atlamaya devam ederiz, ancak eğer küçükse atlama yapılmaz, bu sefer sola doğru (3 – 2 – 1) lineer search yaparız. Böylelikle aradığımız elemanı daha küçük bir aralıkta bulmuş oluruz.

Jump Search Algoritması Örnek

Dizimizin sayıları aşağıdaki gibi olsun

10 20 30 40 50 60 70 80 90 100 120 140 160 180 200 222

Aradığımız sayı 160 olsun.

Atlama aralığımızda 4 olsun

1. Adım: 0 dan 4’e atlarız 4.  sayı 40. 160’tan küçük olduğu için devam ederiz.

2. Adım: 5’ten 8’e atlarız. 8. sayı 80. 160’tan küçük olduğu için devam ederiz.

3. Adım: 8’den 12’ye atlarız. 12. sayı 140. 160’tan küçük olduğu için devam ederiz.

4. Adım: 12’den 16’ya atlarız. 16. sayı 222. 160’tan büyük, bu sefer sola doğru lineer search yaparız.

Lineer Search Adımları.

L1 : 200 160’tan büyük

L2: 180 160’tan büyük

L3: Bu adımda 160’ı bulduk. Böylece indisi return ederiz.

Gördüğünüz üzere 7 Adımda (4 Jump, 3 Lineer) aradığımız sayıyı bulduk. Halbuki direkt Lineer search deneseydik 13 adımda aradığımız sayıyı bulabilecektik.

Jump Algoritmasının Optimize Edilmesi

Jump Arama algoritmasında atlama aralığını keyfimize göre seçebileceğimizi söyledik, ancak bu aralığın seçimi oldukça önemlidir. Bunun için optimal bir yol bulunmuş ve atlama aralığının toplam eleman sayısının karekökü olması gerektiği söylenmiş. Bu sayede optimal bir sonuca ulaşabiliyoruz.

Jump Algoritması C Kodu


#include <stdio.h>
#include <math.h>

int min(int a, int b) {
	return a < b ? a : b;
}

int jumpSearch(int arr[], int n, int val) {
    int jump = (int) sqrt(n);
    int left = 0;
    int right = 0;
	
    while (left < n && arr[left] <= val) {
        right = min(n - 1, left + jump);

        if (arr[left] <= val && arr[right] >= val) {
            break;
        }

        left += jump;
    }

    if (left >= n || arr[left] > val) {
        return -1;
    }

    right = min(n - 1, right);
	
	int i;
	
    for (i = left; i <= right && arr[i] <= val; ++i) {
        if (arr[i] == val) {
            return i;
        }
    }

    return -1;
}

int main()
{
	int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
	int n = 8;

    printf("%d\n", jumpSearch(arr, n, 0)); // -1
    printf("%d\n", jumpSearch(arr, n, 3)); // 1
    printf("%d\n", jumpSearch(arr, n, 11)); // 5
    printf("%d\n", jumpSearch(arr, n, 16)); // -1

    return 0;
}

Jump Search Algoritması Java Kodu


public class JumpSearch
{
    public static int jumpSearch(int[] arr, int x)
    {
        int n = arr.length;

        int step = (int)Math.floor(Math.sqrt(n));

        int prev = 0;
        while (arr[Math.min(step, n)-1] < x)
        {
            prev = step;
            step += (int)Math.floor(Math.sqrt(n));
            if (prev >= n)
                return -1;
        }

        while (arr[prev] < x)
        {
            prev++;

            if (prev == Math.min(step, n))
                return -1;
        }

        if (arr[prev] == x)
            return prev;
 
        return -1;
    }

    public static void main(String [ ] args)
    {
        int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
                     34, 55, 89, 144, 233, 377, 610};
        int x = 55;

        int index = jumpSearch(arr, x);

        System.out.println("\nNumber " + x +
                            " is at index " + index);
    }
}

Jump Search Algoritması Python Kodu


import math

def jump_search(alist, val):
	
	length = len(alist)
	
	# Calculating jump
	jump = int(math.sqrt(length))
	
	left, right = 0, 0

	while left < length and alist[left] <= val:
		right = min(length - 1, left + jump)
		
		if alist[left] <= val and alist[right] >= val:
			break
			
		left += jump;
		
	if left >= length or alist[left] > val:
		return -1
		
	right = min(length - 1, right)
	
	i = left
	while i <= right and alist[i] <= val:
		if alist[i] == val:
			return i
		i += 1
	
	return -1
	
    
alist = [1, 3, 5, 7, 9, 11, 13, 15, 17]

print(jump_search(alist, 0))	# -1
print(jump_search(alist, 3))	#  1
print(jump_search(alist, 11))	#  5
print(jump_search(alist, 16))	# -1

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir