VicRock09
@VicRock09 (Vicky rock)

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

トラブルシューティングについてサポートが必要ですか? クイックソートアプリケーション

C++ でクイック ソート アルゴリズムを構築しようとしましたが、コードが正しく動作していないようです。 コードの関連セクションは次のとおりです。

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>& arr, int low, int high) {
    if (low >= high)
        return;

    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);

    quickSort(arr, low, i);
    quickSort(arr, i + 2, high);
}

// Example usage
int main() {
    vector<int> myArray = {38, 27, 43, 3, 9, 82, 10};
    quickSort(myArray, 0, myArray.size() - 1);

    for (int num : myArray) {
        cout << num << " ";
    }

    return 0;
}

サンプル myArray を使用してコードを実行すると、結果は不正確になります。 配列の分割方法か、quickSort メソッドの再帰呼び出しに問題があると思います。

私のコードを評価して、エラーや改善の余地がある箇所を指摘していただけますか? この記事を研究し、雰囲気をつかむために多くの例を調べましたが、それでも合格できませんでしたか? クイック ソート実装を適切に動作させるために役立つ提案や変更をいただければ幸いです。

ありがとう

0

2Answer

サンプル myArray を使用してコードを実行すると、結果は不正確になります

3 9 10 27 38 43 82
正しくソートされているように見えますが・・・

2Like

改善の余地がある箇所を指摘

quickSortは議論され尽くしている感があります。上記URLコードをご参照ください。
再帰定義は言語によっては関数の起動にもたつくときがあります。そこで、quickSortのアルゴリズムを再帰定義を使わない方法で実現している方もいます。

 ruby,python,awkでその言語でquickSortを実装しましたが、内部関数の速度には敵いませんでした。尚、最速はawkでした。

私はcombsortがお気に入りです。
組み合わせることで新たなアルゴリズムを発見するかもしれません?

1Like

Your answer might help someone💌