[[:oktatas:programozás:programozási tételek|< Programozási tételek]]

====== Programozási tételek Java megvalósításban ======

  * **Szerző:** Sallai András
  * Copyright (c) Sallai András, 2011, 2016, 2017, 2023
  * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]]
  * Web: https://szit.hu

===== Tételek =====

==== Összegzés ====

<code java Program.java>
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		
		int osszeg = 0;
		for(int i=0; i<7; i++)
			osszeg = osszeg + tomb[i];
		
		System.out.println(osszeg);
	}
}
</code>



==== Megszámolás ====

<code java Program.java>
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7;
		int szamlalo = 0;
		for(int i=0; i<n; i++)
			if(tomb[i] > 5)
				szamlalo++;

		System.out.println(szamlalo);
	}
}
</code>


==== Eldöntés tétel ====

<code java Program.java>

class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int ker = 2; //Amiről el szeretnénk dönteni, hogy van-e ilyen

		int i = 0;
		while(i<n && tomb[i] != ker)
			i++;
		
		if(i<n)
			System.out.println("Van ilyen szám.");
		else
			System.out.println("Nincs ilyen szám.");
	}
}
</code>

==== Kiválasztás tétel ====

<code java Program.java>

class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int ker = 2; //Amiről szeretnénk tudni, hogy hányadik helyen van

		int i = 0;
		while(tomb[i] != ker)
			i++;
		
		System.out.printf("%d\n", i + 1);
	}
}
</code>


==== Keresés tétel ====

<code java Program.java>
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int ker = 2; //Amit keresünk

		int i = 0;
		while(i<n && tomb[i] != ker)
			i++;
		
		if(i<n) {
                        //Ha a kérdés az, hogy hányadik akkor i + 1 a vége
                        //ha a kérdés az, hogy mi az indexe, akkor csak i
			System.out.printf("Van ilyen a következő helyen: %d\n", i + 1); 
                            
		}else {
			System.out.println("Nincs ilyen elem");
                }
	}
}
</code>

==== Kiválogatás tétel ====


<code java Program.java>
class Program
{
	public static void main(String[] argv)
	{		
		int[] a = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int[] b = new int[n];
		int j=0;
		for(int i=0; i<n;i++)
			if(a[i] > 5)
				b[j++] = a[i];
		
		int m = j; //A "b" tömb elemeinek száma
		
		//Első tömb kiíratva:
		for(int i=0; i<n;i++)
			System.out.print(a[i] + " ");
		System.out.println();

		//Második tömb kiíratva:
		for(int i=0; i<m;i++)
			System.out.print(b[i] + " ");
		System.out.println();
		
	}
}
</code>


==== Szétválogatás tétel ====

<code java Program.java>

class Program
{
	public static void main(String[] argv)
	{		
		int[] a = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int[] b = new int[n];
		int[] c = new int[n];
		
		int j=0;
		int k=0;
		for(int i=0; i<n;i++)
			if(a[i] > 5)
				b[j++] = a[i];
			else
				c[k++] = a[i];
		
		int m = j; //A "b" tömb elemeinek száma
		int l = k; //A "c" tömb elemeinek száma
		
		//Első tömb kiíratva:
		for(int i=0; i<n;i++)
			System.out.print(a[i] + " ");
		System.out.println();

		//Második tömb kiíratva:
		for(int i=0; i<m;i++)
			System.out.print(b[i] + " ");
		System.out.println();

		//Harmadik tömb kiíratva:
		for(int i=0; i<l;i++)
			System.out.print(c[i] + " ");
		System.out.println();
		
	}
}
</code>

==== Metszet tétel ====

<code java Program.java>

