Sort Functions
-
Hi all, I have a working program that reads stocks symbols and values from a text file and do some operations on the data, and then it outputs the the data as two reports. The first report is sorted by stock symbols, and the other report is sorted by percent gain/loss. I'm having difficulties understating how these sort functions are doing the comparisons.. Can you guys provide some explanation please?
//sorts the stocks naturally (stock symbol)
template<class elemType>
void listType<elemType>::sort(){
int i, j;
int min;
elemType temp;for (i = 0; i <length; i++){ min = i; for (j = i + 1; j < length; ++j) if (list\[j\] < list\[min\]) min = j; temp = list\[i\]; list\[i\] = list\[min\]; list\[min\] = temp; }}
//sorts the stocks by percent gain/loss
void stockListType::sortByGain(){
int i, j;
int temp;
indexByGain = new int[length];//Pre-populate the index array for(int c = 0; c < length; c++){ indexByGain\[c\] = c; } //Sort by the percentage change for (i = 0; i <length; i++){ for (j = i + 1; j < length; j++){ if (list\[indexByGain\[j\]\].getPercentChange() > list\[indexByGain\[i\]\].getPercentChange()){ temp = indexByGain\[i\]; indexByGain\[i\] = indexByGain\[j\]; indexByGain\[j\] = temp; } } }}
The algorithm is something like this - 1. Take the first element in the array. 2. Compare with the rest of the elements below it to check if there is a lesser value. 3. If there is a lesser value, swap the elements. 4. Take the next element in the array. 5. Go to step 2. The
std::sortfunction would be more efficient if you can use it.«_Superman_» _I love work. It gives me something to do between weekends.
-
Hi all, I have a working program that reads stocks symbols and values from a text file and do some operations on the data, and then it outputs the the data as two reports. The first report is sorted by stock symbols, and the other report is sorted by percent gain/loss. I'm having difficulties understating how these sort functions are doing the comparisons.. Can you guys provide some explanation please?
//sorts the stocks naturally (stock symbol)
template<class elemType>
void listType<elemType>::sort(){
int i, j;
int min;
elemType temp;for (i = 0; i <length; i++){ min = i; for (j = i + 1; j < length; ++j) if (list\[j\] < list\[min\]) min = j; temp = list\[i\]; list\[i\] = list\[min\]; list\[min\] = temp; }}
//sorts the stocks by percent gain/loss
void stockListType::sortByGain(){
int i, j;
int temp;
indexByGain = new int[length];//Pre-populate the index array for(int c = 0; c < length; c++){ indexByGain\[c\] = c; } //Sort by the percentage change for (i = 0; i <length; i++){ for (j = i + 1; j < length; j++){ if (list\[indexByGain\[j\]\].getPercentChange() > list\[indexByGain\[i\]\].getPercentChange()){ temp = indexByGain\[i\]; indexByGain\[i\] = indexByGain\[j\]; indexByGain\[j\] = temp; } } }}
Babylon Lion wrote:
Can you guys provide some explanation please?
See here.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Man who follows car will be exhausted." - Confucius
-
Hi all, I have a working program that reads stocks symbols and values from a text file and do some operations on the data, and then it outputs the the data as two reports. The first report is sorted by stock symbols, and the other report is sorted by percent gain/loss. I'm having difficulties understating how these sort functions are doing the comparisons.. Can you guys provide some explanation please?
//sorts the stocks naturally (stock symbol)
template<class elemType>
void listType<elemType>::sort(){
int i, j;
int min;
elemType temp;for (i = 0; i <length; i++){ min = i; for (j = i + 1; j < length; ++j) if (list\[j\] < list\[min\]) min = j; temp = list\[i\]; list\[i\] = list\[min\]; list\[min\] = temp; }}
//sorts the stocks by percent gain/loss
void stockListType::sortByGain(){
int i, j;
int temp;
indexByGain = new int[length];//Pre-populate the index array for(int c = 0; c < length; c++){ indexByGain\[c\] = c; } //Sort by the percentage change for (i = 0; i <length; i++){ for (j = i + 1; j < length; j++){ if (list\[indexByGain\[j\]\].getPercentChange() > list\[indexByGain\[i\]\].getPercentChange()){ temp = indexByGain\[i\]; indexByGain\[i\] = indexByGain\[j\]; indexByGain\[j\] = temp; } } }}
As already suggested, that's the famous bubble sort (the most intuitive one: lower elements comes up). You may notice that
for (i = 0; i < length; i++)
could be replaced by
for (i = 0; i < length-1; i++)
:)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
As already suggested, that's the famous bubble sort (the most intuitive one: lower elements comes up). You may notice that
for (i = 0; i < length; i++)
could be replaced by
for (i = 0; i < length-1; i++)
:)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]So whenever a comparison like that is required, a bubble function is used, right?
-
So whenever a comparison like that is required, a bubble function is used, right?
There's no bubble function, actually. From Wikipedia[^] : "The algorithm gets its name from the way smaller elements 'bubble' to the top of the list". :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
Babylon Lion wrote:
Can you guys provide some explanation please?
See here.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Man who follows car will be exhausted." - Confucius
thank you :)
-
Babylon Lion wrote:
Can you guys provide some explanation please?
See here.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Man who follows car will be exhausted." - Confucius
I may have gone mad but this is a selection sort surely... Edit: my hesitation is due to the fact that (as pointed out above) you never see these sorts of sorts in the wild because there are much better sorts of sorts.
-
So whenever a comparison like that is required, a bubble function is used, right?
Babylon Lion wrote:
whenever a comparison like that is required, a bubble function is used, right?
The bubble sort is not the most efficient method of sorting data as there is a lot of swapping going on. In a short list (array) it works fine and is quicker and easier to code. With a shorter list there really isn't too much loss of efficiency. This site provides a good visual demonstration of the different types of sorts http://www.sorting-algorithms.com/[^] As Superman states use the
std::sortfunction if you can, although learning sort algorithms can be useful. Good luck!It was broke, so I fixed it.
-
Hi all, I have a working program that reads stocks symbols and values from a text file and do some operations on the data, and then it outputs the the data as two reports. The first report is sorted by stock symbols, and the other report is sorted by percent gain/loss. I'm having difficulties understating how these sort functions are doing the comparisons.. Can you guys provide some explanation please?
//sorts the stocks naturally (stock symbol)
template<class elemType>
void listType<elemType>::sort(){
int i, j;
int min;
elemType temp;for (i = 0; i <length; i++){ min = i; for (j = i + 1; j < length; ++j) if (list\[j\] < list\[min\]) min = j; temp = list\[i\]; list\[i\] = list\[min\]; list\[min\] = temp; }}
//sorts the stocks by percent gain/loss
void stockListType::sortByGain(){
int i, j;
int temp;
indexByGain = new int[length];//Pre-populate the index array for(int c = 0; c < length; c++){ indexByGain\[c\] = c; } //Sort by the percentage change for (i = 0; i <length; i++){ for (j = i + 1; j < length; j++){ if (list\[indexByGain\[j\]\].getPercentChange() > list\[indexByGain\[i\]\].getPercentChange()){ temp = indexByGain\[i\]; indexByGain\[i\] = indexByGain\[j\]; indexByGain\[j\] = temp; } } }}
QuickSort is infinitely faster than a bubble sort. I use it exclusively. It recursively breaks the list up into smaller and smaller pieces. The resulting time-to-sort relative to the length of the list is linear instead of exponential. Found this from Googling QUICKSORT. There are many other sources of info out there.
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}int choose_pivot(int i,int j )
{
return((i+j) /2);
}void quicksort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j--;
if( i < j)
swap(&list[i],&list[j]);
}
// swap two elements
swap(&list[m],&list[j]);
// recursively sort the lesser list
quicksort(list,m,j-1);
quicksort(list,j+1,n);
}
} -
QuickSort is infinitely faster than a bubble sort. I use it exclusively. It recursively breaks the list up into smaller and smaller pieces. The resulting time-to-sort relative to the length of the list is linear instead of exponential. Found this from Googling QUICKSORT. There are many other sources of info out there.
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}int choose_pivot(int i,int j )
{
return((i+j) /2);
}void quicksort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j--;
if( i < j)
swap(&list[i],&list[j]);
}
// swap two elements
swap(&list[m],&list[j]);
// recursively sort the lesser list
quicksort(list,m,j-1);
quicksort(list,j+1,n);
}
}danataylor wrote:
QuickSort is infinitely faster than a bubble sort
In general it is; but in its worse case, it's as bad as other sorts.
Watched code never compiles.
-
QuickSort is infinitely faster than a bubble sort. I use it exclusively. It recursively breaks the list up into smaller and smaller pieces. The resulting time-to-sort relative to the length of the list is linear instead of exponential. Found this from Googling QUICKSORT. There are many other sources of info out there.
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}int choose_pivot(int i,int j )
{
return((i+j) /2);
}void quicksort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j--;
if( i < j)
swap(&list[i],&list[j]);
}
// swap two elements
swap(&list[m],&list[j]);
// recursively sort the lesser list
quicksort(list,m,j-1);
quicksort(list,j+1,n);
}
}QuickSort isn't "infinitely" faster than a bubble sort. Its efficiency depends on the choice of pivot, and its performance can be sensitive to the initial order (as explained in that article). For small arrays a bubble sort can be faster! It's usually better to use a built-in sort because that will have had time spent on it to reduce such problems.
-
QuickSort is infinitely faster than a bubble sort. I use it exclusively. It recursively breaks the list up into smaller and smaller pieces. The resulting time-to-sort relative to the length of the list is linear instead of exponential. Found this from Googling QUICKSORT. There are many other sources of info out there.
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}int choose_pivot(int i,int j )
{
return((i+j) /2);
}void quicksort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j--;
if( i < j)
swap(&list[i],&list[j]);
}
// swap two elements
swap(&list[m],&list[j]);
// recursively sort the lesser list
quicksort(list,m,j-1);
quicksort(list,j+1,n);
}
}I would recommend the use of the functions from the standard library like
qsortorqsort_s.«_Superman_» _I love work. It gives me something to do between weekends.
-
Hi all, I have a working program that reads stocks symbols and values from a text file and do some operations on the data, and then it outputs the the data as two reports. The first report is sorted by stock symbols, and the other report is sorted by percent gain/loss. I'm having difficulties understating how these sort functions are doing the comparisons.. Can you guys provide some explanation please?
//sorts the stocks naturally (stock symbol)
template<class elemType>
void listType<elemType>::sort(){
int i, j;
int min;
elemType temp;for (i = 0; i <length; i++){ min = i; for (j = i + 1; j < length; ++j) if (list\[j\] < list\[min\]) min = j; temp = list\[i\]; list\[i\] = list\[min\]; list\[min\] = temp; }}
//sorts the stocks by percent gain/loss
void stockListType::sortByGain(){
int i, j;
int temp;
indexByGain = new int[length];//Pre-populate the index array for(int c = 0; c < length; c++){ indexByGain\[c\] = c; } //Sort by the percentage change for (i = 0; i <length; i++){ for (j = i + 1; j < length; j++){ if (list\[indexByGain\[j\]\].getPercentChange() > list\[indexByGain\[i\]\].getPercentChange()){ temp = indexByGain\[i\]; indexByGain\[i\] = indexByGain\[j\]; indexByGain\[j\] = temp; } } }}
Interesting sort functions. The first function can be associated to a "bubble sort" except nothing is "bubbling up" in the list array. The inner loop is only storing the index of the smallest value. Then at the end of the second loop (bottom of the first loop), the values are swapped. This is more efficient than a bubble sort because we are not swapping the items in the array (excessive memory access) every time we determine that (list[j] < list[min]). The swap is done n times rather than (n * n) times. The second sort is sorting an array of indexes based on the percentage change. The original list array is untouched. It is used only for reference. The final result is the indexByGain array. This should be returned. But, it is not and so is lost. For the reporting, the programmer would need to run through the indexByGain to print out the report as: for (int k = 0; k < length; k++) printf("%f\n", list[indexByGain[k]].getPercentChange()); assuming that getPercentChange() returns a double or float. Sorry, my C coding is a bit rusty.
-
Hi all, I have a working program that reads stocks symbols and values from a text file and do some operations on the data, and then it outputs the the data as two reports. The first report is sorted by stock symbols, and the other report is sorted by percent gain/loss. I'm having difficulties understating how these sort functions are doing the comparisons.. Can you guys provide some explanation please?
//sorts the stocks naturally (stock symbol)
template<class elemType>
void listType<elemType>::sort(){
int i, j;
int min;
elemType temp;for (i = 0; i <length; i++){ min = i; for (j = i + 1; j < length; ++j) if (list\[j\] < list\[min\]) min = j; temp = list\[i\]; list\[i\] = list\[min\]; list\[min\] = temp; }}
//sorts the stocks by percent gain/loss
void stockListType::sortByGain(){
int i, j;
int temp;
indexByGain = new int[length];//Pre-populate the index array for(int c = 0; c < length; c++){ indexByGain\[c\] = c; } //Sort by the percentage change for (i = 0; i <length; i++){ for (j = i + 1; j < length; j++){ if (list\[indexByGain\[j\]\].getPercentChange() > list\[indexByGain\[i\]\].getPercentChange()){ temp = indexByGain\[i\]; indexByGain\[i\] = indexByGain\[j\]; indexByGain\[j\] = temp; } } }}
-
Hi all, I have a working program that reads stocks symbols and values from a text file and do some operations on the data, and then it outputs the the data as two reports. The first report is sorted by stock symbols, and the other report is sorted by percent gain/loss. I'm having difficulties understating how these sort functions are doing the comparisons.. Can you guys provide some explanation please?
//sorts the stocks naturally (stock symbol)
template<class elemType>
void listType<elemType>::sort(){
int i, j;
int min;
elemType temp;for (i = 0; i <length; i++){ min = i; for (j = i + 1; j < length; ++j) if (list\[j\] < list\[min\]) min = j; temp = list\[i\]; list\[i\] = list\[min\]; list\[min\] = temp; }}
//sorts the stocks by percent gain/loss
void stockListType::sortByGain(){
int i, j;
int temp;
indexByGain = new int[length];//Pre-populate the index array for(int c = 0; c < length; c++){ indexByGain\[c\] = c; } //Sort by the percentage change for (i = 0; i <length; i++){ for (j = i + 1; j < length; j++){ if (list\[indexByGain\[j\]\].getPercentChange() > list\[indexByGain\[i\]\].getPercentChange()){ temp = indexByGain\[i\]; indexByGain\[i\] = indexByGain\[j\]; indexByGain\[j\] = temp; } } }}
The first one (sort()), scans the list to find the smallest item (it assumes that elemType has operator<() defined, which we presume is bases on it's ticker symbol string). It then swaps that items with the item in list[0]. Next it scans for the smallest between list[1] and the end, and swaps that with list[1], and onward, swapping the smallest among list[2] & the end with list[2]. I believe this actually makes it an insertion sort, which is slightly faster that a bubble sort (and generally considered the best for small lists) The second sort (sortByGain()) doesn't want to change the order of the items in list (which presumably have just been sorted by sort()), so it creates a array of indexes into list, so that after both functions are called list[0] is the first stock alphabetically, while list[indexByGain[0]] is the stock with the highest gain. sortByGain() does a proper (slow) Bubble sort, potenially swapping after every compare, moving the desired item (which is the smallest in the first sort and the largest in the second) one position closer to it's final location each time.
Truth, James
-
I would recommend the use of the functions from the standard library like
qsortorqsort_s.«_Superman_» _I love work. It gives me something to do between weekends.
«_Superman_» wrote:
I would recommend the use of the functions from the standard library like
qsortorqsort_s.agreed! save time
"Opinions are neither right nor wrong. I cannot change your opinion. I can, however, change what influences your opinion." - David Crow
Never mind - my own stupidity is the source of every "problem" - Mixturecheers, Alok Gupta VC Forum Q&A :- I/IV Support CRY- Child Relief and You