Quicksort algorithm issue

Question

Having a problem with my quicksort algorithm. The code compiles without any errors, but when I try to run the program the only output I get is "The random numbers are: " and then acts like it wants input from the user, and then I have to kill the program. Now when I remove the call for my quicksort function in my main program, the program prints out the numbers, but doesn't work with the call for quicksort function. I'm not sure if the parameters I'm using are the issue or if it's the function itself.

#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <stack>
#include <queue>
using namespace std;

void quicksort(int arr[], int left, int right) {
  int l = left;
  int r = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  while (l <= r) {
    while (arr[l] < pivot)
      l++;
    while (arr[l] > pivot)
      r--;
    if (l <= r) {
      tmp = arr[l];
      arr[l] = arr[r];
      arr[r] = tmp;
      l++;
      r--;
    }
  }

  if (left < r)
    quicksort(arr, left, r);
  if (l < right)
    quicksort(arr, r, right);

}

int main() {
  int n = 20;
  int testlist[n];

 for (int i = 0; i<n; i++) {
   testlist[i] = rand()%100;
 }

 cout << "The random numbers are: " << endl;
 for (int i = 0; i < n; i++) cout << testlist[i] << " ";


 quicksort(testlist, 0, n - 1);

 cout << " " << endl;

 cout << "The sorted numbers are: " << endl;
 for (int i = 0; i < n; i++) {
   cout << testlist[i] << " ";
 }

 return 0;

}

One suggestion: plain l (the letter L in lowercase) looks a lot like 1 which is confusing when reading code. — D. Ben Knoble
– D. Ben Knoble, Commented Sep 7, 2016 at 4:25

David Scarlett · Accepted Answer · 2016-09-07 00:25:18Z

4

You have an infinite loop in your quicksort function. As this function never returns, nothing after the "The random numbers are:" line is printed, as the quicksort call never returns. The random numbers themselves may or may not print (and do print on my system) as the system is not guaranteed to flush the output buffer to the screen immediately. (They probably would be printed if you wrote a std::endl to cout after the for loop that prints the numbers.)

I suspect this is the problem:

while (arr[l] > pivot)
    r--;

That statement while (arr[l] > pivot) should probably actually be while (arr[r] > pivot).

edited Sep 7, 2016 at 0:25

answered Sep 6, 2016 at 23:21

David Scarlett

3,3712 gold badges16 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

gsamaras Over a year ago

David sorry, this was my wrong edit, delete your edit! Also, I am afraid this won't solve the problem and the code will crash!

David Scarlett Over a year ago

I've removed my edit to match OP's current/original code. As for the crash, yes, the infinite loop wasn't the only bug in that function. Now would be a good time for OP to learn to use a debugger and step through it to see what is happening... Or just look for similar copy-paste mistakes where they've gotten variables mixed up. ;-)

gsamaras Over a year ago

Thank you David! :) Let me apologize for the confusion. :/

gsamaras · Accepted Answer · 2016-09-06 23:16:54Z

1

This happens because something goes wrong inside quicksort() and you print the numbers without an std::endl!

You see, without the std::endl, the numbers are written in the output buffer, but they are not flushed. They will, eventually, without the std::endl, but that your code doesn't make it to that time.

Pro tip: Always use std::endl when you debug your code!

I won't debug your quicksort(), since you should do that, in order to practice! If you need a reference, you can always use my baby example: Quicksort (C++), which is written in a c-like way, so that people from both c and c++ can easily follow! :)

Hunch: You use recursion, your program doesn't terminate...Infinite loop may be the cause... ;)

BTW, if I were you and didn't have any important reason to use:

#if __INCLUDE_LEVEL__ < 1

I would discard that (along with the accompanied #endif).

edited Sep 6, 2016 at 23:16

answered Sep 6, 2016 at 23:11

gsamaras

73.7k50 gold badges210 silver badges330 bronze badges

2 Comments

Mooing Duck Over a year ago

I see his bug, it's just a regular, run-of-the-mill infinite loop

gsamaras Over a year ago

I tried so hard not to tell his bug so he can practice. Fortunately the other answer doesn't solve the issue, and I hope that he will debug seeing your code Mr. Psyduck. :)

Collectives™ on Stack Overflow

Quicksort algorithm issue

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related