Help With Quick Sort And Merge Sort - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Help With Quick Sort And Merge Sort

Posts: 15Member
Hello everyone. I really need some help. I have an exam in about 2hrs on sorting methods. The exam consists of converting these sorting methods from integers to characters using functions strcmp and strcpy.

Example - myArray[100][50]={"Ann","Tery","Bob",Tom} should return
Ann, Bob, Tery, and Tom

I would be grateful for any help. Below are the two sorting methods I'm having problems with.

MERGE SORT:

void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}

void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);
}
}

void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}

QUICK SORT
void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}

void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}

Thanks for any help!

• Posts: 15Member
Whew, ok, my exam was posponed to Friday , but can something please help me with the converting? Thanks.
• Posts: 1,784Member
: Whew, ok, my exam was posponed to Friday , but can something please help me with the converting? Thanks.
:
What's the prob?
===============================

• Posts: 9,765Member ✭✭✭
: Whew, ok, my exam was posponed to Friday , but can something please help me with the converting? Thanks.
:

we're not doing your homework for you. make your own attempt then post your code and ask questions. It's really not all that difficult task -- there was another very similar thread here just yesterday. All you have to do is search yesterday's threads and find the one that pretty-much answers your question.
• Posts: 15Member
Ok, I tried doing Merge Sort but I'm having problems.

