質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

解決済

C++でクイックソートの実装に失敗

Cas9bah
Cas9bah

総合スコア2

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

1回答

0グッド

0クリップ

257閲覧

投稿2022/11/19 09:42

前提

C++でクイックソートを実装しようとしています。

実現したいこと

昇順に配列をクイックソートしたいのですが、ここまで書いたコードの何が間違っているのか把握したいです。

発生している問題・エラーメッセージ

値が返ってきません。

該当のソースコード

C++

1#include<bits/stdc++.h> 2using namespace std; 3#include<time.h> 4 5int partition(vector<int>&A, int l, int r, int pivot){ 6 for(;;){ 7 while(A[l] < pivot){ 8 l++; 9 } 10 while(A[r] >= pivot) { 11 r--; 12 } 13 if(l > r) { 14 return l; 15 break; 16 } 17 swap(A[l], A[r]); 18 } 19} 20 21void QuickSort(vector<int>&a, int i, int j){ 22 if(i >= j) return; 23 int pivot; 24 bool t = 0; 25 for(int n = i; n <= j; n++) { 26 if(a[n] != a[n+1]) { 27 pivot = max(a[n], a[n+1]); 28 t = 1; 29 } 30 } 31 if (t=0) return; 32 int k = partition(a,i,j,pivot); 33 QuickSort(a,i,k-1); 34 QuickSort(a,k+1,j); 35} 36 37int main() { 38 int N = 5; 39 vector<int> data = {2,1,4,5,3}; 40 clock_t start = clock(); 41 QuickSort(data,0,N-1); 42 clock_t end = clock(); 43 cout << (double)(end - start) << endl; 44}

試したこと

コード例を参考にしつつ怪しい部分を書き直しました。

補足情報(FW/ツールのバージョンなど)

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

y_waiwai

2022/11/19 11:17 編集

どーゆーふーに値が返ってこないんでしょうか
Cas9bah

2022/11/19 13:46

なにも出力されません。

回答1

0

ベストアンサー

QuickSort内の以下の行、n <= jではなくn < jじゃないの?

c++

1for(int n = i; n <= j; n++) {

次の行でa[n+1]にアクセスするので、n=jまでループを回すとa[j+1](i~jの範囲外)にアクセスしてしまうのでは。

投稿2022/11/19 14:09

actorbug

総合スコア1758

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。