class Program
{
	public static void main(String[] argv)
	{		
		int[] a = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // Az első tömb elemeinek száma
		int[] b = {4, 7, 9, 8, 2};
		int m = 5; //A második tömb elemeinek száma
		int[] c = new int[n+m]; //A harmadik tömb
		
		int j;
		int k = 0;
		for(int i=0; i<n;i++)
		{
			j = 0;
			while(j<m && b[j] != a[i])
				j++;
			if(j<m)
			{
				c[k] = a[i];
				k++;
			}
		}
		
		int l = k; //A "c" tömb elemeinek száma
		
		//Első tömb kiíratva:
		for(int i=0; i<n;i++)
			System.out.print(a[i] + " ");
		System.out.println();

		//Második tömb kiíratva:
		for(int i=0; i<m;i++)
			System.out.print(b[i] + " ");
		System.out.println();

		//Harmadik tömb kiíratva:
		for(int i=0; i<l;i++)
			System.out.print(c[i] + " ");
		System.out.println();
		
	}
}
</code>

==== Unió tétel ====


<code java Program.java>
/* Unió tétel */
class Program7
{
	public static void main(String[] argv)
	{		
		int[] a = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // Az első tömb elemeinek száma
		int[] b = {4, 7, 9, 8, 2};
		int m = 5; //A második tömb elemeinek száma
		int[] c = new int[n+m]; //A harmadik tömb
		
		for(int i=0; i<n; i++)
			c[i] = a[i];
		
		int k = n-1;

		for(int j=0; j<m;j++)
		{
			int i = 0;
			while(i<n && a[i] != b[j])
				i++;
			if(i>=n)
			{
				k++;
				c[k] = b[j];	
			}
		}
		
		int l = k + 1; //A "c" tömb elemeinek száma
		
		//Első tömb kiíratva:
		for(int i=0; i<n;i++)
			System.out.print(a[i] + " ");
		System.out.println();

		//Második tömb kiíratva:
		for(int i=0; i<m;i++)
			System.out.print(b[i] + " ");
		System.out.println();

		//Harmadik tömb kiíratva:
		for(int i=0; i<l;i++)
			System.out.print(c[i] + " ");
		System.out.println();
		
	}
}
</code>

==== Maximum kiválasztás tétele ====

<code java Program.java>

class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma

		int max = tomb[0];

		for(int i=0; i<n;i++)
			if(tomb[i] > max)
				max = tomb[i];

		System.out.println("Legnagyobb: " + max);

	}
}
</code>

==== Minimumkiválasztás tétele ====


<code java Program.java>

class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma

		int min = tomb[0];

		for(int i=0; i<n;i++)
			if(tomb[i] < min)
				min = tomb[i];

		System.out.println("Legkisebb: " + min);

	}
}
</code>


===== Rendezések =====

==== Buborék rendezés ====

<code java Program.java>
/* Buborék rendezés */
class Program
{
	public static void main(String args[])
	{
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		
		for(int i= n-1; i>0; i--)
			for(int j=0; j<i; j++)
				if(tomb[j] > tomb[j+1])
				{
					int tmp = tomb[j];
					tomb[j] = tomb[j+1];
					tomb[j+1] = tmp;
				}
		
		for(int i=0; i<n; i++)
			System.out.print(tomb[i] + " ");
		System.out.println();
	}
}
</code>


Vagy:

<code java Program.java>
/* Buborék rendezés */
class Program
{
	public static void main(String args[])
	{
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		
		for(int i= n-2; i>0; i--)
			for(int j=0; j<=i; j++)
				if(tomb[j] > tomb[j+1])
				{
					int tmp = tomb[j];
					tomb[j] = tomb[j+1];
					tomb[j+1] = tmp;
				}
		
		for(int i=0; i<n; i++)
			System.out.print(tomb[i] + " ");
		System.out.println();
	}
}
</code>
Utóbbi különbsége: mettől-meddig megyünk a ciklusban.

==== Beszúrásos rendezés ====

Rekurzív megvalósítás:
<code java Program01.java>

package rendezesbeszurassal;

public class RendezesBeszurassal {

