Using C++ how can I write a recursive function to sort an array?
447556
Look up "quicksort".\n\nIt fits very naturally into a recursive implementation\nand is also a very efficient sorting algorithm.\n\nI've included a link to the Solaris source for quicksort.\nIt is written in C (rather than C++).  It is somewhat\ncomplicated because it optimizes the sorting of\nshort sequences by switching to an insertion sort.\nHowever, you could implement a simpler version which\nran quicksort all the way to completion.
102513
Sorts:\n\n http://www.programmersheaven.com/zone3/cat475/index.htm\n\nBinary search:\n\n http://physicsresearch.may.ie/yr3compphys/BorlandC2004.doc
898314
Here are some general data structures:\n\n- Set\n- List\n- Map\n- Tree\n- Table\n- Stack\n- Queue
116407
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(n log n) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(n log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.\n\nThe algorithm\n-------------\nQuicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.\n\nThe steps are:\n\nPick an element, called a pivot, from the list. \nReorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. \nRecursively sort the sub-list of lesser elements and the sub-list of greater elements. \nThe base case of the recursion are lists of size zero or one, which are always sorted. The algorithm always terminates because it puts at least one element in its final place on each iteration.\n\nIn simple pseudocode, the algorithm might be expressed as:\n\n function quicksort(q)\n     var list less, pivotList, greater\n     if length(q) ≤ 1  \n         return q  \n     select a pivot value pivot from q\n     for each x in q except the pivot element\n         if x < pivot then add x to less\n         if x ≥ pivot then add x to greater\n     add pivot to pivotList\n     return concatenate(quicksort(less), pivotList, quicksort(greater))
742125
Heapsort is always O(n lg n). Did you mean O(n)?
669633
do you mean you want to sort them? well, you just need to search for sort algorithm. There are some that needs mentioning, like QuickSort and Bubble sort, the first being are the fastest but most complicated and the latter simplest but inefficient. \n\nQuickSort is sorting by choosing some middle value (randomly, or for more efficiency, chosing the approximate median), and checking other value, if it is larger than the current value, it's put after the middle value, if it's smaller, it's put in before the middle value, if it's equal, it's up to programmer want to put it at low or high value (basically, seperating data smaller than middle value and larger value.). Then the data collection in the smaller value and the bigger value is sorted individually. Gradually, this will sort the datas. However, it is widely known that, when working with smaller amount of data, quicksort has a huge overhead, and usually when the data is small enough, the program switch to other sorting method.\n\nVisual on QuickSort\n1 5 6 8 4 7 5 9 6 5 1 2 4 7 8 9 'initial data\n1 5 6 8 4 7.5.9 6 5 1 2 4 7 8 9 'choose midvalue 5\n1 4 1 2 4.5.5 6 8 7 9 6 5 7 8 9 'seperate low and high value\nlow1= 1 4 1 2 4, high1=5 5 9 8 7 6 8 7 9 6 5 'sort low first\nlow1 = 1 4 1.2.4 'mid value = 2\nlow1 = 1 1 2 4 4 'low1 sorted\n1 1 2 4 4, high1=5 5 9 8 7 6 8 7 9 6 5 'sort high\nhigh1=5 5 9 8.7.6 8 7 9 6 5 'middle value = 7\nlow2=6 5 6 5 high2 =7 9 8 7 9 8 'sort low\nlow2=6 5 6 5 ' middle value 5\nlow2=5 5 6 6 ' sorted\n5 5 6 6, high2 =7 9 8 7 9 8 'sort high\nhigh2 =7 9 8 7 9 8 'middle value 8\nhigh2 =7 7 8 8 9 9 'sorted\n\nlow1 = 1 1 2 4 4\nlow2=5 5 6 6\nhigh2 =7 7 8 8 9 9 \n\nassemble these together:\n1 1 2 4 4 5 5 6 6 7 7 8 8 9 9 \n\nPhew, QuickSort really is NOT for human. It's hard for human to sort using quicksort, but relatively easy for computer, using self-calling functions\n\n~~~~~~~~~\n\nBubble sort is sorting algorithm by comparing a value, to it's next value. If the next value is smaller than the current value, it is swapped, if the next value is larger it do nothing. Then move to the next pair, until the last pair. Then repeat the process from the first data until all data is sorted.\n\nVisual on Bubble Sort:\n15 43 64 61 57 67 89 74 65 'initial data\n15 43 64 61 57 67 89 74 65 'check 15 and 43, do nothing\n15 32 43 71 57 67 89 74 65 'check 43 and 32, swap\n15 32 43 71 57 67 89 74 65 'check 43 and 71, do nothing\n15 32 43 57 71 67 89 74 65 'check 71 and 57, swap\n15 32 43 57 67 71 89 74 65 'check 71 and 67, swap\n15 32 43 57 67 71 89 74 65 'check 71 and 89, do nothing\n15 32 43 57 67 71 74 89 65 'check 89 and 74, swap\n15 32 43 57 67 71 74 65 89 'check 89 and 65, swap\n15 32 43 57 67 71 74 65 89 'repeat process\n15 32 43 57 67 71 74 65 89 'check 15 to 74 is already sorted\n15 32 43 57 67 71 65 74 89 'check 74 and 65, swap\n15 32 43 57 67 71 65 74 89 'check 74 to 89 is already sorted\n15 32 43 57 67 71 65 74 89 'check 15 to 71 is already sorted\n15 32 43 57 67 65 71 74 89 'check 71 and 65, swap\n15 32 43 57 67 65 71 74 89 'check 71 to 89 is already sorted\n15 32 43 57 67 65 71 74 89 'check 15 to 67 is already sorted\n15 32 43 57 67 65 71 74 89 'check 67 and 65, swap\n15 32 43 57 67 65 71 74 89 'check all data sorted\n\nNote: in this one, I rather lucky, the random data I used is rather already almost sorted. Bubble sort is slowest when a data is already sorted, but reversed to what it should have been sorted, while fastest when the values are almost sorted.\n\nTrivia: the name bubble sort come since in bubble sort, the higher data is like a bubble, it goes up and up, while the lower value goes down and down
697721
First up you are going to need a compiler, you can get a free one here.\nhttp://www.borland.com/downloads/download_turbo.html\n\nInformation about it can be found here.\nhttp://www.turboexplorer.com/\n\nSome tutorials for c++ can be found here.\nhttp://www.cs.wustl.edu/~schmidt/C++/\n\nhttp://www.cplusplus.com/doc/tutorial/\n\nYou do not have to worry about memory allocation in C++, you can deal with it if you want, but you can avaoid it by using the keywords, 'new', 'delete', and 'delete[]'.\n\nRegarding the generation of random word segments, it would be done the same way as the random numbers are generated.\n\nIe, make an enum of these word segments,\nstring[] word_segments[5] = {"a", "an", "her", "ot", "etc"}\n\nWhen you get the random number, have it select a value from this array.\n\nword_segments[random_number];
197553
I looked through it pretty carefully, and I believe\nit is correct.  I would, however, like to make a\ncouple of comments.\n\nFirst, this code makes no attempt at balancing the\ntrees, so you can easily end up with a linked list\nrather than a binary tree.  Consider if you created\nthe tree by passing in a set of sorted values.\n\nSecond, from the perspective of understanding the\nflow, it's a little harder when a routine has so\nmany distinct return points.  I'm not sure if it is\nbetter, but at least consider the following code\nwhich is semantically identical:\n\nTreeNode* InsertTree( TreeNode* tnPtr, const TreeItemType& item)\n{\n    // Inserting an item\n    if(tnPtr == NULL)\n        tnPtr = new TreeNode(item);\n\n    if(item < tnPtr->item_)\n        tnPtr->left_ = InsertTree(tnPtr->left_, item);\n    else if(item > tnPtr->item_)\n        tnPtr->right_ = InsertTree(tnPtr->right_, item);\n\n    return tnPtr;\n}
981994
pseudo code sort of, based on C++... easiest for me... I am going to do this with an array of integers because the number of integers read into the program can be different than just three.  This can be easily changed though...\n\nstart program:\n\nint arrayInt[3];  //  places to store three integers\nint largestNumber = 0;  // place to store largest number\ncout << "enter three numbers:  ";   // request for three numbers\nfor (int i = 0; i < 3; i++)\n{     cin >> arrayInt[i]; }    \n// takes the three values from the user's input and stores them in an element in the arrayInt array.\n// so... now you need to compare all of the elements in arrayInt\nfor (int i = 0; i < 3; i++)  // do this three times\n{\n     if ( arrayInt[i] > largestNumber )  \n// comare largestNumber to the current element in the array\n// if it is larger, give largestNumber the value of that element\n     {\n         largestNumber = arrayInt[i] );\n     }\n}\n\n// display the largest number\ncout << "the largest number is:  " << largestNumber << endl;\n\n ******************************************************************\n\n1. initialize variables for the three input integers and a variable to store the largest integer (set this one equal to zero).\n2. ask the user for the three numbers\n3. read the user's input into the variables to store them\n4. compare the values stored in the three variables by either doing it individually (if an array is not used) or with a for loop.  Go through each of the three variables that store the user's input and compare the stored value to the largestNumber variable.  The largestNumber variable should be set equal to 0 since we know that all the numbers will be non negative, therefore 0 is the lowest any of the input numbers can be.  If the value of a variable that stores a user given integer is larger than the largestNumber variable, store the value of the input variable in the largestNumber variable ( largestNumber = inputValue2 ).  As you check all of the three input variables, the largest of all of the values checked will be stored in the largestNumber variable. \n5. tell the user the largest variable
235678
you can do that by sorting the data source from where you are populating the list. Or while you are populating the list.\nIf you can tell me how you are populating, I can give you more pointers. I am not sure if there is any way to sort a list directly in java script.\n\njainnys\nMind Experts Inc.\nhttp://www.mindexp.com
781094
Nobody is going to do your homework for you. \n\nIf you're supposed to write code examples that illustrate how two comparable programs might look, then do this. Write some simple programs in C, and then re-write the same program in C++ but put the functions your void main calls in a class and instantiate the class.
140606
Remember to vote for the best answer\n\nExample and online help here :\nhttp://www.vb-helper.com/howto_disk_quicksort.html\n\n\n\n    \nBubbleSort Sub Code\nThis version of the BubbleSort sub is an ascending sort of an integer array. Add this sub to a project right after you start the project. Place the sub in a module for global scope.
697744
I'm not 100% sure I agree with that answer ({3,7,2...}), but regardless...\n\nQuicksort is a sorting algorithm (collect them all!) which breaks the problem of sorting a set of values into one of sorting two small sets of values, a strategy known as "divide and conquer".  It's also an "in place" sorting algorithm, meaning you can actually move values around in the set itself instead of having to work on copies.\n\nIn a quicksort, you pick a "partition" (I guess your teacher is calling it a "fence").  This can be any value in the set, and if your set is always nice & random like this you can just grab the first one instead of wasting time trying to find the median value or anything like that.\n\nOk, so in your example, your partition (fence) value is 10.  So, loop through the set and break it into two lists: everything less than 10, and everything greater than or equal to 10.  Now, you apply the same algorithm to the two lists.  Pick a pivot value in the "less than" list and split it into everything smaller than that value and everything greater than it.  Do the  same to the "greater than" list.  Keep narrowing down the sizes of these lists until you get to a list with a size of 1.  When you exit all the recursive calls, you'll find that the values in the set were sorted.\n\nIt's called a "quicksort" because it's incredibly fast compared to other sorting algorithms.  If written with threading in mind, the sorting tasks can even be split up among multiple CPUs if your system has more than one to make everything even faster.\n\nOh yeah, it's also ok to use a different sort algorithm after a while rather than recursively quicksorting these smaller & smaller lists.  So in that case you'd partition maybe once or twice...maybe three or four times...and then do a shell sort or something on the really small sets rather than break them down further.\n\nIt might help to watch a quicksort in action.  Check out the cool Java applet at this site (about halfway down):\n\nhttp://www.wanginator.de/studium/applets/quicksort_en.html\n\nYou'll have to put the values in one by one, but once you're done keep clicking "next step" to see how the partitioning and sorting works.\n\nOh yeah, I don't see why {3,7,2} should be the order of the "less than" set after just the first step.  Going left to right would give {2,3,7} and going right to left would give {7,3,2}.  What weird method of traversing a set gives that kind of order?
138457
Assuming this is in C, this is an impossible problem given the main program you provided, because you're passing in the parameters by value rather than by reference.  So any changes you make to those values inside the function will disappear once you return to the main context.\n\nIf you're allowed to change the main program to use pointers, you could do this:\n\nvoid sort2 (int *a, int *b) {\n  int tmp;\n\n  if (*a > *b) {\n   tmp = *a;\n   *a = *b;\n   *b = tmp;\n  }\n}\n\nGiven your main program, you'd call it like this:\n  sort2(&u, &v);\n\nBut it may be that this assignment was given to you specifically to demonstrate that you can't change the value of variables that you pass in by value).
240615
I am giving the solution in C++ using recursion..\n\n!!\n\n#include<iostream.h>\nvoid printstars(int n)\n{\nfor(int k=0;k<n;k++)\n     cout<<"*";\ncout<<endl;\n}\nvoid print1(int n)\n{\nif(n<=1)\n   printstars(n);\nelse\n   printstars(n-2);\n}\nvoid print2(int m,int n)\n{\nif(m==n)\n   cout<<endl;\nelse \n{\n   printstars(m);\n   print2(m+2,n);\n}\n}\n\nmain()\n{\nint n,m=1;\ncout<<"Enter an odd number n";\ncin>>n;\nprint2(m,n);\nprint1(n);\n}\n\nThis produces the output u needed and also uses recursion.
919233
Yes, when a list is already sorted, bubblesort will pass through the list once, and find that it does not need to swap any elements. \n\nIt will also use considerably less time if the elements in the list are not too far from their sorted places.
577652
Since you specified that the language is "C", it's\nworth pointing out that the Ansi standard guarantees\nthat the implementation will include a "qsort" function.\n\nAll you need to do is write the simple comparison\nfunction which is passed to qsort, and you're done.\n\nI copied the following (including the little test program)\ndirectly from the qsort man page:\n\n#include <stdlib.h>\n#include <stdio.h>\n\nstatic int\nintcompare(const void *p1, const void *p2)\n{\n  int i = *((int *)p1);\n  int j = *((int *)p2);\n\n  if (i > j)\n    return (1);\n  if (i < j)\n    return (-1);\n  return (0);\n}\n\nint\nmain()\n{\n  int i;\n  int a[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };\n  size_t nelems = sizeof (a) / sizeof (int);\n\n  qsort((void *)a, nelems, sizeof (int), intcompare);\n\n  for (i = 0; i < nelems; i++)\n    (void) printf("%d ", a[i]);\n\n  (void) printf("&#92;n");\n  return (0);\n}\n\n\nSee the references for the man page as well as the\nsource from the OpenSolaris site.