Vector iterator not dereferencable

#1

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 ạ :smiley: 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);
	}
}
#2

Thuật toán bị sai:

  • Lỗi là do bạn truy cập quá kích thước của vector :smiley:
  • Chỉ cần thêm 2 dòng vào đầu hàm partition là trở thành random_quickSort nó sẽ chạy nhanh hơn trong trường hợp dãy đã dc sắp xếp.
    int pivotIndex=start+rand()%(end-start+1);
    iter_swap(database.begin()+pivotIndex,database.begin()+end);
2 Likes
#3

em cảm ơn anh gió :older_man:

1 Like
#4

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

#5

:ok_hand: :baby: :baby: :baby: :baby:
p/s: :older_man: -> :boy:

  • Cái này thì phải nghiên cứu xác suất mới dc. Nói chung khi dãy đã dc sắp xếp thì cách chọn pivot ở đầu và cuối sẽ bị lệch về 1 bên nên thời gian chạy là O(n2). Còn random là O(nlogn)
1 Like
#6

anh @gio cho em hỏi thêm 1 cái nữa :smiley: 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 ạ

#7

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

#8

dạ dữ liệu là tiếng anh nên 1 từ ko quá 20 kí tự

#9

anh @Gio cho em hỏi thêm tí nha :smile: 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

#10

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

1 Like
#11

à em hiểu ý anh rồi, cảm ơn anh

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?