Question

This is a c++ code

/**   
Write a function sort that sorts the elements of a std::list
without using std::list::sort or std::vector.
Instead use list<int>::iterator(s)
*/
using namespace std;
#include <iostream>
#include <iomanip>
#include <string>
#include <list>
void print_forward (list<int>& l)
{
// Print forward
for (auto value : l)
{
cout << value << ' ';
}
cout << endl;
}
void sort(list<int>& l)
{

write code here -- do not use the built-in list sort function

}
int main ()
{
list<int> l { 2, 24, 3, -4, 32, -22};
print_forward(l);
sort(l);
print_forward(l);
return 0;
}

Answer 1

Hey, it's a very good exercise of using iterators and sorting without using any extra libraries.

For understanding purpose, I had divided the solution into parts. So, let's start:

PART ONE: REQUIREMENTS:

The major challenge is that we need to sort the list but without using the standard sort of List or Vector. Now, we have to use a list iterator and we need to sort using that only.

PART TWO: WRITING SORT() METHOD:

1. Writing out sort() Method:

Taking a variable to check whether a list is sorted or not. Considering initially the list will be not sorted and hence initializing to false.

2. If not sorted, perform operations to sort it and check whether the list is sorted or not.

Take two lists <int> iterators for accessing the elements of the list.

The iterator front will access the first and front_advanced will access the character next to it.

3. Applying Bubble sort logic:

We have implemented bubble sort logic and updated the variable isSorted. When the swappings are not required, it means the list is sorted and the operation will complete.

4. Full Code:

PART THREE: FULL CODE IMPLEMENTATION IN CODE FORMAT:

*****************************CODE*************************

 void sort(list<int>& l) {       //A Variable to check whether list is sorted or not.    bool isSorted = false; while (!isSorted) {      isSorted = true;        //Iterator for accessing elements of list       list <int>::iterator front;       list <int>::iterator front_advanced;              //Applying Basic Sorting algorithm on these iterators   for (front = l.begin(), front_advanced = front++; front_advanced != l.end(); ++front_advanced, ++front)         {        //Checking each element with the element next to it            if ((*front_advanced) > (*front)) { //This means List is not sorted and swapping will take place. isSorted = false; std::iter_swap(front_advanced, front); }         }        } }

*************************************************CODE*******************************************

========================================================================

void sort(list<int>& l)
{
   //A Variable to check whether list is sorted or not.
   bool isSorted = false;
while (!isSorted)
{
   isSorted = true;

   //Iterator for accessing elements of list
   list <int>::iterator front;
   list <int>::iterator front_advanced;
  
   //Applying Basic Sorting algorithm on these iterators
   for (front = l.begin(), front_advanced = front++; front_advanced != l.end(); ++front_advanced, ++front)  
   {
   //Checking each element with the element next to it
       if ((*front_advanced) > (*front))
{
//This means List is not sorted and swapping will take place.
isSorted = false;
  
std::iter_swap(front_advanced, front);
  
}
  
   }
  
}
}

========================================================================

Thanks and All the best.

Happy Coding

Please don't forget to thumbs up if it really helped you.

Keep learning and Keep Chegging :)