30/09/2018, 17:16
Vector iterator not dereferencable
Em đang thử implement quicksort trên 1 vector struct word (word gồm có string và int) thì sau khi chạy nó bị lỗi Vector iterator not dereferencable, có anh chị nào có thể sửa giúp em được ko ạ em vẫn còn newbie với vector
int partition(vector<word> &database, int start, int end) //partition the vector
{
word pivot = database[end];
int pIndex = start;
for (int i = pIndex; i < end; i++)
{
if (database[i].freq > pivot.freq)
{
iter_swap(database.begin() + pIndex, database.begin() + i);
pIndex++;
}
}
iter_swap(database.begin() + pIndex, database.end());
return pIndex;
}
void quickSort(vector<word> &database, int start, int end)
{
if (start < end)
{
int partitionIndex = partition(database, start, end);
quickSort(database, start, partitionIndex - 1);
quickSort(database, partitionIndex + 1, end);
}
}
Bài liên quan
Thuật toán bị sai:
vectorpartitionlà trở thànhrandom_quickSortnó sẽ chạy nhanh hơn trong trường hợp dãy đã dc sắp xếp.em cảm ơn anh gió
cơ mà anh giải thích cho em tại sao chọn pivot như vậy nó nhanh hơn ko ạ, em xem trên mạng là ngta bảo hay chọn ở cuối
p/s: ->
anh @gio cho em hỏi thêm 1 cái nữa em test cái thuật toán trên 1 vector 100 phần tử thì ok rồi mà em làm trên quy mô lớn hơn là 10 file texts, mỗi file text có khoảng hơn 400 từ thì nó bị báo lỗi stackoverflow, có phải là do biến cục bộ nhiều quá không ạ
Mỗi từ bao nhiêu kí tự?. Nếu khoảng 100 kí tự * 10 * 400 = 400000 byte thì ko overflow dc
Dùng vector thì nó tự động tăng kích thước khi cần nên biến cục bộ cũng k sao
dạ dữ liệu là tiếng anh nên 1 từ ko quá 20 kí tự
anh @Gio cho em hỏi thêm tí nha em test cái quicksort với 170 file text thì ok (chạy hơi lâu), mỗi file text cỡ 500 từ, mà em sort cỡ 180 file thì nó bị crash lúc đang chạy, debug thì nó bảo stackoverflow, có phải do biến cục bộ nhiều quá không ahnh? em có nên chuyển qua dùng mergesort ko
Dùng merge sort cần thêm bộ nhớ phụ nên càng dễ overflow. Vì bài trên chỉ cần sắp theo freq nên class chỉ lưu freq và chỉ số của chuỗi o trong mảng khác để sắp. Tránh copy chuỗi nhiều lần trong swap
à em hiểu ý anh rồi, cảm ơn anh