StackOverflow khi gọi đệ quy trong quick Sort

[canhquanhoanggia]

chắc mọi người đã quá quen thuộc với QuickSort. Nhưng cho mình hỏi QuickSort của mình sau đây lại bị lỗi StackOverFlow ạ? Cảm ơn vì đã đọc[IMG]images/smilies/biggrin.png[/IMG]

import java.util.Scanner;

/**
 * mr.Kurro
 * 14020665
 * bai tap 5
 */
public class quickSort{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.println("so phan tu can sap xep: ");
        int N = in.nextInt();
        int[] A = new int[N];
        for(int i = 0; i < N; i++){
            System.out.print("Nhap phan tu can sap xep: ");
            A[i] = in.nextInt();
        }
        sort(A, 0, N - 1);
        for(int i = 0; i < N; i++){
            System.out.println(A[i]);
        }
    }

    static int partition(int[] a, int left, int right) {
        int i = left;
        int j = right;
        int pivot = a[(left + right) / 2];
        while (i <= j) {
            while (a[i] < pivot)
                i++;
            while (a[j] > pivot)
                j--;
            if (j <= j) {
                // hoan doi vi tri hai so
                a[i] += a[j];
                a[j] = a[i] - a[j];
                a[i] = a[i] - a[j];
                i++;
                j--;
            }
        }
        return i;
    }
    static void sort(int[] a, int left, int right){
        int p = partition(a, left, right);
        if(left < p){
            sort(a, left, p);
        }
        if(right > p){
            sort(a, p, right );
        }
    }
}

View more random threads:

• eclipse báo lỗi. button.addActionListener(this)
• Từ điển Java
• [Help] Các bạn giúp mình sửa lỗi giúp mình
• Vấn đề sử dụng PreparedStatement
• Học Java có cần phải học C/C++???
• lỗi Exception in thread "main" java.lang.NullPointerException
• ý nghĩa đoạn code
• Giúp mình bài java này với !!!
• Chỉnh sửa các dòng trong file txt
• giúp về dừng thread để thực hiện 1 công việc sau đó chạy tiếp thread đó

[longcheng]

Có 1 lỗi typo:

if (j <= j) {

Còn thuật toán thì chưa biết được.

[thailee]

Thuật toán sai nhé. Nếu muốn kiểm tra xem có mảng phần tử chưa sắp xếp bên trái hay không thì phải so sánh left với j chứ không phải với i. Điều kiện left < i là luôn đúng nên hàm sort được gọi nhiều lần, dẫn đến tình trạng tràn stack.
Mình thì sửa bài của bạn như thế này.

	static void sort(int[] a, int left, int right) {
		int temp;
		int i = left;
		int j = right;
		int pivot = a[(left + right) / 2];
		while (i <= j) {
			while (a[i] < pivot)
				i++;
			while (a[j] > pivot)
				j--;
			if (j <= j) {
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				i++;
				j--;
			}
		}
		if(left<j)
			sort(a, left, j);
		if(i<right)
			sort(a, i, right);
	}

[dudung94]

Mình dùng đệ quy bên C# cũng gặp StackOverFlow. Chia sẻ với bạn thế này hy vọng đúng :

Với những phép đệ quy nhỏ thì nguy cơ gây tràn stack là ít nhưng với những phép đệ quy lớn thì rất dễ gây ra tràn stack.

Đệ quy người ta không ưu tiên dùng (đây là mình đọc đâu đó ). Khi gọi đệ quy thì giống như việc bạn gọi rất nhiều hàm nhưng hàm đó không kết thúc. Khi gọi hàm thì nó sẽ lưu các thông tin cần thiết trước khi gọi hàm vào stack, khi hàm thực hiện xong nó sẽ lấy các thông tin trước khi gọi hàm trên stack để khôi phục công việc. Sau đó các thông tin đã lưu trên stack sẽ bị xóa đi. Nếu các hàm được gọi rất nhiều nhưng không kết thúc thì sẽ tràn stack.