What is the expected complexity of a randomized sorting algorithm?
346407
I think it is order(N squared), so not very good. It's a variant of bubble sort, which you can google. Plus you never know when you're done!
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.
855670
Boy, this is tricky.  I think the probability is (8! * 41c2 * 10c2)/49!, where 41c2 = 41!/39!2! and 10c2 = 10!/8!2!  In this number, 8! represents the correct picks, 41c2 the incorrect picks, and 10c2 the number of ways to order the picks.\n\nFor exactly seven correct numbers in 10 picks , only a minor change is needed.  It becomes (7! * 42c3 * 10c3)/49!.  Follow this pattern for 6 of 10, 5 of 10, etc
226471
get it sorted 1st, \nthen get the differences of adjacent number pairs, \nget the min of this differences
836161
Perhaps you can explain to everyone why you can not do this in google as I just did?\n\n\nPDF] BREADTH-FIRST SEARCH IN THE EIGHT QUEENS PROBLEM C K Yuen and M D ...File Format: PDF/Adobe Acrobat\nThe Eight Queens Problem is a familiar example in programming and algorithm textbooks . Usually, the given solution applies depth-first search with ...\nportal.acm.org/ft_gateway.cfm?id=185019&type=pdf - Similar pages \n\nWeb Resources Guide for Chapter 9Animations of breadth-first search and depth-first search can be found at the ... You can generate all the solutions to the n-queens problem in section 9.4. ...\nwww.mhhe.com/math/advmath/rosen/r5/student/ch09/weblinks.html - 44k - Cached - Similar pages \n\nEight Queens PlusThis is an extension of the "Eight Queens" problem: "Place 8 queens on a ... Here's the recursive depth first Search procedure that finds all 92 solutions: ...\nwww.delphiforfun.org/Programs/EightQueensPlus.htm - 19k - Cached - Similar pages \n\nDictionary of Algorithms, Data Structures, and ProblemsProblems include traveling salesman and Byzantine generals. ... Very Fast Substring Search Algorithm, Communications of the ACM, 33(8):132-142, August 1998. ...\nwww.nist.gov/dads/ - 88k - Cached - Similar pages
55122
Better way is to creat an instance of Random class.\nIt has methods, nextInteger(), nextdouble(), and others.
189594
There is a great book that may help you..\n\n"Data Structures and Algorithms in C++","Adam Drozdel"..\n\ncheck the website.\n:)
979933
I'm giving u the program (in C), just go through it, then write the algo. It'll be easier.\n\n// Program :  MERGE  SORT\n\n#include<stdio.h>\n#include<conio.h>\n\nvoid mergesort(int *,int);\n\nvoid main()\n{\nint x[30],n,i;\nclrscr();\nprintf("Enter total no. of elements");\nscanf("%d",&n);\nprintf("Enter %d nos.",n);\nfor(i=0;i<n;i++)\n   scanf("%d",&x[i]);\n\nmergesort(x,n);\n\nprintf("After sorting in descending order :&#92;n");\nfor(i=n-1;i>=0;i--)\n  printf(" %d",x[i]);\n\ngetch();\n}\n\n\n\nvoid mergesort(int x[],int n)\n{\n  int aux[30],l1,l2,u1,u2,i,j,k,size;\n  size=1;   // merges file of size 1\n  while(size<n)\n  {\n    l1=0;   // initialize lower-bound of 1st. file\n    k=0;    // k is index for auxilliary array\n    while(l1+size<n)\n    {\n      // initialize remaining parameters...\n      l2=l1+size;\n      u1=l2-1;\n      u2=(l2+size-1)<n ? (l2+size-1):(n-1);\n      for(i=l1,j=l2;i<=u1 && j<=u2;k++)\n if(x[i]<=x[j])\n   aux[k]=x[i++];\n else\n   aux[k]=x[j++];\n      while(i<=u1)\n      aux[k++]=x[i++];\n      while(j<=u2)\n      aux[k++]=x[j++];\n\n      l1=u2+1;\n    } /* end of 2nd. while-loop */\n    for(i=l1;k<n;i++)\n       aux[k++]=x[i];\n    for(i=0;i<n;i++)\n       x[i]=aux[i];\n\n    size*=2;\n  } /* end of 1st. while-loop */\n}
785224
An algorithm for solving this would be to divide up the digits and shuffle or switch them in the direction that makes them closer to correct (the "greedy algorithm").  That should work without too much trial and error.
270029
There are of course good ways and bad ways of doing this.  The best way involves using a search tree like DFS and then pruning.  Instead of showing you something this complex (since I am unsure of your level of understanding) I will show you a common simple algorithm.  I will leave the code up to you, here is the psuedo-code:\n\n----------------------------------------------------\nALGORITHM JohnsonTrotter(n)\n//input: positive integer n\n//output: a list of all permutations of (1...n)\n\ninitialize the first permutation with (1,2...n) and with a second correspoing list ('L','L',...,'L').\n\n//Definition: mobile integer = if the corresponding letter is L \n//and the left adjacent number is smaller or vise versa.\n \nwhile there exists a mobile integer k do\n     find the largest integer K\n     swap K and the adjacent integer (left one if L) right otherwise\n     reverse the direction of all integers that are larger than k\nend do while\n----------------------------------------------------\nthis is really a simple algorithm to follow and to code, I am working off memmory here so it may not be the exact terms used but the algorithm is 100% I assure you.  Hope this helps and have fun.
511341
I'm not sure if I understood correctly but check out the pigeonhole principle
529442
just google for "merge sort java" and you will find examples. You may have to make modification for your linked-list requirement but that shouldn't be too difficult.
419823
You may have to be more specific.\n\nalgorithm.h is not a standard library, as such it will be impossible to know what kind of code is in it.\n\nThere are numerous sorting algorithms, some more efficient than others.  There's bubble-sort, insertion-sort, heap-sort, quick-sort, etc.  If you're interested in searching and sorting, try doing a google search.\n\nThere is a sort() tool for UNIX systems, but that uses data streams and pipes at the console level, not intended for use inside a program.\n\nIf you want, you can open up algorithm.h and take a look inside.  You won't be able to see what the function definitions are, but at least you can see what parameters it takes.  Also, if you're really lucky ;-) there will be comments in the file describing what kind of sort it uses.  Just do a little detective work, and you can get all the info you need.
735064
That sounds familiar... Think I'm working on it now! But I don't remember q. It is n in my book. In which case, q (if I'm thinking right) is the number of samples. Then again what's up with the ^'s? If np was > 10, then it meant that the distribution was approx. normal. You might be ahead of me right now...
245731
We can classify sorting techniques according to their underlying structure.\n\nSwap-based sorts begin conceptually with the entire list, and exchange particular pairs of elements (adjacent elements or elements with certain step like in  Shell sorts) moving toward a more sorted list. \nMerge-based sorts creates initial "naturally" or "unnaturally" sorted sequences, and then add either one element (insertion sort) or merge two already sorted sequences. \nTree-based sorts store the data, at least conceptually, in a binary tree; there are two different approaches, one based on heaps, and the other based on search trees. \nFinally, the other category catches sorts which use additional key-value information, such as radix or bucket sort. \n We can also classify sorting algorithms by several other criteria:\n\nComputational complexity (worst, average and best number of comparisons for several typical test cases, see below) in terms of the size of the list (n). Typically, good average number of comparisons is O(n log n) and bad is O(n2). Note that asymptotic analysis does not tell about algorithms behavior on small lists or worst case behavior. Worst case behavior is probably more important then average. For example "plain-vanilla" quicksort requires O(n2) comparisons in case of already sorted arrays: a very important in practice case.  Sort algorithms which only use an abstract key comparison operation always need at least O(n log n) comparisons on average; while sort algorithms which exploit the structure of the key space cannot sort faster than O(n log k) where k is the size of the keyspace.  Please note that the number of comparison is just convenient theoretical metric. In reality both moves and comparisons matter and on short keys the cost of move is comparable to the cost of comparison (even if pointers are used). \n  \nStability: stable sorting algorithms maintain the relative order of records with equal keys. If all keys are different the this distinction does not make any sense. But if there are equal keys, then  a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list. \n  \nMemory usage (and use of other computer resources). One large class of algorithms are "in-place sorting. They are generally slower than algorithms that use additional memory: additional memory can be used for mapping of keyspace.  Most fast stable algorithms use additional memory.  With the current 4G of memory of more of  memory and virtual memory used in all major OSes, the old emphasis on algorithms that does not require additional memory should be abandoned.  Speedup that can be achieved by using of a small amount of additional memory is considerable and it is stupid to ignore it.  Moreover you can use pointers and then additional space of the size N actually becomes size of N pointers. In real life when the records usually have size several times bigger then the size of a pointers (4 bytes in 32 bit CPUs) that makes huge difference and make those methods much more acceptable then they look form purely theoretical considerations. \n  \nThe difference between worst case and average behavior (quicksort is efficient only on the average, and its worst case in to order n2, while heapsort has an interesting property that the worst case is not much different form the an average case.  Behaviors on practically important data sets (completely sorted, inversely sorted and 'almost sorted' (1 to K permutations, where K is less then N/10) has tremendous practical implications that are often not addressed or addressed incorrectly in textbooks other then Knuth. \nAmong non-stable algorithms Shellsort is probably the most underappreciated and quicksort  is one of the most overhyped. Please note the quicksort is a fragile algorithm because the choice of pivot is equal to guessing an important proper
1159892
Sequential search:\n\nhttp://cprogramming.com/discussionarticles/sorting_and_searching.html
2509
Here's a java solution that uses recursion.  The permute function takes two arguments: a done portion and a todo portion.   The basic idea is that each of the characters in the todo portion could be the next character.  So, at each step, n recursive calls are made, where n is the length of todo.  Each call chooses a different character as the next character to go into the done portion.  So, the first time the number of recursive calls will equal the number of characters in the initial string.  Each of these calls will make further recursive calls equal to the number of characters in the initial string minus one.  And so on.  Thus, the number of solutions will be n! = n*n-1*n-2*...*1, where n is the number of characters in the initial string.\n\nThe program below was tested with java's sun compiler 1.4.2.\npublic class perm\n{\n  public perm(String S)\n  {     \n    permute("", S);\n  }     \n  public void permute(String done, String todo) \n  {     \n    if ((todo.length()==0)||\n        (todo.equals("")))\n      System.out.println(done);\n    else        \n    {           \n      for (int i=0; i<todo.length(); i++)\n      {                 \n        String c = todo.substring(0,1);\n        todo = todo.substring(1);\n        permute(done+c, todo);  \n        todo = todo + c;        \n      }                 \n    }           \n  }     \n  public static void main(String args[])\n  {     \n    if ((args.length==0)||\n        (args[0].length()==0)||\n        (args[0].equals("")))\n      return;           \n    perm p = new perm(args[0]);\n  }     \n}