Java Quicksort neden/nerede değerler değişiyor?

Question

Şu anda okulda Java öğreniyorum ve en son konu Java'daki sıralama algoritmalarıdır. Anlamaya çalıştığım şey hızlı bağlantı.

Bu algoritmanın bir dizide sayıları nasıl sıraladığını anlamak için, Eclipse hata ayıklayıcı penceresinde adım adım kodumdan devam etmeye karar verdim.

Şimdi, yüzlerce kez hissettiklerimden geçtikten sonra bile kavrayamadığım bir adım vardı. Ben 10 ve 2 ardından 5 ve 3 ve sonra 2 ve 2 değiştirerek program başlamadan koduyla gittiğinizde

Benim ilk dizi [10, 5, 3, 22, 11, 2]

olduğunu. Bu noktada i değeri 1 ve j değeri -1'dur.

Şimdi öyle anlıyorum üç koşul

false döndürür

1. while(i<=j) olmasıdır i = 1 ve false döndürür

2. if(left < j)j = -1, çünkü left = 0 çünkü j = -1

3. if(i < right) Ayrıca hangi Program ama aniden değerlerini satır programın geri atlar sağ public static void display önceki son dilimine aldığında i = 1 çünkü right = 1

Ama benim için sürpriz, i, falsej ve pivot döndürür sırasıyla 5, 2, -1 ve 3 olarak değiştirilmiştir.

çok çok değerli olabilir, birisi değerlerin neden değiştiğini açıklayabilirse.

Ben de benim Eclipse penceresinde step I don't understand

public class QSort { 

    public static void quickSort(int[] arr, int left, int right){ 
     int i = left; 
     int j = right; 
     int temp; 
     int pivot = arr[(left+right)/2]; 
     System.out.println("\n\nleft = " + left + "\tright = " + right); 
     System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")"); 
     while(i <= j){ 
      while(arr[i] < pivot){ 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
       i++; 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
      } 
      while(arr[j] > pivot){ 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
       j--; 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
      } 
      if(i <= j){ 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
       System.out.println("Swapped " + arr[i] + "(" + i + ")"+ " with " + arr[j] + "(" + j + ")"); 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 
       i++; 
       j--; 
       System.out.println("i is: (" + i + ")"); 
       System.out.println("j is: (" + j + ")"); 
       System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")"); 
      } 
     } 
     if(left < j){ 
      System.out.println("j is: (" + j + ")"); 
      quickSort(arr, left, j); 
     } 
     if(i < right){ 
      System.out.println("i is: (" + i + ")"); 
      quickSort(arr, i, right); 
     } 
    } 

    public static void display(int[] arr){ 
     if(arr.length > 0){ 
      System.out.print(arr[0]); 
     } 
     for(int i = 1; i < arr.length; i++){ 
      System.out.print(", " + arr[i]); 
     } 
    } 

    public static void main(String[] args) { 
     int[] data = new int[]{10,5,3,22,11,2}; 
     System.out.println("Before: "); 
     display(data); 
     quickSort(data, 0, data.length-1); 
     System.out.println("\nAfter: "); 
     display(data); 
    } 
} 

Çok teşekkürler gördükleri göstermek iki resim eklemiş!

Answer 1

Bence senin sorunun, özyineyi tam olarak anlamadığın. En azından sorunun tarifinden hoşlandığı şey bu. Her durumda, tüm değişkenleri izleyerek programınızı izlemeyi denedim. Umut bu yardımcı olur: i<=j şimdi false (2 > 1) olduğu için

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[10,5,3,22,11,2] 0   5   
              0   5  arr[2] = 3 
[2,5,3,22,11,10]       1   4 
                3 
                2 
[2,3,5,22,11,10]       2   1 

while döngüsü tamamladı.

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[2,3,5,22,11,10] 0   1 
              0   1  arr[0] = 2 
                0 
[2,3,5,22,11,10]       1   -1 

süre: - yani bunu şimdi hiçbir şey olmaz, zaten sıralanmış diziyi [2,3] sıralamak quicksort(arr, 0, 1): Tekrar yinelemeli quicksort diyoruz böylece

ilk şart left < j (0 < 1), true olduğunu döngü koşulu şimdi false. left < j ilk koşulu da false olup (0 > -1) ve ikinci koşul i < right da yanlıştır (çünkü 1 == 1) Bu çağrı bitti ve bulunduğunuz yere döndünüz. O muydu? Yukarıdaki tablonun ilk koşulu. değişkenler ve parametreler devlet artık geçerli: (çalıştırıldıktan sonraki çizgidir olarak)

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[10,5,3,22,11,2] 0   5   2   1  3 

ikinci koşul kontrol edilir. Durumu i < right (2 < 5) olduğu için değeri de doğrudur. Yani şimdi tekrar yinelemeli quicksort yapın: quicksort(arr, 2, 5) - Şimdi dizi [3,22,11,10] sıralamak demektir: artık bu yüzden while döngüsü çıkmak

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[2,3,5,22,11,10]   2   5   
              2   5  arr[3] = 22 
              3 
[2,3,5,10,11,22]       4   4 
              5 

i > j.

ilk şart left < j (2 < 4) true, bu yüzden zaten sıralanır [5,10,11] sıralamak amacıyla quicksort(arr, 2, 4) diyoruz. Diziyi hiç değiştirmediğinden bu kısmı atlayacağım.

