
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
June 19th, 2010, 09:35 PM  #1 
Member Joined: Apr 2010 Posts: 54 Thanks: 0  complexity of primitive sorting
What follows is pseudocode for a simple algorithm to sort an array of numbers: procedure slowsort ( x: array[1..n] ) {sorts a given array of numbers into nondecreasing order} for r:=1 to n1 do for j:=r+1 to n do if x[j]<x[r] then swap(x[j],x[r]) end. {slowsort} Here swap(x[j],x[r]) is a procedure that interchanges the positions of x[j] and x[r] in the array. What the algorithm does is to first find the smallest element and put it in the first position, then find the second smallest and put it in the 3rd position, etc. I need to count the average number of swaps (calls to swap) that the algorithm does if one analyzes all n! possible initial permutations of the array. Assume that all the elements of the array are distinct. According to my book this should be Theta(n^2). This means that the average is larger than n^2 times some constant and smaller than n^2 times some other constant. I'm not sure how to prove this. Thanks. 
June 20th, 2010, 10:08 AM  #2  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: complexity of primitive sorting Quote:
 
June 20th, 2010, 01:14 PM  #3  
Member Joined: Apr 2010 Posts: 54 Thanks: 0  Re: complexity of primitive sorting Quote:
 
June 20th, 2010, 05:39 PM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: complexity of primitive sorting Quote:
 

Tags 
complexity, primitive, sorting 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primitive root  James1973  Abstract Algebra  1  November 19th, 2013 08:47 PM 
Primitive Statements  rhymin  Applied Math  4  March 24th, 2013 11:20 AM 
Primitive Statements  rhymin  Algebra  1  March 24th, 2013 08:41 AM 
Sorting by CoveredRest Distance and Time  poisonpoison  Algebra  0  October 15th, 2011 01:00 PM 
Primitive function  Valar30  Calculus  5  April 23rd, 2011 05:58 PM 