Thắc mắc Selection Sort?

#1

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]);
    }
}
#2

Ngay sau đó min bị ghi đè nên câu lệnh không khác Arr[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.

1 Like
#3

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ĩ :joy:

1 Like
#4

Đến thế thì std::sort cho rồi :expressionless: đang học mà.

3 Likes
#5

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ế.

#6

có link chi tiết không ban?

#7

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.

#8

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) :slight_smile: bài này là:

  • Mảng lúc nào cũng phải là hoán vị của mảng ban đầu. (chung cho các thuật toán sắp xếp)
  • a[i] là phần tử nhỏ thứ i dưới thứ tự <= cho trước. Ta nhớ rằng hoán vị không giảm là hoán vị mà thành phần thứ i cũng nhỏ thứ i.

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ì :grin:

2 Likes
#9

Anh nói em mới ngộ ra. Đúng là sai thật.

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