What is a fast sorting algorithm?

[Shatronics]

Hello,
I have had no education in algorithm. I have written an algorithm that can sort 2200 song titles (my music collection) alphabetically in about 0,3 seconds.
Is that a fast algorithm? I would just like to hear from some of the pro's how fast a good sorting algorithm in my case would be?

Regards,

Simon H.A.

[therockon7throw]

http://en.wikipedia.org/wiki/Sorting_algorithm

[Shatronics]

I have been on that place before, but they only talk about a speed of for example O(n log n). I don't know how to calculate those theoretically speeds. I'm thinking of the practical speed. Like in how many milliseconds it takes to order a specific array or so.

Regards,

Simon H.A.

[Peter87]

0,3 seconds doesn't say much on it's own. You have to compare it with some other algorithm using the same computer, same compiler etc. Some algorithms are better if the list is almost sorted already.

C++ has a build in sorting function called std::sort in the <algorithm> header. The exact algorithm used by std::sort depends on what standard library implementation you use.

[Shatronics]

Okay. I might try some different algorithms and see the results. I think 0,3s for a pretty scrambled list with a 1,8GHz atom processor is pretty good ;).

Regards,

Simon H.A.

[ReedTompkins]

Hi Simon,

Why not share your code/algorithm with us? It'd be interesting to compare your solution to existing sorting algorithms.

[Galik]

Compare your algorithm with std::sort(). That should give you an idea on how fast it is.

http://cplusplus.com/reference/algorithm/sort/

[Shatronics]

Sure thing. My sorting algorithm is made for sorting song titles. So I don't think it would be very fast with other types of data.
The structure that holds the data has a two dimensional TCHAR array. First I create an index holding the first two letters. To avoid problems for example if there is no characters I have made sure that there are at least two NULL characters since it's easier that way.

Also note that you should ignore swapping of SHOW_LIST[LIST].SELECT[PLACE] since it has no relevance for the sorting part.

First I set in what order the list should be ordered (controlled by a variable):

			BOOL SORT = 0;

			//Sets whether to sort from first to last or last to first.
			if(mode == 1)
				SORT = 1;
			else
				SORT = -1;

Then the index list is created. INDEX keeps track of the playlists numbers that are referenced to the library list.
FIRST_CHAR keeps track of the two first letters in the list for compare.

			//Creates index (used for ordering the first two letter).
			DWORD* INDEX = new DWORD[SHOW_LIST[LIST].LIST_SIZE+2];
			//Creates holder for the first two letters (first letter * 0x10000 + second letter).
			DWORD* FIRST_CHAR = new DWORD[SHOW_LIST[LIST].LIST_SIZE+2];

			TCHAR convert[2];

			//Loads the list to the index and converts all the first chars to uppercase.
			for(int i = 0; i < SHOW_LIST[LIST].LIST_SIZE; i++) {
				INDEX[i] = SHOW_LIST[LIST].LIST[i];

				//Gets first two letters.
				convert[0] = LIB_LIST.TITLE[INDEX[i]][0];
				convert[1] = LIB_LIST.TITLE[INDEX[i]][1];

				//Only convert if needed. (Not upper and part of unicode).
				if(_istlower(convert[0]) && _istascii(convert[0]))
					convert[0] = _toupper(convert[0]);
				if(_istlower(convert[1]) && _istascii(convert[1]))
					convert[1] = _toupper(convert[1]);

				//Adds to the list.
				FIRST_CHAR[INDEX[i]] = convert[0]*0x10000 + convert[1];
			}

Then I sort the index list using a simple selection sort. It's a very slow algorithm but it was easy to use and since we're only comparing single DWORD's it take no time:

			DWORD PLACE = 0;
			DWORD POSITION = 0;
			DWORD MAX_POS = 0;

			//Sorts the first two letter.
			do {

				PLACE = POSITION;

				//Finds the smallest/largest.
				for(int i = POSITION; i < (SHOW_LIST[LIST].LIST_SIZE-1); i++) {
					//Sort either after smallest or largest.
					if(SORT == 1) {
						if(FIRST_CHAR[INDEX[PLACE]] > FIRST_CHAR[INDEX[i+1]])
							PLACE = i+1;
					}
					if(SORT == -1) {
						if(FIRST_CHAR[INDEX[PLACE]] < FIRST_CHAR[INDEX[i+1]])
							PLACE = i+1;
					}
				}

				//Swaps.
				Swap(SHOW_LIST[LIST].SELECT[PLACE], SHOW_LIST[LIST].SELECT[POSITION]);
				Swap(INDEX[PLACE], INDEX[POSITION]);
				POSITION++;

			}while(POSITION < (SHOW_LIST[LIST].LIST_SIZE-1));

Then I've have written a function that compares two strings and returns whether the first should be last, is equal or should be first.

