Lỗi sinh số lạ trong thuật toán Merge Sort

#1

Hi mọi người. Em có viết đoạn code thuật toán merge sort sau theo ý tưởng thông thường:
Hàm mergeSort() thực hiện việc sort bằng cách chia đôi mảng ban đầu ra thành 2 mảng con và tiếp tục như thế. Sau đó dùng Merge() để trộn 2 mảng con đã sắp xếp.

#include <iostream>
#include <vector>

using namespace std;

vector<int> Merge(const vector<int> &v1, const vector<int> &v2)
{
    vector<int> res;
    int s1 = v1.size(), s2 = v2.size(), i, j;
    /*
    cout << endl;
    for (int i = 0; i < s1; ++i)
        cout << v1[i] << " ";
    cout << endl;
    for (int i = 0; i < s2; ++i)
        cout << v2[i] << " ";
    cout << endl;
    */
    for (i = 0, j = 0; i < s1, j < s2;) {
        if (v1[i] <= v2[j]) {
            res.push_back(v1[i]);
            ++i;
        }
        else {
            res.push_back(v2[j]);
            ++j;
        }
    }
    if (i < s1) {
        for (int var = i; var < s1; ++var)
            res.push_back(v1[var]);
    }
    else {
        for (int var = j; var < s2; ++var)
            res.push_back(v2[var]);
    }
    return res;
}

vector<int> mergeSort(const vector<int> &arr, int left, int right)
{
    // 3 9 7 1 5 4 2
    if (left == right) return vector<int>{arr[left]};
    int m = (left + right) / 2;
    vector<int> first = mergeSort(arr, left, m);
    vector<int> second = mergeSort(arr, m + 1, right);
    vector<int> res = Merge(first, second);
    /*
    for (auto &it : res) cout << it << " ";
    cout << endl;
    */
    return res;
}

int main()
{
    vector<int> arr{3, 9, 7, 1, 5, 4, 2};
    vector<int> res = mergeSort(arr, 0, arr.size() - 1);
    for (auto &it : res) cout << it << " ";
    return 0;
}

Lấy 1 ví dụ đơn giản là mảng sau: 3, 9, 7, 1, 5, 4, 2
Kết quả sau khi sort là: 1 2 3 0 0 0 0 0 4 5 7 9 (trên IDEone)
và 1 2 3 0 4 5 7 9 (trên Codeblocks)
Điểm chung về lỗi là cứ dư 1 số 0 giữa số 3 và số 4. Nên mình cho thêm vài dòng cout ở trong hàm mergeSort() và hàm Merge() để in ra kết quả mỗi lần xử lý. Thì ở lần đầu tiên mình thấy việc xử lý trong hàm Merge() như sau:
vecto v1: 3
vecto v2: 9
kết quả sau khi xử lý trong hàm Merge(): 3 0 9
Ngay lần đầu đã xuất hiện số 0 nhưng ở những lần merge sau (VD 7 1) thì kết quả ra bình thường (1 7) …
Mình xem kỹ hoài vẫn ko biết bug ở đâu, mong mọi người giúp đỡ!
Thanks in advance!

#2

dấu phẩy là sao đây???

3 Likes
#3

Mình để 2 biến chạy song song ấy? VD 2 mảng là: 1 3 7 9 và 2 4 5 thì chỉ số i của mảng 1 và chỉ số j của mảng 2, rồi mình cứ so sánh 2 phần tử đầu tiên của 2 mảng rồi push vào mảng res và tăng i hoặc j ?

#4

dấu phẩy trong C++ có ý nghĩa khác :V Cái điều kiện thoát vòng lặp for kia là gì bạn nói tiếng Việt ra được ko?

4 Likes
#5

À về cái này thì trước giờ mình cứ nghĩ lập khuông là i < s1, j < s2 có nghĩa là vòng lặp sẽ được thoát khi biến i >= s1 hoặc j >= s2 (1 trong 2) có đúng ko nhỉ ?

#6

đúng là i >= s1 hoặc j >= s2 nhưng dấu phẩy trong C++ ko có nghĩa là “hoặc” :V Dấu “hoặc” trong C++ là gì :V

4 Likes
#7

dấu phẩy là “và” chứ hả ? i < s1, j < s2 có nghĩa là i < s1 và j < s2 là điều kiện duy trì vòng lặp, suy ra điều kiện thoát là i >= s1 || j >= s2 (mình hơi bị rối chỗ này chút!)

#8

dấu phẩy ko phải là “và”. Dấu “và” khác mà :V Hình như đâu có ngôn ngữ lập trình nào cho dấu phẩy mang ý nghĩa “và” đâu :V

hoặc là || còn và là …

5 Likes
#9

OH god não bị rồi loạn mất !
Thanks bạn nhiều nhé: i < s1 && j < s2

Vậy là dấu phẩy chỉ dùng ở chỗ int i = 0, j = 0; thôi hả?

#10

chắc vậy :V Còn có dùng chỗ khác nhưng cái này black magic ko nên đụng vào…

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