Need help to display the process of partitioning and sorting of quick sorting

i am totally new to programming and i have to do quick sort programming and i can't seem to find the correct code to write for the sorting, this is the best i can do though





insert

Code:

---

#include <stdio.h>
#include <conio.h> 
 #define cutoff 3 
 void swap(int *a,int *b) 
 { 
    int temp=*a; 
    *a=*b; 
    *b=temp; 
 } 
 int median(int a[],int left,int right) 
 { 
  int center=(left+right)/2; 
  if(a[left]>a[center]) 
  swap(&a[left],&a[center]); 
  if(a[left]>a[right]) 
  swap(&a[left],&a[right]); 
  if(a[right]<a[center]) 
  swap(&a[right],&a[center]); 
  swap(&a[center],&a[right-1]); 
  return a[right-1]; 
 } 
 void insertionsort(int A[],int n) 
 { 
 int j,p,temp; 
 for(p=1;p<n;p++) 
 { 
 temp=A[p]; 
 for(j=p;j>0&&A[j-1]>temp;j--) 
 A[j]=A[j-1]; 
 A[j]=temp; 
 } 
 } 
 void qsort(int a[],int left,int right) 
 { 
    int i,j,pivot; 
    if(left+cutoff<=right) 
    { 
    pivot=median(a,left,right); 
    i=left; 
    j=right-1; 
    while(1) 
    { 
        while(a[++i]<pivot){} 
        while(a[--j]>pivot){} 
        if(i<j) 
        swap(&a[i],&a[j]); 
        else 
        break; 
    } 
    swap(&a[i],&a[right-1]); 
    qsort(a,left,i-1); 
    qsort(a,i+1,right); 
    } 
    else 
    insertionsort(a+left,right-left+1);   
 }
 

 
 
 
 
 void quicksort(int a[],int n) 
 { 
    qsort(a,0,n-1); 
 } 
 int main() 
 { 
  printf("Unsorted array:\n8,5,2,13,1,17,6,4,9,15,7,3\n");
  printf("Sorted array: \n");
  int a[]={8,5,2,13,1,17,6,4,9,15,7,3}; 
  quicksort(a,12); 
  int i; 
  for(i=0;i<12;i++) 
 
    {
    printf("%d ",a[i]); 
    } 
    getch(); 
 }

---

Can't FIND a program??

Oh my! :(

We're not a code library or scavenger oriented forum, but your Quicksort is similar to the one I use.

What part of your program is working OK, -- and what part is NOT working OK?

You will not learn anything about writing code (or Quicksort), by just posting bad code, and saying "It doesn't work". Roll up your sleeves and show some interest in fixing this. Quicksort is a brilliant piece of logic! REALLY worth your time to learn about it.

I don't mean to be crude or rude, but the fact is, if you don't show some increased interest in this, why should anyone else take it upon themselves to work on it?

Do you get warnings from your compiler (and are your warnings turned on)?
Do you have any compiler errors

If you try to sort 7 int's (0,1,2,3,4,5,6,7), what is the output from the program?
Now try (5,4,7,6,0,3,2,1) and see what you get.

You are actually pretty close.
One thing I see that is a problem is your inner while loops.
"i" starts at "left", then the ++i adjusts that to left+1 before it looks at the item in the array.
Similarly, the first item it indexes with j will be right-2.

Have you traced it through in a debugger?

everything is working i only don't know what to type in for displaying the partitioning and sorting when i run it

Oh wow, you're right, it passes every test I threw at it. It does in fact appear to sort correctly! I can see why now too.

If you are interested in drawing the items and animating the sorting process, then you need to put in some delays, and add some code to draw the items in their positions at various points throughout the sorting.
I have a program which can animate lots of sorting algorithms here. Perhaps that is the kind of thing you are wanting to make?
Or perhaps you just want to show numbers in the console?

Adak nailed it. Typical copy/paste Turbo C code. The OP has no idea how to program (because he's a copy/paster), so the code doesn't exactly satisfy his assignment. Solution: find someone to give him the code to complete it.

Unfortunately i'm only a beginner and i was told to search from the net to complete and the only hint given is this quick sort program running as shown in the picture
(Display array of unsorted numbers which is defined as 8,5,2,13,1,17,6,4,9,15,7,3 , display process of partitioning and sorting, display the final sorted product)

Attachment 11796Attachment 11797

I'm using Dev-C++ to write this program and i only can use C program code when i wasn't even guided what am i supposed to find

Quote:

---

Originally Posted by Low Chee Kwan

Unfortunately i'm only a beginner and i was told to search from the net to complete and the only hint given is this quick sort program running as shown in the picture

---

Are you taking a programming class, or a "how to use google" class?

Exactly. No source code to learn from. I don't understand why this task was even given

can anyone show example or explain on which part of the code should i print array to show the process as shown in the picture?

Quote:

---

Originally Posted by Low Chee Kwan

can anyone show example or explain on which part of the code should i print array to show the process as shown in the picture?

---

My suggestion is to make the printing loop you have now in main(), into a printIt function by itself. Then call the printIt function: (and remove the current for loop used for printing from main(), and move it to the printIt function). Then:

1) Before the start of the sort. Remove the current (first) print line in main(), and replace it with a call to the printIt function.
2) After the mid point has been selected - and highlight the mid point number, perhaps by printing it with a yellow color so it stands out
3) After each swap
4) Immediately after each recursive call to qsort()