//Checks which string should come first. Returns -1 if str1 < str2. Returns 0 if str1 == str2. Returns 1 if str1 > str2.
BOOL song_list::CheckString(TCHAR* str1, TCHAR* str2) {

	//Gets the smallest length.
	DWORD l1 = _tcslen(str1);
	DWORD l2 = _tcslen(str2);
	
	DWORD length;

	length = l2;

	if(l1 < l2)
		length = l1;

	//Create strings for holding the uppercase string.
	TCHAR* string1 = new TCHAR[l1+2];
	TCHAR* string2 = new TCHAR[l2+2];

	//Adds the null character.
	string1[l1] = NULL;
	string2[l2] = NULL;

	//Converts string to uppercase.
	for(int i = 0; i < l1; i++) {

		string1[i] = str1[i];

		if(_istlower(str1[i]) && _istascii(str1[i]))
			string1[i] = _toupper(str1[i]);
	}
	//Converts string to uppercase.
	for(int i = 0; i < l2; i++) {

		string2[i] = str2[i];

		if(_istlower(str2[i]) && _istascii(str2[i]))
			string2[i] = _toupper(str2[i]);
	}

	BOOL LARGER = 0;

	//Checks if the first string is larger than the last string.
	for(int i = 0; i < length; i++) {
		//Letter larger than the second string? Set return value and break.
		if(string1[i] > string2[i]) {
			LARGER = 1;
			break;
		}
		//Is it smaller than the second string? Set return value and break.
		if(string1[i] < string2[i]) {
			LARGER = -1;
			break;
		}
	}

	//Are they equal but one of the strings are longer than the other?
	if(LARGER == 0) {
		if(l2 < l1)
			LARGER = TRUE;
	}

	//Deletes strings.
	delete [] string1;
	delete [] string2;

	//Returns result.
	return LARGER;
}

Now I sort the whole list. First I get a part of the list with the same two letters and then I sort that list using simple bubble sort. (Yes it is slow but improves can be made later on).

			POSITION = 0;
			
			//Sorts the list by splitting the list up in parts who has the same two letters.
			do {

				MAX_POS = POSITION;

				//Gets how many characters are matching.
				for(int i = POSITION; i < SHOW_LIST[LIST].LIST_SIZE-1; i++) {

					MAX_POS++;

					//No more matches? We've found how large the list is.
					if(FIRST_CHAR[INDEX[i]] != FIRST_CHAR[INDEX[i+1]])
						break;
				}

				BOOL DONE = TRUE;

				//Orders the part of the list via bubble sort.
				do {

					DONE = TRUE;

					//Goes through the list.
					for(int i = POSITION; i < MAX_POS; i++) {
						//Is there a need for swapping values?
						if(CheckString(LIB_LIST.TITLE[INDEX[i]], LIB_LIST.TITLE[INDEX[i+1]]) == SORT) {
							//Swaps values.
							Swap(SHOW_LIST[LIST].SELECT[i], SHOW_LIST[LIST].SELECT[i+1]);
							Swap(INDEX[i], INDEX[i+1]);
							DONE = FALSE;
						}
					}

				}while(DONE != TRUE);

				//Goes to next part.
				POSITION = MAX_POS;

			//Sorts until end is reached-.
			}while(MAX_POS != SHOW_LIST[LIST].LIST_SIZE-1);

The list is loaded to the playlist and we get rid of the pointers.

			//Loads the new ordered list.
			for(int i = 0; i < SHOW_LIST[LIST].LIST_SIZE; i++)
				SHOW_LIST[LIST].LIST[i] = INDEX[i];

			delete [] INDEX;
			delete [] FIRST_CHAR;

This code is improved compared to what I wrote before. It sorts the 2200 titles on an average of around 0,15 s with a 1,8 GHz atom processor.
I guess the speed would be even faster with better sorting algorithms but I won't improve this code for now since it's fast enough right now.
This is only fast with song titles since song titles are very random in their names.
A simple bubble sort that uses the CheckString funtion to compare takes over 8 seconds to sort compared to this sorting algorithm that still uses the same sorting type.
Hope you find this post interesting.

Regards,

Simon H.A.

[cire]

I can understand if you're doing this just for the sake of learning, but if you're concerned about speed, used std::sort. It's correct and has the benefit of experience behind it.

On my machine, it sorts ~10000 song titles in .005s. .035s if I also time the code to read the song titles from a file into a vector and shuffle them.

[Shatronics]

Okay, I can see that it's not so fast at all. But yes, it's mostly for learning. It's fast enough for my needs so I will still use it.
I will keep std::sort in mind when I need pure speed.

Regards,

Simon H.A.

[Shatronics]

Just a little update. I read on how the merge sorting algorithm works and I wrote a code based on that. Now my time is 0,05s for sorting 2200 strings including loading the data ; )

Regards,

Simon H.A.