Dizileri sıralamak, Java'ya yeni başlayan birinin nasıl yapılacağını bilmesi gereken en yaygın işlemlerden biridir. Diziler her zaman verileri düzenlemenin en uygun yolu olmasa ve bu çoğunlukla küçük sayılar için geçerli olsa da, dizi sıralamanın ardındaki kavram, karmaşık yazılım ve veri biliminde tonlarca uygulamaya sahiptir. Bu yazıda, ekleme sıralamasının ne olduğuna daha yakından bakacağız. Bu konsepti tamamen anlamanıza yardımcı olmak için bazı örnekler ve uygulama problemleri ekledik.
Ekleme Sıralaması Nedir?
Temel olarak, eklemeli sıralama, geliştiricilerin küçük sayı dizilerini düzenlemek için kullandıkları bir algoritmadır. Tüm değerleri iki yığına ayırır - sıralanmış ve sıralanmamış. "Sıralanmamış" yığındaki sayılar birer birer seçilir ve doğru sıraya konur. Ekleme sıralamasının girdisine ve çıktısına daha yakından bakalım:
Girdi: sıralanmamış sayısal öğeler içeren bir A dizisi: A[0,1, n, n-2...].
Çıktı: aynı sayıları içeren ancak tamamen sıralanmış bir dizi. Bu, tipik olarak B: B[0]B[1]...B[n-1] olarak adlandırılır.
Araya girerek sıralamayı kullanmanın birkaç yolu vardır - işte en popüler olanları:
Sayısal sıralama (artan düzen): [1, 2, 3, 4, 5]
Sayısal sıralama (azalan düzen): [5, 4, 3, 2, 1]
Alfabetik sıralama: [a, b, c, d]
Not: Boş bir diziniz veya bir tekil öğeniz varsa, bunlar varsayılan olarak sıralanmış kabul edilir.
Ekleme Sıralaması Teorisini Anlamak
Ekleme sıralamanın arkasındaki kodu keşfetmeden önce, teknik olmayan bir dil kullanarak algoritmayı parçalayalım. Sıralama kodunu artan düzende göstereceğimiz için, bu yazıda algoritmayı adım adım açıklamak mantıklı olacaktır. Adım 1. Sayısal bir değerin genellikle 10'dan küçük olduğu arr[1]ve arr[n]arasında yineleme . Adım 2. Seçtiğiniz öğeyi ( olarak bilinir ) yöntemi kullanarak dizideki önceki sayıyla karşılaştırın . Adım 3. Tüm öğeler ardıllarından daha küçükse, daha büyük bir değer bulana kadar karşılaştırmayı tekrarlayın. Adım 4. Sıralı bir dizi oluşturmak için daha büyük bir değeri küçük değerin bir konumu ile değiştirin. nkeysort()Adım 5. Sıralanmış bir karakter dizisi elde edene kadar işlemi tekrarlayın.
İlkel dizileri sıralama
Algoritma en basit Java işlemlerinden biri olduğu için, tamamen yeni başlayanlar bile onu uygulamakta çok fazla sorun yaşamamalıdır. İşte bir diziyi sıralamak için adım adım bir kılavuz
1. Sıralama için bir dizi bildirin
Başlamak için, daha sonra Java kullanarak göstereceğimiz bir değerler dizisi oluşturalım. Ekleme sıralamasını kullanmak için bir dizi oluşturmanız gerekir. Bunun için kullanınint[]
int[] arrayA = {10, 14, 20, 30};
2. Algoritmayı uygulamak için sort_arr kullanın
sort_arr yöntemi, eklemeli sıralamayı uygulamanın en yaygın yollarından biridir. Pratikte şöyle görünür:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Bir döngü ve yineleyici oluşturun
Ekleme sıralama algoritmasında bir döngü kullanarak, geliştiricilerin mantığı her öğe için tekrar etmesi gerekmez. Döngüler oluşturmak karmaşık görünse de oldukça basittir - işte bir örnek:
for(int i=0; i< sort_arr.length; ++i){
Artık çalışan bir döngünüz olduğuna göre, tüm öğeleri istenen sırada sıralayacak bir yineleyici oluşturma zamanı. Bundan sonra iteratöre " " olarak atıfta bulunacağız j.
int j = i;
4. Bir "while döngüsü" oluşturma
Eklemeli sıralama söz konusu olduğunda, yeni, sıralanmış bir dizi için bir "while" döngüsü gereklidir. Bunu artan sıralı ekleme sıralaması için ayarlamak üzere bir geliştiricinin iki koşula uyması gerekir:
j'ye atanan değer 0'dan büyük olmalıdır
Atanan değerin j-1dizinden büyük olması gerekirj
While döngüsündeki her iki koşul da doğru olur olmaz, dizinin anahtar değeri dizine eşit olacaktır j.
5. Diziyi sıralama
While döngüsünü kurduktan sonra, while döngüsündeki koşullardan biri veya her ikisi de başarısız olana kadar jve değerleri değiştirilir. j-1Benzer şekilde sıralama, for döngüsü koşulları da başarısız olana kadar for döngüsündeki her değer için tekrarlanacaktır. Araya ekleme sıralama işlemi pratikte şu şekilde çalışır:
Eklemeli sıralamanın arkasındaki matematiği anlamak önemli olsa da, gerçek hayattaki yazılım geliştirme söz konusu olduğunda, ArrayList'leri ilkel dizilerdeki dizilerden çok daha fazla sıralayacaksınız. İşte bir ArrayList'i sıralamak için adım adım bir kılavuz:
ElementKoleksiyona ait öğeler için yeni bir sınıf oluşturun .
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
Bir koleksiyon içinde bir yöntem vardır compareTo()- bunu iki öğenin kimliklerini karşılaştırmak için kullanacağız.
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Algoritmayı uygulayın ve nesneleri ArrayListkarşılaştırmak yerine sıralamak için bazı döngüler oluşturun.
public static void insertionSortArrayList(List<element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
ArrayListAşağıda gösterildiği gibi daha fazla öğe de ekleyebilirsiniz :
List<element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// To use insertion sort, shuffle the values
Collections.shuffle(list);
Şimdi sıralama zamanı:
// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Display a sorted array
list.forEach(e -> System.out.print(e.getId() + ", "));
Şimdi hata yapmadığımızdan emin olmak için girdi ve çıktıyı karşılaştıralım. İşte örnek olarak kullandığımız dizenin karşılaştırması.
Artık bu sıralama algoritmasına hakim olduğunuza göre, teorik ve pratik becerilerinizi test etme zamanı. Teori sınavı #1 Size bir [1, 4, 6, 8] dizisi veriliyor ve ona yeni bir n = 7 elemanı ekliyorsunuz. Sıralanmış bir sayı dizisi elde etmek için kaç karşılaştırma yapmanız gerekecek? Dizideki n indeksinin son değerini belirtin. Teori sınavı #2 Bir iş görüşmesinde, bir ekip lideri sizden sıralama eklemenin verimsiz bir yöntem olduğunu kanıtlamanızı ister. [0, 3, 6, 8, 9] şeklinde bir sayı dizisi verildiğinde, sıralama için gereken çalışma süresini en üst düzeye çıkarmak için giriş sıranızın sırası ne olmalıdır? Alıştırma problemi Java için ekleme sıralamasını kullanarak [0, 1, 4, 5, 2, 3, 7, 9, 8] dizisini artan düzende sıralayın.
Çözüm
Ekleme sıralamasını kavramadaki en büyük zorluk, sürecin nasıl çalıştığını anlamaktır. Bir kez alıştıktan sonra, şablonu koda dönüştürmek çocuk oyuncağıdır. Alıştırma yaptığınız ve ilgili alıştırma problemlerini zaman içinde tekrar gözden geçirdiğiniz sürece, eklemeli sıralama hızınızı hızla artıracaksınız.
Ekleme sıralamasının girdisine ve çıktısına daha yakından bakalım:
GO TO FULL VERSION