01/10/2018, 13:37
Thắc mắc Selection Sort?
cách viết sort như thế này thì sai ở đâu nhỉ?
void selectionSort(int Arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = Arr[i];
for (int j = i + 1; j < n; j++) {
if (min > Arr[j]) {
min = Arr[j];
}
}
swap(min, Arr[i]);
}
}
Bài liên quan
Ngay sau đó
minbị ghi đè nên câu lệnh không khácArr[i] = min;, điều này vi pham một ràng buộc tối quan trọng của các thuật toán sắp xếp: output phải là hoán vị không giảm của input với thứ tự <= toàn phần cho trước, và riêng với thuật toán này thì một bất biến đã bị vi phạm: sau mỗi vòng, thành phẩm phải là hoán vị của đầu vào.Mấy cái code sort O(n^2) thì cứ lên google rồi copypasta cho nhanh, tự viết làm gì mất công suy nghĩ
Đến thế thì std::sort cho rồi đang học mà.
Các hàm sort thường không dùng
swap(min, A[i])mà thường làswap(&A[j], &A[i])hay đại loại thế.có link chi tiết không ban?
Mình thấy cái này cũng đúng mà selection sort thì nó lưu vị trí còn bạn lưu giá trị có khác nhau là mấy đâu.
Mỗi tội chỗ swap thì nên cho thêm if(min!=Arr[i]) thì mới swap.
min có nằm trong mảng đâu bạn, vậy mới sai.
Bất biến là khái niệm trong c/m thuật toán (algorithm correctness) bài này là:
Bất biến là mệnh đề ứng với chương trình, khác với điều kiện lặp. Bất biến phải luôn đúng, điều kiện lặp thì
Anh nói em mới ngộ ra. Đúng là sai thật.