Radix Sort and Usage of STL Sort Algorithm

Prerequisites, Goals, and Outcomes

Prerequisites: Students should have mastered the following prerequisite skills.

• Radix Sort - Knowledge of the radix sort algorithm
• C++ STL – Basic knowledge of the usage of C++ STL
• C++ function pointer – Basic Knowledge of C++ function pointer

Goals: This assignment is designed to reinforce the student's understanding of radix sort with time complexity . And also as the final assignment of sort algorithm, the students should master the usage of STL sort algorithm.

Outcomes: Students successfully completing this assignment would master the following outcomes.

• Understand the linear time sort algorithm
• Master the usage of STL sort algorithm

Background

Radix Sort

Radix sort follows the non-intuitive order of sorting on the least significant feature first and recombining all the lists immediately after each completed splitting.  For instance if keys were 5 digit numbers, the sort could first be on the 1's digit, then the 10's digit, ... and finally the most significant digit, the 10,000's digit.  The only requirement to have this work is the splitting and recombining operations make keys that go in the same bucket end up in the same relative order as the started (i.e. be stable). 

Do small example: for simplicity only 3 possible values in each place

Initial data	first pass	second pass	last pass	combined
123	231	111	111	111
222	111	312	113	113
312	121	113	121	121
113	+	+	123	123
231	222	121	+	222
111	312	222	222	231
333	+	123	231	312
121	123	+	+	333
	113	231	312
	333	333	333

 

STL Sort Algorithm

The header <algorithm> defines a collection of functions especially designed to be used on ranges of elements.

A range is any sequence of objects that can be accessed through iterators or pointers, such as an array or an instance of some of the STL containers. Notice though, that algorithms operate through iterators directly on the values, not affecting in any way the structure of any possible container (it never affects the size or storage allocation of the container).

There are five sort algorithms in STL, and the function prototypes are listed below:

sort	Sort elements in range (function template)
stable_sort	Sort elements preserving order of equivalents (function template)
partial_sort	Partially Sort elements in range (function template)
partial_sort_copy	Copy and partially sort range (function template)
nth_element	Sort element in range (function template)

 

 

 

Sort

template <class RandomAccessIterator>

  void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

  void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

Description

Sorts the elements in the range [first,last) into ascending order.The elements are compared using operator< for the first version, and comp for the second.Elements that would compare equal to each other are not guaranteed to keep their original relative order.

Parameters

first, last

Random-Access iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

comp

Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

stable_sort

template <class RandomAccessIterator>

  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,

                     Compare comp );

Description

Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort grants that the relative order of the elements with equivalent values is preserved.The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last

Random-Access iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

comp

Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

partial_sort

template <class RandomAccessIterator>

  void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,

                      RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

  void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,

                      RandomAccessIterator last, Compare comp );

Description

Rearranges the elements in the range [first,last), in such a way that the subrange [first,middle) contains the smallest elements of the entire range sorted in ascending order, and the subrange [middle,end) contains the remaining elements without any specific order.

The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last

Random-Access iterators to the initial and final positions of the sequence to be used. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Notice that in this function, these are not consecutive parameters, but the first and third ones.

middle

Random-Access iterator pointing to the element within the range [first,last) that is used as the upper boundary of the elements that are completely sorted.

comp

Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

partial_sort_copy

template <class InputIterator, class RandomAccessIterator>

  RandomAccessIterator

    partial_sort_copy ( InputIterator first,InputIterator last,

                        RandomAccessIterator result_first,

                        RandomAccessIterator result_last );

template <class InputIterator, class RandomAccessIterator, class Compare>

  RandomAccessIterator

    partial_sort_copy ( InputIterator first,InputIterator last,

                        RandomAccessIterator result_first,

                        RandomAccessIterator result_last, Compare comp );

Description

Copies the smallest elements in the range [first,last) to [result_first,result_last), sorting the elements copied. The amount of elements copied is (result_last-result_first) (unless this is more than the amount of elements in [first,last)). [first,last) remains unmodified.

The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last

Input iterators to the initial and final positions of the sequence to copy from. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

result_first, result_last

Random-Access iterators to the initial and final positions of the destination sequence. The range used is [result_first,result_last).

comp

Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

nth_element

template <class RandomAccessIterator>

  void nth_element ( RandomAccessIterator first, RandomAccessIterator nth,

                     RandomAccessIterator last );

template <class RandomAccessIterator, class Comapre>

  void nth_element ( RandomAccessIterator first, RandomAccessIterator nth,

                     RandomAccessIterator last, Compare comp );

Description

Rearranges the elements in the range [first,last), in such a way that the element at the resulting nth position is the element that would be in that position in a sorted sequence, with all the elements preceding it being smaller and all the elements following it greater than it. Neither the elements preceding it nor the elements following it are granted to be ordered.

The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last

Random-Access iterators to the initial and final positions of the sequence to be used. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Notice that in this function, these are not consecutive parameters, but the first and third ones.

nth

Random-Access iterator pointing to the location within the range [first,last) that will have the sorted element.

comp

Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

 

Task

Your task this time is composed of two independent parts.

