Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Help With Quick Sort And Merge Sort

Platinum4Platinum4 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!

Comments

  • Platinum4Platinum4 Posts: 15Member
    Whew, ok, my exam was posponed to Friday :), but can something please help me with the converting? Thanks.
  • IDKIDK 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?
    ===============================
    El [b]PRO[/b]grammador Niklas Ulvinge

  • stoberstober 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.
  • Platinum4Platinum4 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);
    }


  • stoberstober 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]
    // your code here
    [ /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.




  • Platinum4Platinum4 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]



  • stephlstephl 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]

    I hope this will help you. If it still does not work, I'll take time to read your code.

    Take care, Steph.
  • Platinum4Platinum4 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]
  • stephlstephl 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.
Sign In or Register to comment.