Skip to main content
Code Review

Return to Question

Rollback to Revision 1
Source Link
Mast
Mast
  • 13.9k
  • 12
  • 57
  • 128

UPDATE**

Based on Jerry Coffin's ans, I have made the changes except for using templates.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>


typedef std::vector<int>::iterator itr;

itr partition(itr left,itr right)
{

    itr i=left-1;

    itr it=left;

    while(it<right)
    {
        if(*it<*right)
        {

            using std::swap;
            
            std::advance(i,1);
            swap(*i,*it);
        }
        std::advance(it,1);
    }

    using std::swap;

    swap(*(i+1),*right); 
    std::advance(i,1);
    return i;
}

void quicksort(itr left, itr right)
{
    if(std::distance(left,right)>=2)
    {
        itr q=partition(left,right);
        quicksort(left,q-1);
        quicksort(q+1,right);
    }
}


int main()
{
    std::vector<int> v={6,10,4,5,3,9,13,8};

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

    quicksort(std::begin(v),std::end(v)-1);

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;


    return 0;
}

UPDATE**

Based on Jerry Coffin's ans, I have made the changes except for using templates.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>


typedef std::vector<int>::iterator itr;

itr partition(itr left,itr right)
{

    itr i=left-1;

    itr it=left;

    while(it<right)
    {
        if(*it<*right)
        {

            using std::swap;
            
            std::advance(i,1);
            swap(*i,*it);
        }
        std::advance(it,1);
    }

    using std::swap;

    swap(*(i+1),*right); 
    std::advance(i,1);
    return i;
}

void quicksort(itr left, itr right)
{
    if(std::distance(left,right)>=2)
    {
        itr q=partition(left,right);
        quicksort(left,q-1);
        quicksort(q+1,right);
    }
}


int main()
{
    std::vector<int> v={6,10,4,5,3,9,13,8};

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

    quicksort(std::begin(v),std::end(v)-1);

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;


    return 0;
}
Based on Jerry Coffin's ans, I have made the changes except for using templates, which I might change later.
Source Link
AlexanderTG
AlexanderTG
  • 95
  • 1
  • 5

UPDATE**

Based on Jerry Coffin's ans, I have made the changes except for using templates.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>


typedef std::vector<int>::iterator itr;

itr partition(itr left,itr right)
{

    itr i=left-1;

    itr it=left;

    while(it<right)
    {
        if(*it<*right)
        {

            using std::swap;
            
            std::advance(i,1);
            swap(*i,*it);
        }
        std::advance(it,1);
    }

    using std::swap;

    swap(*(i+1),*right); 
    std::advance(i,1);
    return i;
}

void quicksort(itr left, itr right)
{
    if(std::distance(left,right)>=2)
    {
        itr q=partition(left,right);
        quicksort(left,q-1);
        quicksort(q+1,right);
    }
}


int main()
{
    std::vector<int> v={6,10,4,5,3,9,13,8};

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

    quicksort(std::begin(v),std::end(v)-1);

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;


    return 0;
}

UPDATE**

Based on Jerry Coffin's ans, I have made the changes except for using templates.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>


typedef std::vector<int>::iterator itr;

itr partition(itr left,itr right)
{

    itr i=left-1;

    itr it=left;

    while(it<right)
    {
        if(*it<*right)
        {

            using std::swap;
            
            std::advance(i,1);
            swap(*i,*it);
        }
        std::advance(it,1);
    }

    using std::swap;

    swap(*(i+1),*right); 
    std::advance(i,1);
    return i;
}

void quicksort(itr left, itr right)
{
    if(std::distance(left,right)>=2)
    {
        itr q=partition(left,right);
        quicksort(left,q-1);
        quicksort(q+1,right);
    }
}


int main()
{
    std::vector<int> v={6,10,4,5,3,9,13,8};

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

    quicksort(std::begin(v),std::end(v)-1);

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;


    return 0;
}
Tweeted twitter.com/StackCodeReview/status/753459173086617600
Source Link
AlexanderTG
AlexanderTG
  • 95
  • 1
  • 5

QuickSort C++ Implementation using Iterators

I implemented quicksort using iterators. I am will be grateful, if someone can review my piece of code. BTW, I am just selecting the last element as the pivot (which I plan to randomize later) I am mainly looking for the following:

  1. Correctness of the Implementation

  2. Correct usage of iterators

  3. Basic coding style.

Although above are the key things I am looking for, please feel free to point out any mistakes. Thanks!!!

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>


typedef std::vector<int>::iterator itr;

itr partition(itr left,itr right)
{
    
    itr i=left-1;

    itr it=left;

    while(it<right)
    {
        if(*it<=*right)
        {
            ++i;
            std::swap(*i,*it);
        }
        ++it;
    }

    std::swap(*(i+1),*right); 
    return ++i;
}

void quicksort(std::vector<int>& v,itr left, itr right)
{
    if(std::distance(left,right)>=2)
    {
        itr q=partition(left,right);
        quicksort(v,left,q-1);
        quicksort(v,q+1,right);
    }
}


int main()
{
    std::vector<int> v={6,10,4,5,3,9,13,8};
    
    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

    quicksort(v,std::begin(v),std::end(v)-1);
    
    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

    
    return 0;
}