Geliştirme projeleri, çeşitli algoritmaları düşündüğünüzden daha sık kullanır. Örneğin, fazla çaba harcamadan veriler arasında gezinebilmek için bazı verileri belirli parametrelere (sütunlara) göre sıralamamız gerektiğini varsayalım. Bu nedenle, bir iş görüşmecisinin size belirli bir temel algoritma hakkında soru sorması ve belki de kod kullanarak onu uygulama görevini vermesi hiç de garip olmaz. Ve bu web sitesinde olduğunuza göre, Java ile yazdığınızı varsayacak kadar cesur olacağım. Bu nedenle bugün, bazı temel algoritmaları ve bunların Java'da nasıl uygulanacağına dair belirli örnekleri öğrenmenizi öneriyorum. "Bazı" derken şunu kastediyorum:
Dizi sıralama algoritmalarına genel bakış:
kabarcık sıralama,
seçim sıralaması,
ekleme sıralaması,
Kabuk sıralaması,
hızlı sıralama,
birleştirme sıralaması,
açgözlü algoritmalar
Yol bulma algoritmaları
derinlik öncelikli arama
genişlik öncelikli arama
Dijkstra'nın Önce En Kısa Yol algoritması
Neyse lafı daha fazla uzatmadan işimize dönelim.
1. Sıralama algoritmalarına genel bakış
Kabarcık sıralama
Bu sıralama algoritması öncelikle basitliği ile bilinir, ancak aynı zamanda en yavaş olanlardan biridir. Örnek olarak, artan düzende sayılar için bir kabarcık sıralaması düşünelim. Rastgele bir sayı dizisi düşünelim. Dizinin başından başlayarak bu sayılar üzerinde aşağıdaki adımları gerçekleştireceğiz:
iki sayıyı karşılaştırın;
soldaki sayı daha büyükse değiştirin;
bir konum sağa hareket ettirin.
Tüm dizide bu adımları gerçekleştirdikten sonra, en büyük sayının sayı dizimizin sonunda olduğunu göreceğiz. Ardından, yukarıdakiyle tamamen aynı adımları uygulayarak dizinin üzerinden başka bir geçiş yaparız. Ancak bu sefer listenin son öğesini dahil etmeyeceğiz, çünkü bu en büyük sayıdır ve zaten sayılar sıralandığında tam olarak olması gereken yerdedir. Bir kez daha, bir sonraki en büyük sayıyı dizimizin sonuna taşıyacağız. Elbette bu, en büyük iki sayının uygun yerlerinde durduğu anlamına gelir. Yine tüm elemanlar gereken sırada olana kadar zaten yerlerinde olan elemanları hariç tutarak sıralama üzerinden geçişler yapıyoruz. Balon sıralamanın Java kodunda nasıl uygulandığına bir göz atalım:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
Gördüğünüz gibi, burada karmaşık bir şey yok. Her şey harika görünüyor ve tek bir eksiklik olmasa olurdu - kabarcık sıralama çok, çok yavaş. İç içe döngülere sahip olduğumuz için zaman karmaşıklığı O(N²)'dir. Elemanların üzerindeki dış döngü N kez gerçekleştirilir. İç döngü ayrıca N kez yürütülür. Sonuç olarak, N*N veya N² yinelemeleri elde ederiz.
Seçim sıralaması
Bu algoritma kabarcık sıralamaya benzer, ancak biraz daha hızlı çalışır. Yine örnek olarak artan düzende düzenlemek istediğimiz bir sayı dizisini ele alalım. Bu algoritmanın özü, tüm sayıları sırayla yinelemek ve aldığımız en küçük öğeyi seçmek ve onu en soldaki öğeyle (0. öğe) değiştirmektir. Burada balon sıralamaya benzer bir durumla karşı karşıyayız, ancak bu durumda sıralanan öğemiz en küçük olacaktır. Bu nedenle, elemanlardan bir sonraki geçiş, indeksi 1 olan elemandan başlayacaktır. Tüm elemanlar sıralanana kadar bu geçişleri tekrarlayacağız. Java'da uygulama:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
Bu algoritma kabarcık sıralamadan üstündür, çünkü burada gerekli kaydırma sayısı O(N²)'den O(N)'ye düşürülmüştür. Tüm liste boyunca tek bir öğe kullanmıyoruz, ancak karşılaştırma sayısı hala O(N²).
Ekleme sıralaması
Artan düzende düzenlemek istediğimiz başka bir sayı dizisini ele alıyoruz. Bu algoritma, işaretçinin solundaki tüm öğelerin zaten kısmen kendi aralarında sıralandığı bir işaretleyici yerleştirmekten oluşur. Algoritmanın her adımında, elemanlardan biri seçilecek ve kısmen sıralanmış dizide istenen konuma yerleştirilecektir. Böylece sıralanan kısım, tüm unsurlar incelenene kadar büyüyecektir. Halihazırda sıralanmış olan öğelerin alt kümesini nasıl elde edeceğinizi ve işaretçiyi nereye koyacağımızı nasıl belirlediğimizi merak ediyor musunuz? Ama ilk elemandan oluşan dizi zaten sıralandı, değil mi? Java'daki uygulamaya bir göz atalım:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
Bu tür sıralama, yukarıda açıklananlardan daha üstündür, çünkü aynı O(N²) çalışma süresine sahip olmasına rağmen, bu algoritma kabarcık sıralamadan iki kat daha hızlıdır ve seçim sıralamasından biraz daha hızlıdır.
Kabuk sıralaması
Bu sıralama aslında değiştirilmiş bir ekleme sıralamasıdır. Ne hakkında konuşuyorum? İlk önce ilk şeyleri koyalım. Önce bir aralık seçmeliyiz. Bu seçimi yapmak için birçok yaklaşım var. Bu konuda fazla detaya girmeyeceğiz. Dizimizi ikiye bölelim ve bir sayı alalım - bu bizim aralığımız olacak. Yani dizimizde 9 eleman varsa aralığımız 9/2 = 4,5 olacaktır. Kesirli kısmı atıyoruz ve 4 elde ediyoruz, çünkü dizi indeksleri sadece tamsayı olabilir. Bu aralığı gruplarımızı oluşturmak için kullanacağız. Bir elemanın indeksi 0 ise, grubundaki bir sonraki elemanın indeksi 0+4, yani 4'tür. Üçüncü elemanın indeksi 4+4, dördüncü - 8+4 vb. İkinci grupta birinci eleman 1,5,9 olacak... Üçüncü ve dördüncü grupta da durum aynı olacak. Sonuç olarak, {6,3,8,8,6,9,4,11,1} sayı dizisinden dört grup elde ederiz: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Genel dizideki yerlerini koruyorlar, ancak aynı grubun üyeleri olarak işaretledik: {6,3,8,8,6,9,4,11,1} Sonraki, ekleme sıralama bu gruplara uygulanır ve sonra şöyle görünürler: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Genel dizide, grupların işgal ettiği hücreler aynı kalacak, ancak yukarıdaki grupların sırasına göre iç sıraları değişecektir: {1,3,4,8,6,9,8,11,6} Dizi, biraz daha düzenli, değil mi? Bir sonraki aralık 2'ye bölünecek: 4/2 = 2 İki grubumuz var: I — {1,4,6,8,6} II — {3,8,9,11} Genel dizide, : {1,3,4,8,6,9,8,11,6} Ekleme sıralama algoritmasını her iki grupta da çalıştırıyoruz ve şu diziyi elde ediyoruz: {1,3,4,8,6,9,6, 11, 8} Şimdi dizimiz neredeyse sıralandı. Algoritmanın son bir yinelemesini gerçekleştirmemiz gerekiyor: aralığı 2: 2/2 = 1'e bölüyoruz. Tüm diziden oluşan bir grup elde ediyoruz: {1,3,4,8,6,9,6,11 ,8} Araya ekleme sıralama algoritmasını bunun üzerinde çalıştırarak şunu elde ederiz: {1,3,4,6,6,8,8,9,11} Bu sıralamayı Java kodunda nasıl hayata geçirebileceğimize bir göz atalım:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
Sonuçlar farklı durumlarda farklılık gösterdiğinden, şu anda Shellsort'un performansını karakterize etmek kolay değil. Deneysel tahminler O(N 3/2 ) ile O(N 7/6 ) arasında değişmektedir.
Hızlı sıralama
Bu, en popüler algoritmalardan biridir, bu nedenle özel dikkat göstermeye değer. Bu algoritmanın özü, bir elemanlar listesinden bir pivot elemanın seçilmesidir. Diğer tüm öğeleri pivot öğeye göre sıralarız. Pivot öğesinden küçük değerler soldadır. Ondan büyük değerler sağdadır. Daha sonra sağ ve sol kısımda pivot elemanları da seçilir ve aynı şey olur: değerler bu elemanlara göre sıralanır. Daha sonra yeni oluşturulan parçalarda pivot elemanlar seçilir ve sıralanmış bir dizi elde edene kadar bu böyle devam eder. Bu algoritmanın aşağıdaki Java uygulaması özyinelemeyi kullanır:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
Şüphesiz, hızlı sıralama algoritması en popüler olanıdır, çünkü çoğu durumda diğerlerinden daha hızlı çalışır. Zaman karmaşıklığı O(N*logN) şeklindedir.
Birleştirme sıralaması
Bu tür de popülerdir. "Böl ve fethet" ilkesine dayanan birçok algoritmadan biridir. Bu tür algoritmalar önce sorunu yönetilebilir parçalara ayırır (hızlı sıralama, böyle bir algoritmanın başka bir örneğidir). Peki bu algoritmanın özü nedir?
Bölmek:
Dizi, yaklaşık olarak aynı boyutta iki parçaya bölünür. Bu iki parçanın her biri ikiye bölünür ve mümkün olan en küçük bölünemez parça kalana kadar böyle devam eder. Her dizinin bir elemanı olduğunda, yani zaten sıralanmış bir dizi olduğunda, en küçük bölünemez parçalara sahibiz.
Fethetmek:
Algoritmaya adını veren işleme burada başlıyoruz: birleştirme. Bunu yapmak için, ortaya çıkan iki sıralanmış diziyi alıp bir dizide birleştiriyoruz. Bu durumda, iki dizinin ilk elemanlarından en küçüğü elde edilen diziye yazılır. Bu işlem, bu iki dizideki tüm elemanlar kopyalanana kadar tekrarlanır. Yani, iki minimum dizimiz {6} ve {4} varsa, bunların değerlerini karşılaştırır ve şu birleştirilmiş sonucu üretiriz: {4,6}. {4,6} ve {2,8} dizilerini sıraladıysak önce 4 ve 2 değerlerini karşılaştırırız sonra çıkan diziye 2 yazarız. Ondan sonra 4 ve 8 karşılaştırılacak ve 4 yazacağız. Son olarak 6 ve 8 karşılaştırılacak. Buna göre 6 yazacağız ve ancak ondan sonra 8 yazacağız. Sonuç olarak aşağıdaki birleştirilmiş diziyi elde ederiz: {2,4,6,8}. Bu Java kodunda nasıl görünecek? Bu algoritmayı çalıştırmak için özyinelemeyi kullanmak bizim için uygun olacaktır:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
Hızlı sıralamada olduğu gibi, özyinelemeli yöntemi bir ara yönteme taşırız, böylece kullanıcının yalnızca sıralanacak diziyi sağlaması gerekir ve herhangi bir ek varsayılan bağımsız değişken sağlama konusunda endişelenmesine gerek kalmaz. Bu algoritmanın hızlı sıralama ile benzerlikleri vardır ve şaşırtıcı bir şekilde yürütme hızı aynıdır: O(N*logN).
2. Açgözlü algoritmalar
Açgözlü bir algoritma, nihai çözümün de optimal olacağı varsayımıyla her aşamada yerel olarak optimal kararların verildiği bir yaklaşımdır. "Optimal" çözüm, herhangi bir belirli adımda/aşamada en bariz ve acil faydayı sunan çözüm olacaktır. Bu algoritmayı keşfetmek için oldukça yaygın bir sorunu ele alalım: sırt çantası sorunu. Bir an için hırsız olduğunuzu farz edin. Bir sırt çantası (sırt çantası) ile gece bir mağazaya girdiniz. Önünüzde çalabileceğiniz birkaç mal var. Ancak aynı zamanda sırt çantanızın kapasitesi de sınırlıdır. 30 birimden fazla ağırlık taşıyamaz. Ayrıca sırt çantasına sığacak en değerli eşya setini de taşımak istiyorsunuz. Çantanıza ne koyacağınıza nasıl karar veriyorsunuz? Bu yüzden,
Henüz alınmamış en pahalı öğeyi seçin.
Sırt çantasına sığıyorsa koy, sığmıyorsa bırak.
Zaten her şeyi çaldık mı? Değilse, 1. adıma geri döneriz. Evet ise, yapmaya geldiğimiz şeyi başardığımız için mağazadan hızlı bir şekilde kaçarız.
Buna bir bakalım, ama Java'da. Item sınıfı şu şekilde görünecektir:
public class Item implements Comparable {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
Burada özel bir şey yok: öğenin özelliklerini tanımlayan üç alan (ad, ağırlık, değer). Ayrıca, görebileceğiniz gibi, Öğelerimizi fiyata göre sıralamamıza izin vermek için Karşılaştırılabilir arayüz uygulanmıştır. Ardından, sırt çantamızı temsil eden Bag sınıfına bakacağız:
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
maxWeight , bir nesne oluşturduğumuzda ayarlanan sırt çantamızın kapasitesidir;
öğeler, sırt çantamızdaki nesneleri temsil eder;
currentWeight , currentValue — bu alanlar, addItem yöntemine yeni bir öğe eklediğimizde artırdığımız sırt çantasındaki tüm öğelerin geçerli ağırlığını ve değerini saklar.
Her neyse şimdi tüm aksiyonun gerçekleştiği sınıfa geçelim:
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
İlk olarak, bir öğe listesi oluşturur ve sıralarız. 30 birim kapasiteli bir çanta nesnesi oluşturuyoruz. Ardından, öğeleri ve çanta nesnesini, açgözlü algoritmamıza göre sırt çantasını dolduran fillBackpack yöntemine aktarıyoruz:
Oldukça basit: Maliyete göre sıralanmış bir ürün listesini gözden geçirmeye ve kapasitesi izin veriyorsa bunları çantaya koymaya başlıyoruz. Yeterli yer yoksa öğe atlanacak ve listenin sonuna ulaşana kadar diğer öğeler arasında gezinmeye devam edeceğiz. Main'i çalıştırdığımızda, alacağımız konsol çıktısı şöyle:
Sırt çantasının ağırlığı 29'dur. Sırt çantasındaki eşyaların toplam değeri 3700'dür.
Bu açgözlü bir algoritma örneğidir: her adımda yerel olarak en uygun çözüm seçilir ve sonunda küresel olarak en uygun çözümü elde edersiniz. Bizim durumumuzda, en iyi seçenek en pahalı öğedir. Ama bu en iyi çözüm mü? Sırt çantamızı toplam değeri daha da fazla olan eşyalarla doldurmak için çözümümüzü biraz iyileştirmenin mümkün olduğunu düşünmüyor musunuz? Bunun nasıl yapılabileceğine bir göz atalım.
public static void effectiveFillBackpack(Bag bag, List items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
Burada önce her bir öğe için değer-ağırlık oranını hesaplıyoruz. Bu bize belirli bir öğenin her bir biriminin değerini söyler. Daha sonra bu oranları kullanarak eşyalarımızı sıralayıp çantamıza ekliyoruz. Aşağıdakileri çalıştıralım:
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
Bu konsol çıktısını alıyoruz:
Sırt çantasının ağırlığı 29'dur. Sırt çantasındaki eşyaların toplam maliyeti 4150'dir.
Biraz daha iyi, değil mi? Açgözlü algoritma, nihai çözümün de optimal olacağını umarak her adımda yerel olarak optimal bir seçim yapar. Bu varsayım her zaman geçerli değildir, ancak birçok görev için açgözlü algoritmalar optimum bir nihai çözüm sağlar. Bu algoritmanın zaman karmaşıklığı O(N)'dir. Oldukça iyi, ha?
Ve bu web sitesinde olduğunuza göre, Java ile yazdığınızı varsayacak kadar cesur olacağım. Bu nedenle bugün, bazı temel algoritmaları ve bunların Java'da nasıl uygulanacağına dair belirli örnekleri öğrenmenizi öneriyorum. "Bazı" derken şunu kastediyorum:
GO TO FULL VERSION