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