void merge(char numbers[100][50], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (strcmp(numbers[left]numbers[mid]<=0)
{
strcpy(temp[tmp_pos],numbers[left]);
(tmp_pos,tmp_pos + 1);
(left,left +1);
}
else
{
strcpy(temp[tmp_pos],numbers[mid]);
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while (left <= left_end)
{
strcpy(temp[tmp_pos],numbers[left]);
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
strcpy(temp[tmp_pos],numbers[mid]);
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
strcpy(numbers[right],temp[right]);
right = right - 1;
}
}

void m_sort(char numbers[100][50], int temp[], int left, int right)
{
int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}

void mergeSort(char numbers[100][50], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}

• Posts: 9,765Member ✭✭✭
[b][red]This message was edited by stober at 2005-4-28 13:14:1[/red][/b][hr]
: Ok, I tried doing Merge Sort but I'm having problems.
:
:

please learn to post your code inside code tags to make it easier to read. Also post the first few error messages, and identify the in your code where the errors occur.

Code tags are
[ code] [red]<< remove the space before "code"[/red]
[ /code] [red]<< remove the space before "/code"[/red]

If you get hundreds of errors (and I do too) pay close attention to just the first one or two because that's usually where the error occurs. Fix that error then recompile.

Read you code very carefully, paying special attention to the number of open an closing parentheses and braces. For every open one there must be a matching closing one. Some compilers IDEs have a special macro that will find matching braces/brackets/parentheses. *nix vi, vim, and M\$ VC++ 3.0 has them. Don't know about others.

• Posts: 15Member
[b][red]This message was edited by Platinum4 at 2005-4-28 17:53:22[/red][/b][hr]
Okay, forget about merge sort. I found out what the problem was. Now, I'm working on converting quick sort the same way I did with heap and merge earlier. However, I wondering what do I change with the "pivot" in the code?

(15) : error C2664: 'strcpy' : cannot convert parameter 1 from 'char' to 'char *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast

(18) : error C2664: 'strcmp' : cannot convert parameter 2 from 'char' to 'const char *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast

(18) : fatal error C1903: unable to recover from previous error(s); stopping compilation
Error executing cl.exe.

[code]
void q_sort(char numbers[100][50], int left, int right)
{
int l_hold, r_hold;
char pivot;
l_hold = left;
r_hold = right;
strcpy(pivot,numbers[left]);
while (left < right)
{
while ((strcmp(numbers[right],pivot)>=0) && (left < right))
right--;
if (left != right)
{
strcpy(numbers[left],numbers[right]);
left++;
}
while ((numbers[left]<=pivot) && (left < right))
left++;
if (left != right)
{
strcpy(numbers[right],numbers[left]);
right--;
}
}
strcpy(numbers[left],pivot[100]);
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}

void quickSort(char numbers[100][50])
{
q_sort(numbers, 0, 100 - 1);
cout<<numbers[0]<<numbers[1];
}
[/code]

• Posts: 422Member
: (15) : error C2664: 'strcpy' : cannot convert parameter 1 from 'char' to 'char *'
: Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
:
[red] pivot should be declared as a char array, ie:
[code]char pivot[50];[/code][/red]

: (18) : error C2664: 'strcmp' : cannot convert parameter 2 from 'char' to 'const char *'
: Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
:
[red]same as previous.[/red]

: (18) : fatal error C1903: unable to recover from previous error(s); stopping compilation
: Error executing cl.exe.
:
: [code]
: void q_sort(char numbers[100][50], int left, int right)
: {
: int l_hold, r_hold;
: char pivot;
: l_hold = left;
: r_hold = right;
: strcpy(pivot,numbers[left]);
: while (left < right)
: {
: while ((strcmp(numbers[right],pivot)>=0) && (left < right))
: right--;
: if (left != right)
: {
: strcpy(numbers[left],numbers[right]);
: left++;
: }
: while ((numbers[left]<=pivot) && (left < right))
: left++;
: if (left != right)
: {
: strcpy(numbers[right],numbers[left]);
: right--;
: }
: }
: strcpy(numbers[left],pivot[100]);
: pivot = left;
: left = l_hold;
: right = r_hold;
: if (left < pivot)
: q_sort(numbers, left, pivot-1);
: if (right > pivot)
: q_sort(numbers, pivot+1, right);
: }
:
: void quickSort(char numbers[100][50])
: {
: q_sort(numbers, 0, 100 - 1);
: cout<<numbers[0]<<numbers[1];
: }
: [/code]
:
I did not read your code, so perhaps there are other errors. However, I would like to give you a piece of advice. Sorting an array does not really depend on what it contains; the only things that depend on the type of the elements contained in the array are affectation and the function to compare. So, when you've got the code for an int array, it is not hard to modify it in order to sort a string array. Change every affectation between int to a strcpy call, eg:
[code]
i2=i1:
becomes
strcpy(s2,s1);
[/code]
Next, every time you campare int values, change the comparison to a call to strcmp, like in:
[code]
i2<i1
becomes
strcmp(s2,s1)<0
[/code]

Take care, Steph.
• Posts: 15Member
Alright, I changed the code, so there are no errors. However, the names still won't print in order. Where am i going wrong?

[code]
void q_sort(char numbers[5][10], int left, int right)
{
int l_hold, r_hold;
char pivot[5];
l_hold = left;
r_hold = right;
strcpy(pivot,numbers[left]);
while (left < right)
{
while ((strcmp(numbers[right],pivot)>=0) && (left < right))
right--;
if (left != right)
{
strcpy(numbers[left],numbers[right]);
left++;
}
while ((numbers[left]<=pivot) && (left < right))
left++;
if (left != right)
{
strcpy(numbers[right],numbers[left]);
right--;
}
}
strcpy(numbers[left],pivot);
pivot[5] = left;
left = l_hold;
right = r_hold;
if (left < pivot[5])
q_sort(numbers, left, pivot[5]-1);
if (right > pivot[5])
q_sort(numbers, pivot[5]+1, right);
}

void quickSort(char numbers[5][10])
{
q_sort(numbers, 0, 5 - 1);
}

[/code]
• Posts: 422Member
: Alright, I changed the code, so there are no errors. However, the names still won't print in order. Where am i going wrong?
:
: [code]
: void q_sort(char numbers[5][10], int left, int right)
: {
: int l_hold, r_hold,temp;
: char pivot[5];[red]Why 5? Your strings are 10 characters long.[/red]
: l_hold = left;
: r_hold = right;
: strcpy(pivot,numbers[left]);
: while (left < right)
: {
: while ((strcmp(numbers[right],pivot)>=0) && (left < right))
: right--;
: if (left != right)
: {
: strcpy(numbers[left],numbers[right]);
: left++;
: }
: while ([red]strcmp(numbers[left],pivot)<=0[/red] && (left < right))
: left++;
: if (left != right)
: {
: strcpy(numbers[right],numbers[left]);
: right--;
: }
: }
: strcpy(numbers[left],pivot);
: [red]temp=left;[/red]
: left = l_hold;
: right = r_hold;
: if (left < [red]temp[/red])
: q_sort(numbers, left, [red]temp[/red]-1);
: if (right > [red]temp[/red])
: q_sort(numbers, [red]temp[/red]+1, right);
: }
:
: void quickSort(char numbers[5][10])
: {
: q_sort(numbers, 0, 5 - 1);
: }
:
: [/code]
:
There were a few mistakes still; I did not check whether your algorithm does what it is supposed to do; I just corrected the mistakes concerning the pointers.

I hope this works. Take care, Steph.