?
Solved

Quick Sort Help.

Posted on 2003-03-13
5
Medium Priority
?
270 Views
Last Modified: 2010-04-01
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
Comment
Question by:lexxwern
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
5 Comments
 
LVL 23

Expert Comment

by:Roshan Davis
ID: 8129293
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
 
LVL 9

Accepted Solution

by:
jasonclarke earned 2000 total points
ID: 8129411
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
 

Expert Comment

by:arjkane
ID: 8130946
Why don't you just use qsort() in stdlib.h?
0
 
LVL 12

Author Comment

by:lexxwern
ID: 8133421
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
 
LVL 1

Expert Comment

by:simpsons17371
ID: 8142799
i tried that program and it works fine, thats cool.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question