Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 274
  • Last Modified:

Quick Sort Help.

I wrote the following code for Quick Sort. It doesn't work as its supposed to and it goes into an infinite loop. Can someone point out where Im going wrong?

#include<iostream.h>
#include<conio.h>

int array[10] = {9,8,7,6,5,4,3,2,1,0};
int temp[10] = {0,0,0,0,0,0,0,0,0,0};

void quicksort(int start, int end)
{
    cout<<"Set to Sort:\n";
    for(int i=start;i<=end;i++)
        cout<<array[i]<<" ";
   
    cout<<endl;
   
    int middle = (end-start)/2;
    int pivot = array[middle];
    int pos=start;
    int size = (end-start)+1;

    for(int i=start; i<=end; i++)
        if(array[i] < pivot)
                temp[pos++] = array[i];
   
    temp[pos++] = pivot;
   
    for(int i=start; i<=end; i++)
        if(array[i] > pivot)
                temp[pos++] = array[i];
               
    for(int i=start;i<=end;i++)
        array[i]=temp[i];
   
   
    if (size == 1 || size < 1)
    {
        cout<<"Sorting Set Ends!\n\n";
        return;
    }
    else
    {
        cout<<"\nSorting Results and Attributes\n";
        cout<<"Size:"<<size<<"   Middle:"<<middle<<"   Pivot:"<<pivot<<endl;
        for(int i=start; i<=end; i++)
                cout<<array[i]<<" ";
        cout<<"\n\n-----------------------------------------\n\n";
        getch();cout<<endl;
       
        quicksort(start, middle);
        cout<<"\n\n----------------drill ends---------------\n\n";
        quicksort(middle+2, end);
    }
}

void main()
{
    int start = 0;
    int end = 9;
   
    quicksort(start,end);
   
    cout<<"\n\n\nSorting End Results:\n";
    for(int i=start; i<=end; i++)
        cout<<array[i]<<" ";
   
    getch();
}
0
lexxwern
Asked:
lexxwern
1 Solution
 
Roshan DavisCommented:
Here is the code for 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);
}


You can find the Algorithm Analysis Here
http://linux.wku.edu/~lamonml/algor/sort/quick.html

Good Luck
0
 
jasonclarkeCommented:
Here is a fixed version of your code, your problems seem to be in working out the 'middle' value correctly and in the selection of the pivot point.

void quicksort(int start, int end)
{
   cout<<"Set to Sort:\n";
   for(int i=start;i<=end;i++)
       cout<<array[i]<<" ";
   
   cout<<endl;
   
   int middle = (end-start)/2 + start;
   int pivot = array[middle];
   int pos=start;
   int size = (end-start)+1;

   for(int i=start; i<=end; i++)
   {
       if(array[i] < pivot)
               temp[pos++] = array[i];
   }
   
   int pivotPoint = pos;
   temp[pos++] = pivot;
   
   for(int i=start; i<=end; i++)
   {
       if(array[i] > pivot)
               temp[pos++] = array[i];
   }
               
   for(int i=start;i<=end;i++)
       array[i]=temp[i];
   
   
   if (size == 1 || size < 1)
   {
       cout<<"Sorting Set Ends!\n\n";
       return;
   }
   else
   {
       cout<<"\nSorting Results and Attributes\n";
       cout<<"Size:"<<size<<"   Middle:"<<middle<<"   Pivot:"<<pivot<<endl;
       for(int i=start; i<=end; i++)
               cout<<array[i]<<" ";
       cout<<"\n\n-----------------------------------------\n\n";
       getch();cout<<endl;
       
       quicksort(start, pivotPoint-1);
       cout<<"\n\n----------------drill ends---------------\n\n";
       quicksort(pivotPoint+1, end);
   }
}
0
 
arjkaneCommented:
Why don't you just use qsort() in stdlib.h?
0
 
lexxwernAuthor Commented:
roshmon, thanks but i wanted to write my own code.

jasonclarke, that worked perfectly ... thanks for pointing "int middle = (end-start)/2 + start;" out ... points goto you.

arjkane, as mentioned earlier i had to write my own code ...


once again thankyou everybody!
0
 
simpsons17371Commented:
i tried that program and it works fine, thats cool.
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now