Sorting Program Problems

• 03-04-2003
valar_king
Sorting Program Problems
I've been spending awhile today trying to put together a sorting program. This one is a Quicksort look alike. It almost always sorts 4 count arrays correct but anything more and it sorts them wrong.

The way I want it to work:
Say I gave it the input 3582. It has a left value, 0, and right value, 3, and a middle value, starting out at 0. These correspond to the location of the left, right, and middle point in the array.
Each iteration the left value starts out one to the left of the middle, unless the middle's at the end, then it goes at th end. The right goes to the right of the middle value. It increases the right value and decreases the left value and swaps the two if the left is greater then the right. When both are at the end it moves the middle right one and goes again.
So I want the iterations to give these results:

Code:

```3582 - No swap 3582 - No swap 2583 - 3 and 2 Middle moves to the right 2583 - No swap 2583 - No swap 2583 - No swap Middle moves to the right 2358 - 5 and 3 2358 - No swap 2358 - No swap Middle moves to the right 2358 - No swap 2358 - No swap 2358 - No swap```
It works like this MOST of the time, but never does on numbers with more than four digits. I've been trying to figure it out for a long time. Some help would be much appreciated.
Here's my main.cpp, just a main() to test the stuff in main.h:
Code:

```#include <stdlib.h> #include <stdio.h> #include <time.h> #include <iostream> #include <string> using namespace std; #include "main.h" const int ELEMENTS = 10; int numlist[ELEMENTS]; int main() {  string inp_string, old_string;  srand(time(NULL));  cout << "Quicksort Algorithm\nScott A. Hand\n";  cout << "Generating number list...\n";  for (l=0;l<ELEMENTS;l++)  {   numlist[l] = rand()%10;  }  cout << "Before Sorting: ";  for (l=0;l<ELEMENTS;l++)  {   cout << numlist[l];  }  cout << "\nSorting...\n";  *numlist = sort_int(numlist, (sizeof(numlist)/sizeof(numlist[0])));  cout << "Done.\n";  cout << "After Sorting: ";  for (l=0;l<ELEMENTS;l++)  {   cout << numlist[l];  }  cout << "\nDone, exiting program...\n";  return 0; }```
Here's my main.h with the real code:
Code:

```// (sizeof(numlist)/4+1) int l=0; void swap(int& a, int& b) {  int c;  c = a;  a = b;  b = c; } int sort_int(int inp[], int size) {  int left, middle, right;  int sleft, sright;  left = 0;  right = size;  middle = left;  sleft = middle;  sright = middle + 1;  cout << "Left: " << left << "\nMiddle: " << middle << "\nRight: " << right << endl;  do {   for(;!(sleft < left && sright > right);)   {   if (!(sleft < left && sright > right))   {     if (inp[sleft] > inp[sright])     {     cout << "Swapping " << inp[sleft] << " with " << inp[sright] << endl;     swap(inp[sleft], inp[sright]);     if (middle != left)     {       sleft = middle - 1;     } else     {       sleft = left;     }     if (middle != right)     {       sright = middle + 1;     } else     {       sright = right;     }     }   }   if ((sleft == left && sright == right))   {     break;   }   if (sleft > left)     sleft--;   if (sright < right)     sright++;   }   middle++;   if (middle != left)   sleft = middle - 1;   if (middle != right)   sright = middle + 1;  } while (middle <= right);  return *inp; }```
Thanks
• 03-04-2003
PJYelton
It doesn't work on numbers over 4 because, the way you have it set up, not all digits are compared with each other all the time. Look at something like:

1 5 6 3 9

Nothing gets swapped until 6 is the middle, then 3 and 5 get swapped. But now heres the problem, from here on out, nowhere does 5 and 6 get compared, so you end up with

1 3 6 5 9