can some one help me with this question..
"The name of students are sorted in an array of strings.Write a program to prepare alphabetically sorted listing of names.."
Sreya_1
Edited
by Sreya_1: insufficient characters
- 5 Contributors
- forum4 Replies
- 33 Views
- 4 Years Discussion Span
- comment Latest Post by Banfa
Ancient Dragon 5,243
There are lots of sorting algorithms, c++ even has one. Are you allowed to use the standard c++ std::sort function? If not, then probably the simplest one to code is the bubble sort. The bubble sort is among the slowest of the sort algorithms, but for small sets of data and for data that's already almost sorted it is ok.
Schol-R-LEA 1,087
I would actually recommend Gnome Sort, as it is a little smaller marginally faster than Bubble Sort, though it is a little harder to understand. The main reason bubble sort is such a topic of fascination for computer scientists is that it appears to be the 'naive' algorithm for sorting, that is to say, it is the one which most people, if asked to sort a list by computer and not given any algorithms to follow, will come up with on their own.
FYI, in case you are wondering, in practice there are no ideal sorting methods that work fastest for all input. Every practical sorting algorithm is sensitive to the order of the original unsorted list, and even where there is a clear difference in the optimal performance (i.e., O(n log n) for the average case of quicksort versus O(n^2) for Bubblesort), the theoretically slower sorting algorithm may perform better in practice, either because of the order of the input, or because the overhead is smaller for smaller inputs.
In theory, the worst 'practical' sorting algorithm is Bogosort, which consists of repeatedly shuffling the list and testing to see if it has randomly entered a sorted state. The average performance for this is O((n-1) n! (that is to say, the number of items in the list minus one, times the product of every number between 1 and the size of the list - a very, very bad performance); the worst case is unbounded (that is to say, it is not guaranteed to ever find a sorted list). Ironically, the theorectically best performing sort is the parallel quantum-mechanical variant of Bogosort, in which you perform the sort in n parallel universes and select the one in which it is sorted. The theoretical time overhead is O(1); providing the resources need to perform this task are left as an exercise for the reader.
Edited
by Schol-R-LEA
David W 131
You may like to see this ref link to the sorts that already come in the C++ library
The example at the above link is for sorting a vector of integers.
Below is an example of sorting a C++ STL list of C++ strings:
// sort_list_of_string.cpp //
#include <iostream>
//#include <algorithm> // not needed for list sort
#include <string>
#include <list>
using namespace std;
ostream& operator << (ostream& os, const list< string >& ml )
{
list< string >::const_iterator it;
for( it = ml.begin() ; it != ml.end() ; ++ it )
os << *it << ' ';
return os;
}
bool myLenCmp( const string& a, const string& b )
{
return a.size() < b.size() ;
}
int main ()
{
list< string > myList; // construct an empty list ...
myList.push_back( "Joe" );
myList.push_back( "Sue" );
myList.push_back( "Annie" );
myList.push_back( "Zoe" );
myList.push_back( "Lynne" );
cout << "myList unsorted: \n" << myList << endl;
// call list sort and compare strings in dictionary order
myList.sort();
cout << "myList dictionary sorted: \n" << myList << endl;
// call list sort and compare strings in len order
myList.sort( myLenCmp );
cout << "myList length sorted: \n" << myList << endl;
return 0;
}
Edited
by David W: cleaned up comments
Banfa 597
Personally I would recomend the Comb Sort algorithm rather than bubble sort which tends to be more efficient in the average case than Bubble sort but isn't that much more complex.
I have used it on a microprocessor (PIC) implementation with limited flash and ram (the list being sorted took around 75% of the available ram).