Giúp đỡ về QuickSort trong Java

#1

Mình có tham khảo một clip và bài trên mạng về QuickSort giờ thực hành thì nó chả chạy được ngồi một lúc cũng không biết lỗi nên mong ae gíup mình.

    public class QuickSort {
    public static int arrayInt [] ={2,23,12,20,10,15,20};
    public void output(){
        for(int i: arrayInt){
            System.out.print(i+" ");
        }
    }
    public void Quicksort(int left,int right){
        int x = arrayInt[(left+right)/2];//Gán mốc là giá trị ở giữa mãng
        int i = left, j = right;//Gán giá trị i chạy từ trái qua phải và j ngược lại
        do{
            while((i<=j)&&(x>=arrayInt[i])){
              i++;  
            }
            while((i<=j)&&(x<=arrayInt[j])){
                j--;
            }
            if(i<j){
                int temp = arrayInt[i];
                arrayInt[i] = arrayInt[j];
                arrayInt[j] = temp;
                i++;
                j--;
            }
        }while(i<=j);
        if(left<j){
            Quicksort(left, j);
        }
        if(i<right){
            Quicksort(i, right);
        }
    }
    public static void main(String[] agrs){
        QuickSort met = new QuickSort();
        System.out.println("Value before the sort");
        met.output();
        met.Quicksort(0, arrayInt.length -1);
        System.out.println("Value after the sort");
        met.output();
    }
}

Nó được như sau:

Value before the sort
2 23 12 20 10 15 20
1 Like
#2

Cái này nếu a[i] hoặc a[j] ==x thì không biết sắp về bên nào? mình nghĩ dk là:

while((i<=j)&&(x>arrayInt[i])){
              i++;  
            }
            while((i<=j)&&(x<arrayInt[j])){
                j--;
            }

nếu i==j thì i++,j-- nữa nên dk đây là if(i<=j)

#3

Ý bạn điều kiện khúc này hả:

if(i<j){
                int temp = arrayInt[i];
                arrayInt[i] = arrayInt[j];
                arrayInt[j] = temp;
                i++;
                j--;
            }

Nếu mình đổi điều kiện i<=j thì khi i==j nó sẽ tự đổi chổ chính nó. Cho nên củng như không :smiley: .

#4

À ý nói là nếu i==j thì i++,j-- nên phải viết thêm vào 1 if nữa. nên nếu không muốn viết thêm thì thêm vào dấu = đó :smiley:

#5

Mơ hồ qúa bạn :sweat:, sữa code lại vứt mình tham khỏa với! Với lai sao vắng thế nhỉ? Hix :sob:

#6 
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
class QuickSort{
  public static int arrayInt [] ={2,23,12,20,10,15,20};
    public void output(){
        for(int i: arrayInt){
            System.out.print(i+" ");
        }
        System.out.println();
    }
    public void Quicksort(int left,int right){
    
        int x = arrayInt[(left+right)/2];//Gán mốc là giá trị ở giữa mãng
        int i = left, j = right;//Gán giá trị i chạy từ trái qua phải và j ngược lại
        do{
            while((i<=j)&&(x>arrayInt[i])){
              i++;  
            }
            while((i<=j)&&(x<arrayInt[j])){
                j--;
            }
            if(i<=j){
                int temp = arrayInt[i];
                arrayInt[i] = arrayInt[j];
                arrayInt[j] = temp;
                i++;
                j--;
            }
        }while(i<j);
        //System.out.printf("%d %d %d %d\n",left,j,i,right);
        //output();
        if(left<j){
            Quicksort(left, j);
        }
        if(i<right){
            Quicksort(i, right);
        }
    }
    public static void main(String[] agrs){
        QuickSort met = new QuickSort();
        System.out.println("Value before the sort");
        met.output();
        met.Quicksort(0, arrayInt.length -1);
        System.out.println("Value after the sort");
        met.output();
    }
}
1 Like
#7

Nếu như đổi điều kiện i<=j thì nó sẽ đổi chổ chính nó đó bạn, thực sự thêm vào = là thừa.

#8

thì thực ra là thêm 1 câu if nữa:

if (i==j) i++,j--;

Nhưng viết gộp vào cho nó đơn giản thôi. 2 câu trên khác nhau bởi i==j của bạn không thay đổi i,j

#9

Nếu như i==j của mình thì nó sẽ thây đổi ở phiên sau bạn ạ! Ví dụ: array[i]=array[j]=5 so sánh nó với mốc x=10 thì nó không thể vừa lớn hơn vừa nhỏ hơn được nên sẽ có i++ hoặc j-- ở đây.

while((i<=j)&&(x>arrayInt[i])){
              i++;  
            }
while((i<=j)&&(x<arrayInt[j])){
                j--;
            }
#10

Nếu i==j ở bước đó thì nó đã thoát ra câu lệnh do .. while mất rồi. nên Qsort sẽ bị lặp vô hạn do có 1 phần tử chung

#11

Tại sao lại thoát câu lệnh do…while nhỉ? nó sẽ lặp 1 lần nữa rồi mới thoát chứ?

#12

Không biết nên nói về code nào nữa. Nếu mà code của bạn mình cũng không biết nên thay đổi kiểu gì :smiley:

#13

Cảm ơn bạn ha :smiley: , thôi chắc gác lại học tiếp rồi hồi xem lại.

#14

Mình sữa lại chỗ này: while(i>=j) thành while(i<=j).

do{
            while((i<=j)&&(x>=arrayInt[i])){
              i++;  
            }
            while((i<=j)&&(x<=arrayInt[j])){
                j--;
            }
            if(i<j){
                int temp = arrayInt[i];
                arrayInt[i] = arrayInt[j];
                arrayInt[j] = temp;
                i++;
                j--;
            }
        }while(i<=j);
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?