Firstly, you should implement the radix sort algorithm, and your program is supposed to sort a sequence of English words. For simplicity, all the English words only contain 3 capital letters. For example, you can test your program on the sequence {COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX}.

Secondly, a very simple student class is given below. It has two member variables. Your program is supposed to sort a list of students with the STL sort functions. And you can add some other member function as you need. Then you are supposed to write a program to use the entire STL sort algorithms listed above. You can choose to store a collection of students in an array or some containers in STL, whichever you like.

class student{

 public:

               string stu_num; // The number of a student, which is unique for each student.

               string stu_name;//The name of a student.

…

};

参考代码：

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;
class student{
 public:
 string stu_num; // The number of a student, which is unique for each student.
 string stu_name;//The name of a student.
 bool operator<(student t)const
 {
  if (stu_num.length()<t.stu_num.length())
   return true;
        if (stu_num.length()==t.stu_num.length())
            return (stu_num<t.stu_num);
  return false;
 }
};

void RadixSort(string Array[], int n,int d, int r)
{
    string *TempArray =new string [n]; //辅助排序的临时数组
 int* count= new int[r];    //计数器，Count[i] 存储了第i个桶中的记录数
 int i,j,k;
 int Radix=d-1;         //用来取Array[j]的第i位排序码
 for (i=1; i<=d; i++)    // 分别对第i个排序码进行分配
 {
  for (j=0; j<r; j++)    // 初始计数器均为0
   count[j] = 0;   
   for (j=0; j<n; j++)   // 统计每个桶中的记录数
   {
   k=(Array[j][Radix]);  //取Array[j]的第i位排序码
   count[k]++;     //相应计数器加1
   }
   
  for (j=1; j<r; j++)    // 将TempArray中的位置依次分配给r个桶
   count[j] = count[j-1] + count[j];
  for (j=n-1; j>=0; j--)   // 将所有桶中的记录依次收集到TempArray中
  {
   k=(Array[j][Radix]);  //取Array[j]的第i位排序码
   count[k]--;     //从第k个桶中取出一个记录，计数器减1
   TempArray[count[k]] = Array[j];
  }
  for (j=0; j<n; j++)    // 将临时数组中的内容复制到Array中
   Array[j] = TempArray[j];        
  Radix-=1;
 }
 delete[]TempArray;
 delete[]count;
}
void main()
{  
 int i,n;
 //排序
    string a[16]={"COW","DOG","SEA","RUG","ROW","MOB","BOX","TAB","BAR","EAR","TAR","DIG","BIG","TEA","NOW","FOX"};
    RadixSort(a,16,3,256);
    cout<<"基数排序结果为"<<endl;
    for(i=0;i<16;i++)
        cout<<a[i]<<" ";
    cout<<endl;
 student s[20];
 student t[20];
 student d[20];
 student f[20];
 student w[20];
 student q[20];
 cout<<"input the number of student"<<endl;
 cin>>n;
 cout<<"请输入学生学号及姓名："<<endl;
 for(i=0;i<n;i++)
  cin>>s[i].stu_num>>s[i].stu_name;
 cout<<"Before arrangement"<<endl;
 for(i=0;i<n;i++)
    {
        cout<<s[i].stu_num<<" "<<s[i].stu_name<<" ";
    }
 cout<<endl;
    cout<<endl;
 cout<<"-------------------sort---------------------"<<endl;
 for(i=0;i<n;i++)
    {
        t[i]=s[i];
    }
    sort(t,t+n);
 for(i=0;i<n;i++)
    {
        cout<<t[i].stu_num<<" "<<t[i].stu_name<<" ";
    }
 cout<<endl;
    cout<<endl;
 cout<<"--------------------stable_sort------------------"<<endl;
 for(i=0;i<n;i++)
    {
        d[i]=s[i];
    }
    stable_sort(d,d+n);
 for(i=0;i<n;i++)
    {
        cout<<d[i].stu_num<<" "<<d[i].stu_name<<" ";
    }
 cout<<endl;
    cout<<endl;
 cout<<"-------------------partial_sort-------------------"<<endl;
 partial_sort(t,t+3,t+n);
 cout<<"first four arrange result:"<<endl;
 for(i=0;i<4;i++)
    {
        cout<<t[i].stu_num<<" "<<t[i].stu_name<<" ";
    }
 cout<<endl;
    cout<<endl;
 cout<<"--------------------partial_sort_copy--------------------"<<endl;
     partial_sort_copy(d,d+n,w+2,w+7);
  cout<<"arrange from 3nd to 8th"<<endl;
  for(i=2;i<7;i++)
  {
   cout<<w[i].stu_num<<" "<<w[i].stu_name<<" ";
    }
 cout<<endl;
    cout<<endl;
  cout<<"-------------------nth_element------------------------"<<endl;
  for(i=0;i<n;i++)
  {
   q[i]=s[i];
    }
  cout<<"the 6th arrangement result:"<<endl;
     nth_element(q,q+5,q+n);
   
   cout<<q[5].stu_num<<" "<<q[5].stu_name<<" ";
   
   cout<<endl;

}