CODEWITHSUNDEEP
c++algorithmfunctionsortingquicksort
Nar1y
Nar1y

Reputation: 25

Quicksort algorithm issue

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;

}

Upvotes: 0

Views: 114

Answers (2)

David Scarlett
David Scarlett

Reputation: 3341

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).

Upvotes: 4

gsamaras
gsamaras

Reputation: 73366

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 -like way, so that people from both and 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).

Upvotes: 1

Related Questions