Adding newlines as needed.

Instead of printing all the array, all the time you call printIt(), I would just print the sub-array part that is actually being sorted, with each call. So if you have 10 numbers, you print all 10 numbers on the first, and on the last calls to printIt(). All the other calls to printIt(), you print only the part of the array, that you are passing to qsort().

It sounds more difficult than it is to do this - you already are passing the parameters you would use for printIt(), to qsort().

Your program has this recursive call:

Code:

---


qsort(a,left,i-1);

---

And you would then call printIt() with:

Code:

---

qsort(a,left,i-1);
printIt(a, left, i-1);

---

So you're printing the subarray between left and i-1, only at that time.

Similarly,

Code:

---

qsort(a,i+1,right);

//becomes
qsort(a,i+1,right);
printIt(a, i+1, right);

---

Since now you want to print out the sub-array between i+1, and right.

Also, print out the entire array is before you call the Insertion sort function.

not quick sure what you mean but i'll give it another try thanks a lot

Quote:

---

Originally Posted by Low Chee Kwan

not quick sure what you mean but i'll give it another try thanks a lot

---

In your example above, you are printing out the entire array, every time you print any part of the array.

My suggestion was to print out only the part of the sub-array, that was being sorted, at that moment, instead.

Quicksort works by repeatedly taking the array, choosing a pivot value, and moving the array values in comparison to that pivot. (Lower numbers go to the left, higher numbers go to the right). With every recursive call, the range of the array index being worked on, is cut down - that's why the call to qsort() has a variable for left and right (low and high) index values being passed to it, instead of just 0 and N-1 all the time. (Where 0 to N-1 is the full size of the array indexes). So as the recursive calls continue, the part of the array being sorted at that time, becomes progressively smaller.

The beauty of the recursive Quicksort, is that these sub-array's being worked on (and there will be several of them), are all seamlessly put back "together" (rejoined), by the return from the recursive calls. If you haven't seen this before, it's a bit like magic, the way recursive calls keep track of all this, without anything being needed from you.

This problem you're having now does highlight the problem with copy/pasting available code. As sure as the sun rises in the East, you're going to want code that does something - and you won't be able to find it! Now you're stuck!

Try adding some print statements as I suggested above, and post that code, along with whatever problems you now are having.

We can help, but we need to see what you're doing with the code, to understand how to help you.

i haven't learn much about call function so i not sure how to relate printIt with the quick function i get printIt undeclared when i run it

Code:

---

#include <stdio.h>
#include <conio.h> 
 #define cutoff 3 
 void swap(int *a,int *b) 
 { 
    int temp=*a; 
    *a=*b; 
    *b=temp; 
 } 
 int median(int a[],int left,int right) 
 { 
  int center=(left+right)/2; 
  if(a[left]>a[center]) 
  swap(&a[left],&a[center]); 
  if(a[left]>a[right]) 
  swap(&a[left],&a[right]); 
  if(a[right]<a[center]) 
  swap(&a[right],&a[center]); 
  swap(&a[center],&a[right-1]); 
  return a[right-1];
 } 
 void insertionsort(int A[],int n) 
 { 
 int j,p,temp; 
 for(p=1;p<n;p++) 
 { 
 temp=A[p]; 
 for(j=p;j>0&&A[j-1]>temp;j--) 
 A[j]=A[j-1]; 
 A[j]=temp;
 } 
 } 
 void qsort(int a[],int left,int right) 
 {   
    int i,j,pivot; 
    if(left+cutoff<=right) 
    { 
    pivot=median(a,left,right); 
    i=left; 
    j=right-1; 
    while(1) 
    { 
        while(a[++i]<pivot){} 
        while(a[--j]>pivot){} 
        if(i<j) 
        swap(&a[i],&a[j]); 
        else 
        break;
       
    } 
    swap(&a[i],&a[right-1]); 
    qsort(a,left,i-1);
    printIt(a, left, i-1);   
    qsort(a,i+1,right);     
    printIt(a, i+1, right);
    } 
    else 
    insertionsort(a+left,right-left+1);
 
 
 }
 
 void printIt()
 {
      printf("%d", a[i]);
}
 
 
 
 
 void quicksort(int a[],int n) 
 { 
    qsort(a,0,n-1); 
 } 
 int main() 
 { 
  printf("Unsorted array:\n8,5,2,13,1,17,6,4,9,15,7,3\n");
  printIt( );
 printf("\n\t");
system("pause");
return 0;
}

---

void printIt() is not recognized, because you don't have the parameters correct for it. You want to change line #63 to

Code:

---

void printIt(int a[], int left, int right) {
  int i;
  for(i=left, i<right;i++)
      printf("%2d ",a[i]);
  printf("\n");
}

---

Then, whenever you want to print out the array (the part that you want of it at least), you'd use:

Code:

---

printIt(a, NameOFLeftVariable, NameOFRightVariable);

so your first call (where you want to print all the numbers), would be
printIt(a, 0, 12);

---

But, instead of using 12, I would add a

#define N 12

Right below your other define at the top of your program. Then use printIt(a, 0, N).

And you removed the call to quicksort() in this version of your program. You need that added back into the program, as it was before.