Sorting Program Problems

This is a discussion on Sorting Program Problems within the C++ Programming forums, part of the General Programming Boards category; I've been spending awhile today trying to put together a sorting program. This one is a Quicksort look alike. It ...

  1. #1
    Satan valar_king's Avatar
    Join Date
    Aug 2001
    Posts
    288

    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
    -Save the whales. Collect the whole set.

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Have a few minor problems trying to finish this program
    By kisiellll in forum C Programming
    Replies: 4
    Last Post: 02-22-2009, 07:00 PM
  2. Problems with DLLEXPORT while updating a program
    By pirata in forum C++ Programming
    Replies: 3
    Last Post: 09-05-2008, 02:00 PM
  3. Sorting Problems
    By Surfin_Bird in forum C Programming
    Replies: 10
    Last Post: 03-26-2005, 02:30 PM
  4. Problems with easy program
    By chuckster in forum C++ Programming
    Replies: 2
    Last Post: 09-09-2004, 12:08 PM
  5. Replies: 1
    Last Post: 10-18-2003, 10:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21