My sorting algorithm
-
I have a list of values in single dimensional vector/array as follow:
{([point0, value0], [point1, value1], ... , [pointx, valuex]), ([pointx+1, valuex+1], [pointx+2, valuex+2], ... , [pointy, valuey]), ([pointy+1, valuey+1], [pointy+2, valuey+2], ... , [pointz, valuez])}
[at first it may look like weird how this is single dimentional array; but yes it is ]
{point0,value0,point1,value1,...,pointx,valuex}
Here i know how values are structured in an input array. I just need to implement best sorting technique for this. Requirement is to sort each block based on point value(i.e. sort point0,value0 to pointx,valuex). I have information about number of elements in each block (which will be consistent for all blocks). I can simply write something like:
// blockSize is given // totalBlocks size is given // setOfValues is given (to be sorted)for(int blockIndex = 0 ; blockIndex < totalBlocks; ++blockIndex) { for(int i = blockSize * blockIndex; i < blockSize*(blockIndex + 1); i = i + 2) { for(int j = blockSize * blockIndex; j < blockSize*(blockIndex + 1); j = j + 2) { if (setOfValues[i] < setOfValues[j]) { int temp = setOfValues[i]; setOfValues[i] = setOfValues[j]; setOfValues[j] = temp; temp = setOfValues[i+1]; setOfValues[i+1] = setOfValues[j+1]; setOfValues[j+1] = temp; } } } }Time required for this algorithm is very huge: O(totalBlocks * blockSize^2) I am thinking of writing this in better way. Any help would be great! Thanks, AksharRoop -
I have a list of values in single dimensional vector/array as follow:
{([point0, value0], [point1, value1], ... , [pointx, valuex]), ([pointx+1, valuex+1], [pointx+2, valuex+2], ... , [pointy, valuey]), ([pointy+1, valuey+1], [pointy+2, valuey+2], ... , [pointz, valuez])}
[at first it may look like weird how this is single dimentional array; but yes it is ]
{point0,value0,point1,value1,...,pointx,valuex}
Here i know how values are structured in an input array. I just need to implement best sorting technique for this. Requirement is to sort each block based on point value(i.e. sort point0,value0 to pointx,valuex). I have information about number of elements in each block (which will be consistent for all blocks). I can simply write something like:
// blockSize is given // totalBlocks size is given // setOfValues is given (to be sorted)for(int blockIndex = 0 ; blockIndex < totalBlocks; ++blockIndex) { for(int i = blockSize * blockIndex; i < blockSize*(blockIndex + 1); i = i + 2) { for(int j = blockSize * blockIndex; j < blockSize*(blockIndex + 1); j = j + 2) { if (setOfValues[i] < setOfValues[j]) { int temp = setOfValues[i]; setOfValues[i] = setOfValues[j]; setOfValues[j] = temp; temp = setOfValues[i+1]; setOfValues[i+1] = setOfValues[j+1]; setOfValues[j+1] = temp; } } } }Time required for this algorithm is very huge: O(totalBlocks * blockSize^2) I am thinking of writing this in better way. Any help would be great! Thanks, AksharRoopThat is the worst sorting algorithm I've ever seen: you have chosen a poor data representation, picked the least sophisticated algorithm, and created a poor implementation. For a general overview on sorting algorithms, read either this[^] or Knuth's book on the subject. If your data were represented in a normal way (say an array of structs, each struct holding two ints), you could use the built-in Sort method which exists for arrays and all kinds of collections. Specifying the sorting criterium is explained here[^]. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
-
That is the worst sorting algorithm I've ever seen: you have chosen a poor data representation, picked the least sophisticated algorithm, and created a poor implementation. For a general overview on sorting algorithms, read either this[^] or Knuth's book on the subject. If your data were represented in a normal way (say an array of structs, each struct holding two ints), you could use the built-in Sort method which exists for arrays and all kinds of collections. Specifying the sorting criterium is explained here[^]. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
I know Luc. But I have don't have other choice. I can't change the representation of data because it is sent further for some processing.
-
I know Luc. But I have don't have other choice. I can't change the representation of data because it is sent further for some processing.
How big is the data set? You could change it into something more suitable before using a better sorting algorithm then change it back once sorted. I am not sure I get what your data is supposed to look like so it's difficult to suggest a sorting algorithm to work on it in its raw state.
-
How big is the data set? You could change it into something more suitable before using a better sorting algorithm then change it back once sorted. I am not sure I get what your data is supposed to look like so it's difficult to suggest a sorting algorithm to work on it in its raw state.
I don't think the data representation is the main problem here (unless they're large data structures) it's the choice of algorithm. As already mentioned, it's probably the least efficient one possible...
Days spent at sea are not deducted from one's alloted span - Phoenician proverb
-
I don't think the data representation is the main problem here (unless they're large data structures) it's the choice of algorithm. As already mentioned, it's probably the least efficient one possible...
Days spent at sea are not deducted from one's alloted span - Phoenician proverb
I know - I just think it be easier for him to put the data into something more usable then sort on that using an appropriate algorithm out of the box rather than fiddling with an algorithm to use his data structure.