    static void rendezesBeszurassalR(int[] t, int n) {        
        if(n>0) { // eredeti: n>1
            rendezesBeszurassal(t, n-1);
            int x = t[n-1]; // eredeti: t[n]
            int j = n-2; // eredeti: n-1
            while(j>= 0 && t[j]>x) {
                t[j+1] = t[j];
                j = j-1;
            }
            t[j+1] = x;
        }
    }
    static void kiir(int[] t) {
        for (int i = 0; i < t.length; i++) {
            System.out.print(t[i]+" ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] t = {35, 24, 83, 12, 7, 23};
        rendezesBeszurassalR(t, t.length);
        kiir(t);
    }
    
}

</code>

Normál megvalósítás:
<code java>
    static void rendezesBeszurassal(int[] t) {
        for (int i = 0; i < t.length; i++) {  //eredeti: i=1
            int x = t[i];
            int j = i - 1;
            while(j>=0 && t[j]>x) {
                t[j+1] = t[j];
                j = j - 1;
            }
            t[j+1] = x;
        }
    }
</code>


A megjegyzések azokra a tömbökre utalnak, ahol a kezdőérték 1.

==== Gyorsrendezés ====

Különböző változatokat látunk itt a gyorsrendezésre.


A tömböt felosztjuk három részre. Egy kisebb, egy egyenlő és egy nagyobb részre, a pivot elem alapján. Ezt követően rekurzívan hívja önmagát az egyes részekre.


<code java Program01.java>
import java.util.ArrayList;
import java.util.Arrays;


public class Program01 {
    static ArrayList<Integer> quicksort(ArrayList<Integer> list) {
        if (list.size() <= 1) {
            return list;
        }
        ArrayList<Integer> less = new ArrayList<>();
        ArrayList<Integer> equal = new ArrayList<>();
        ArrayList<Integer> greater = new ArrayList<>();
        int pivot = list.get(list.size()-1);
        for (Integer x : list) {
            if (x < pivot) less.add(x);
            if (x == pivot) equal.add(x);
            if (x > pivot) greater.add(x);
        }        
        ArrayList<Integer> sumList = new ArrayList<Integer>();
        sumList.addAll(quicksort(less));
        sumList.addAll(equal);
        sumList.addAll(quicksort(greater));        
        return sumList;
    }

    static void kiirLista(ArrayList<Integer> list) {
        for(Integer x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Integer[] t = {8, 2, 7, 9, 5, 4, 3};
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(t));
        list = quicksort(list);
        kiirLista(list);
    }
}

</code>



A következő **helyben rendező** változat hatékonyabb lehet nagyobb méretű elem számnál, mivel nem készít újabb tömböket, helyette a bemeneti tömbön dolgozik.

A bal és jobb széleket azért kell megadni, mert rekurzióban így egyre kisebb tömböket kell átnéznie az algoritmusnak. Így a tömb rendezésekor a második paraméter mindig 0, a harmadik paraméter mindig n-1, ahol n a tömb elemeinek száma. 


A következő példa tömbön dolgozik:


<code java Program.java>
class Program
{
	static void gyors(int[] tomb, int bal, int jobb)
	{
		if(bal < jobb)
		{
			int also = bal, felso = jobb + 1, kulcs = tomb[bal];
			for( ; ; )
			{
				while(++also < felso && tomb[also] < kulcs)
					;
				while(tomb[--felso] > kulcs)
					;
				if(also >= felso)
					break;
				csere(tomb, also, felso);
			}	
			csere(tomb, felso, bal);
			gyors(tomb, bal, felso -1);
			gyors(tomb, felso+1, jobb);			
		}
	}

	static void csere(int[] tomb, int i, int j)
	{
		int seged = tomb[i];
		tomb[i] = tomb[j];
		tomb[j] = seged;
	}

	public static void main(String args[])
	{
		int[] tomb = {8, 5, 2, 9, 4, 3, 1, 6};
		int meret = 8;
		
		gyors(tomb, 0, 7);
		
		for(int i=0; i<meret; i++)
			System.out.print(tomb[i] + " ");
		System.out.println();
	}
}
</code>


Ez is helyben rendező, de listán dolgozik.

<code java Program01.java>

import java.util.ArrayList;
import java.util.Arrays;

public class Program01 {

    static void quicksort(ArrayList<Integer> list, int lo, int hi) {
        if(lo < hi) {
            int p = partition(list, lo, hi);
            quicksort(list, lo, p-1);
            quicksort(list, p+1, hi);
        }
    }
    static int partition(ArrayList<Integer> list, int lo, int hi) {
        int pivot = list.get(hi);
        int i = lo -1;
        for (int j = lo; j < hi; j++) {
            if(list.get(j)<= pivot) {
                i++;
                swap(list, i, j);
            }
        }
        swap(list, i+1, hi);
        return i + 1;
    }
    static void swap(ArrayList<Integer> list, int i, int j) {
        int tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }
    static void kiir(ArrayList<Integer> list) {
        for(Integer x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Integer[] t = {8, 2, 7, 3, 4, 9};
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(t));
        quicksort(list, 0, list.size()-1);
        kiir(list);
    }
    
}
</code>

Ne felejtsük el, hogy a listáknak vannak saját rendező metódusaik is.


==== Shell rendezés ====


<code java Program.java>
class Program
{
	public static void main(String args[])
	{
		int[] tomb = {8, 5, 2, 9, 4, 3, 1, 6};
		int[] leptomb = {5, 3, 1};
		
		int meret = 8;
		
		for(int k = 0; k< 3; k++)
		{
			int lepeskoz = leptomb[k];
			for(int j = lepeskoz; j < meret; j++)
			{
				int i = j - lepeskoz;
				int kulcs = tomb[j];
				while(i>=0 && tomb[i] > kulcs)
				{
					tomb[i + lepeskoz] = tomb[i];
					i = i - lepeskoz;
				}
				tomb[i + lepeskoz] = kulcs;
			}
		}
		
		for(int i=0; i<meret; i++)
			System.out.print(tomb[i] + " ");
		System.out.println();
	}
}
</code>

===== Összefuttatás =====
==== Összefuttatás, összefésülés ====

<code java Program01.java>
class Program01{
	public static void main(String[] args) {
		int[] a = { 1, 3, 5, 7, 9};
		int[] b = {2, 4, 6, 8 };
		
		int[] c = new int[a.length+b.length];
		
		int n = a.length;
		int m = b.length;
		
		int i = 0;
		int j = 0;
		int k = -1;
		while(i<n && j<m) {
			k++;
			if(a[i]<b[j]) {
				c[k] = a[i];
				i++;
			}else if(a[i] == b[j]) {
				c[k] = a[i];
				i++;
				j++;				
			}else if(a[i] > b[j]) {
				c[k] = b[j];
				j++;
			}
		}
		while(i<n) {
			k++;
			c[k] = a[i];
			i++;
		}
		while(j<m) {
			k++;
			c[k] = b[j];
			j++;
		}
		
		kiir(c, k);
		
	}
	public static void kiir(int[] tomb, int meret) {		
		for (int i = 0; i < meret + 1; i++) {			
			System.out.println(tomb[i]);
		}		
	}

</code>

===== Keresés rendezett tömbben =====
==== Logaritmikus keresés ====

<code java Program01.java>
public class Program01 {
	public static void main(String[] args) {
		
		int[] t={3, 4, 6, 8, 18, 50, 52, 61, 68, 70};	
		
		int n = t.length;		
		
		int e = 0;
		int u = n-1;
		int k;
		int ker = 52;
		do {
			k = (e+u) / 2;
			if(ker<t[k]) u = k-1;
			if(ker>t[k]) e = k+1;
		}while(e<=u && t[k]!=ker);
		boolean van = e<=u;
		int index = 0;
		
		if(van) {			
			index = k;
		}
		System.out.printf("%s %d\n", van, index);
		
	}
}
</code>