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

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

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

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

ソート

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

Q&A

解決済

1回答

497閲覧

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

Cas9bah

総合スコア2

アルゴリズム

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

ソート

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

0グッド

0クリップ

投稿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/ツールのバージョンなど)

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

y_waiwai

2022/11/19 11:17 編集

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

2022/11/19 13:46

なにも出力されません。
guest

回答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

総合スコア2224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.48%

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

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

質問する

関連した質問