8 Replies - 329 Views - Last Post: 11 February 2014 - 10:22 AM Rate Topic: -----

#1 desinerd93  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 13-September 13

QuickSorting Help!

Posted 09 February 2014 - 12:15 PM

Hey Guys! I am having some problem with my quick sort problem. My program is supposed to create 5 arrays with 5,10,15,and 20 random integers, respectively. Then it should sort those arrays, where the numbers are bigger or smaller than the middle element in the original array! The program I wrote should do that but, its not! The program just keeps running infinitely! Can you please help me with this? (I'm still new to coding so its pretty basic code!
#include <iostream>
#include <cstdlib>
using namespace std;

void p(int k[],int left, int right) {
      int i = left, j = right;
      int n;
      int m = k[(left + right) / 2];
      cout<<"Middle Element:"<<m <<endl;
      while (i <= j) {
        while (k[i] < m)
            i++;
        while (k[j] > m)
            j--;
            if (i <= j) {
                n = k[i];
                k[i] = k[j];
                k[j] = n;
                i++;
                j--;
            }
      };
      if (left < j)
            p(k, left, j);
      if (i < right)
            p(k, i, right);
}
int main (){
	int i=0;
	int k[i],left,right;
	for (int i=0;i<=20;i+5){
	   k[i]= rand()%100;
	   cout<<"Before:"<<k[i]<<endl;
    }
    p(k,left,right);
    cout<<"After:"<<k[i]<<endl;
    return 0;
}


Is This A Good Question/Topic? 0
  • +

Replies To: QuickSorting Help!

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4068
  • View blog
  • Posts: 12,550
  • Joined: 25-December 09

Re: QuickSorting Help!

Posted 09 February 2014 - 12:32 PM

I don't see how it runs indefinitely since it doesn't even compile for me.

Quote

main.cpp||In function ‘void p(int*, int, int)’:|
main.cpp|5|warning: no previous declaration for ‘void p(int*, int, int)’ [-Wmissing-declarations]|
main.cpp||In function ‘int main()’:|
main.cpp|30|error: ISO C++ forbids variable length array ‘k’ [-Wvla]|
main.cpp|31|warning: declaration of ‘i’ shadows a previous local [-Wshadow]|
main.cpp|29|warning: shadowed declaration is here [-Wshadow]|
main.cpp|31|warning: for increment expression has no effect [-Wunused-value]|
||=== Build finished: 1 errors, 4 warnings (0 minutes, 0 seconds) ===|


Array sizes in C++ must be compile time constants. Plus you can't create an array with a size of zero.

Jim

This post has been edited by jimblumberg: 09 February 2014 - 12:33 PM

Was This Post Helpful? 0
  • +
  • -

#3 desinerd93  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 13-September 13

Re: QuickSorting Help!

Posted 09 February 2014 - 03:40 PM

jimblumbergThanks for your reply! Im still new at programming, so sorry if my questions sound dumb! But I'm confused by what you mean when you say array sizes in C++ must be compile time constants? How would I do that in my program? I fixed what you said about the array size not being 0, and the program did compile in Dev++ but it is still running infinitely!

int main (){
	int i;
	int k[i],left,right;
	for (int i=5;i<=20;i+5){
	   k[i]= rand()%100;
	   cout<<"Before:"<<k[i]<<endl;
    }
    p(k,left,right);
    cout<<"After:"<<k[i]<<endl;
    return 0;
}

Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is online

  • member icon


Reputation: 4068
  • View blog
  • Posts: 12,550
  • Joined: 25-December 09

Re: QuickSorting Help!

Posted 09 February 2014 - 04:21 PM

Did you look at and fix all the errors/warnings I posted? Answer, No.


Quote

I fixed what you said about the array size not being 0,

But you actually made things worse. Now the size of the array is undefined because you're using an uninitialized non-constant variable for the size of your array. Look at the following snippet:
    int i;  // i is uninitialized
    int k[i]; Now you use this uninitialized value to size your array.


Quote

How would I do that in my program?

You either use a constant or you use the const qualifier on your variable.

int k[10]; // Using a constant for the size.
const int MAX = 10; // Create a variable with the const qualifier.
int k[MAX]; // Use the const qualified variable  to set the size.



And don't forget to look at this warning and be sure you fix it!

Quote

main.cpp|31|warning: for increment expression has no effect [-Wunused-value]|

Here is the line where this warning is referring.
    for (int i=5;i<=20;i+5){

Look closely at the increment section of the above snippet, it isn't doing anything.


You need to read the documentation for your IDE and find out how to increase the compiler warning levels. By default the compiler doesn't issue enough warnings for a novice programmer. You need to increase the warnings to the maximum allowed by your IDE.


Jim

Edit:
Also look closely at the 5th and 6th warnings I posted, here is the code in question:
	int i;  // Uninitialized.
...
	for (int i=5;i<=20;i+5){ // Shadowing happens here. This i is not the same as the previous instance.
...
    cout<<"After:"<<k[i]<<endl; // i is uninitialized.


In the above snippet i in the last line is uninitialized because you never initialized it initially. The warning is talking about a "shadowed declaration" the i in the for loop is a different variable, even though the names are the same.

Jim

This post has been edited by jimblumberg: 09 February 2014 - 04:29 PM

Was This Post Helpful? 0
  • +
  • -

#5 Switters  Icon User is offline

  • D.I.C Head

Reputation: 25
  • View blog
  • Posts: 110
  • Joined: 03-June 12

Re: QuickSorting Help!

Posted 11 February 2014 - 07:15 AM

View Postjimblumberg, on 09 February 2014 - 12:32 PM, said:

Array sizes in C++ must be compile time constants. Plus you can't create an array with a size of zero.

Jim


I disagree with the latter comment. This compiles and runs with no issue:

#include <iostream>

using namespace std;

int main()
{
    cout << "Hello world!" << endl;

    int myArray[0];
    cin.get();
    return 0;
}



So does this:

#include <iostream>
#include <array>

using namespace std;

int main()
{
    cout << "Hello world!" << endl;

    array<int,0> myArray;
    cin.get();
    return 0;
}



Why one would want to do this is another question, of course.
Was This Post Helpful? 0
  • +
  • -

#6 jimblumberg  Icon User is online

  • member icon


Reputation: 4068
  • View blog
  • Posts: 12,550
  • Joined: 25-December 09

Re: QuickSorting Help!

Posted 11 February 2014 - 08:47 AM

Quote

I disagree with the latter comment. This compiles and runs with no issue:

I get the following error messages when I try to compile your first snippet.

Quote

main.cpp||In function ‘int main()’:|
main.cpp|9|error: ISO C++ forbids zero-size array ‘myArray’ [-Wpedantic]|
main.cpp|9|warning: unused variable ‘myArray’ [-Wunused-variable]|
||=== Build finished: 1 errors, 1 warnings (0 minutes, 0 seconds) ===|


So perhaps you're using some kind of compiler "hack" or you have a broken compiler, but standard C++ doesn't allow zero sized arrays. Just because something compiles doesn't make it correct.

By the way I wasn't talking about std::array, just basic arrays, your second snippet is correct and should compile but like you I don't see much use for zero sized std::arrays.

Jim

This post has been edited by jimblumberg: 11 February 2014 - 08:49 AM

Was This Post Helpful? 0
  • +
  • -

#7 Switters  Icon User is offline

  • D.I.C Head

Reputation: 25
  • View blog
  • Posts: 110
  • Joined: 03-June 12

Re: QuickSorting Help!

Posted 11 February 2014 - 09:09 AM

GNU GCC [-std=C++11]

No hacks, all warnings (and "extra" warnings) are turned on. It isn't guaranteed to be portable, however.

See also: http://herbsutter.co...gth-array-okay/

This post has been edited by Skydiver: 11 February 2014 - 10:52 AM
Reason for edit:: Removed unnecessary quote. No need to quote the message above yours.

Was This Post Helpful? 0
  • +
  • -

#8 jimblumberg  Icon User is online

  • member icon


Reputation: 4068
  • View blog
  • Posts: 12,550
  • Joined: 25-December 09

Re: QuickSorting Help!

Posted 11 February 2014 - 09:25 AM

Quote

No hacks,

Wrong, unless you use another switch your compiler is using hacks. The switch is -Wpedantic to turn off all compiler "hacks".

That link also points this out:

Quote

So the reader is quoting from 8.3.4 [dcl.array], which governs non-heap allocated arrays (e.g., T array[N];)/>. In that case, a zero length is not allowed by the standard.

And since we're not talking about dynamic arrays using new, this still holds:

Quote

"If the constant-expression (5.19) is present, it shall be an integral constant expression and its value shall be greater than zero."


Quote

You canít rely on it in portable code because although it is allowed as an extension in some popular compilers (e.g., Gnu gcc) it is treated as an error in others (e.g., Visual C++).

The it being zero length arrays. I do disagree about the portable part, because if you use the correct compiler switches it's an error with both compilers listed. IMO you shouldn't be using compiler hacks, unless you know exactly what they are and the "gotchas" associated with the various hacks.

Jim

This post has been edited by jimblumberg: 11 February 2014 - 09:26 AM

Was This Post Helpful? 2
  • +
  • -

#9 Switters  Icon User is offline

  • D.I.C Head

Reputation: 25
  • View blog
  • Posts: 110
  • Joined: 03-June 12

Re: QuickSorting Help!

Posted 11 February 2014 - 10:22 AM

Defeat admitted.

I am dishonored!

Posted Image

This post has been edited by Skydiver: 11 February 2014 - 10:51 AM
Reason for edit:: Removed unnecessary quote. No need to quote the message above yours.

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1