Yinelemeli arama tamamlandığında, bulunduğumuz yere dönüyoruz ve şimdi ikinci koşul kontrol edilecektir. i < right (5 < 5) false ve bu yüzden bitti.

Orijinal quicksort araması bitti ve dizi sıralandı.

Answer 2

Bulunduğunuz ilk resim, hata ayıklayıcısını iki kez yinelemeli hızlı çağrıya dahil olduğunu gösterir: Quicksort ana bilgisayardan çağrılır ve daha sonra 38 numaralı satırda tekrar quicksort çağrısı yapılır (bu, quicksort ilkesidir, bu yineleme stratejisidir). Yani, iç aramanın 40. satırında olduğunu görüyorsunuz, o zaman oradan adım attığınız zaman, bir önceki quicksort çağırma sürecine geri dönersiniz (hata ayıklayıcı size sol üst pencerede üç yerine iki satırlık bir yığın gösterir), ve pivot'un önceki değerlerine geri döndüğünüzde, dizi paylaşıldığı için tüm özyinelemeli çağrılar için geçirilir, ancak tamsayı değişkenleri değildir.

Burada, anlaşılmasını zorlaştıran özyineleme olduğunu düşünüyorum, çağrı yığınınızı kontrol edin.

Answer 3

Baskı ifadeleri ve bir hata ayıklayıcısını kullanarak sıralama algoritmalarını çalışmak için harcadığınız çabaya değer! Fakat şu anki Quicksort uygulamanızın en azından başlangıçta anlaşılması oldukça zordur, çünkü hem yineleme hem de yineleme devam ediyor (yani döngüleri kullanıyorsunuz ve aynı zamanda quicksort kendiniz çağırıyorsunuz).

Quicksort'un nasıl çalıştığını ve neden çalıştığını görmek için oldukça farklı bir yaklaşım (tamamen özyinelemeli yaklaşım) uygulayalım. Bu özyinelemeli prosedürü yinelemeli bir şeye dönüştürmek (bir şekilde yazmış gibi), neyse ki, bir teknik meselesidir (bu durumda)! Bunu burada yaptığımızı öneriyorum çünkü bu şekilde karmaşıklığı daha iyi kontrol edebiliyoruz. Yine, bunu yapmamın nedeni'da olup bitenleri daha iyi anlamaktır.o

public static void qsort(int[] ints, int fi, int li) {       
    /* the recursive procedure */             
    if (fi < li) {                 
     int p = partition(ints, fi, li); // key routine -- see below           
     qsort(ints, fi, p - 1);              
     qsort(ints, p + 1, li);              
    }                    
    } 

var: Sir Tony Hoare algoritması önerilmiştir ve doğru olup olmadığını kanıtlamıştır

, böyle bir şeydi! Güzel değil mi Eh, öyle. Tek yapmanız geçerli:

• Bölme verilen dizi. Gözlerimde, bölümleme zor bir sorunu iyi çözmek için zarif bir prosedürdür. Sorun basit: Bir sayı dizisi verildiğinde dizisini dizgesini yeniden düzenleyin, böylece içinde bir sayı var, soldaki tüm sayılar daha küçük veya ona eşit ve sağdaki tüm sayılar daha büyük. buna eşit veya ona eşit - dizide böyle bir elemanın indeksini döndür. Bu sorunu kendi başınıza çözmeye çalışmanızı tavsiye ediyorum. Vikipedi'de verilen prosedürler (Lomuto ve Hoare) iyi çalışır.
• beklendiği gibi bölümleme çalıştığından emin olduğunuzda, yinelemeli sıralama aynı qsort prosedürü kullanarak iki bölüm (özyinelemeli aramaların sırası yapar değil madde) ve yapılır!

  /** 
      Implements partitioning of array a from a[p] to a[r], leaves all the other elements of the array intact. 
      @param a the given int array 
      @param p int first index of the part of array to be partitioned 
      @param r int the second index of the part of array to be partitioned 
  */ 
      public static int partition(int[] a, int p, int r) { 
      //this is something I have written 
      int pivot = a[p]; 
      int i = p + 1; 
      int j = i - 1; 
      while (i <= r) { 
       if (a[i] < pivot) { 
       a[j] = a[i]; 
       a[i] = a[j+1]; 
       j++; 
       } 
       i++; 
      } 
      a[j] = pivot; 
      return j; 
      } 
  
      private static void swap(int[] ints, int i1, int i2) { 
      int tmp = ints[i2]; 
      ints[i2] = ints[i1]; 
      ints[i1] = tmp; 
      } 
  

  Şimdi, henüz bu prosedürün doğruluğunu ispat değil, ama biz ayrı olarak yapabilirsiniz:

Ben partition yordamı kendim uygulamaya çalışmıştır. Hatta Lomuto procedure'u yeniden canlandırabilir ve bunun sizin memnuniyetinize uygun olduğunu görebilirsiniz.

Ve işte bu kadar. Bunu şimdi bir hata ayıklayıcısında hata ayıklamak istiyorsanız, bunu yapmak için daha donanımlısınız. İşte entire implementation.

Şimdi, yinelenen bir birine bu özyinelemeli prosedürü dönüştürme soru çok ilginç ve bu belgesidir: (utanmaz fişi: ben yazdım) http://bit.ly/recurse-iterate size bazı ipuçları vermelidir. Yukarıdaki Quicksort prosedürünün yinelemeli olarak dönüştürülmesi, okuyucuya bir egzersiz olarak bırakılır.