My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
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 pseudo-code 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 n-1 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.
becko is offline  
 
June 20th, 2010, 10:08 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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:
Originally Posted by becko
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.
You should be able to count the exact number of loops for a given n. There are n-1 outer loops, each of which has 1 to n-1 inner loops. In particular, the inner statement executes (n-1) + (n-2) + ... + 2 + 1 times. Total this up using high-school methods and that should give you Theta(n^2) directly.
CRGreathouse is offline  
June 20th, 2010, 01:14 PM   #3
Member
 
Joined: Apr 2010

Posts: 54
Thanks: 0

Re: complexity of primitive sorting

Quote:
Originally Posted by CRGreathouse
There are n-1 outer loops, each of which has 1 to n-1 inner loops. In particular, the inner statement executes (n-1) + (n-2) + ... + 2 + 1 times. Total this up using high-school methods and that should give you Theta(n^2) directly.
This counts the number of comparisons ( x[j] < x[r] ? ) that are made. Only if the comparison returns true, will there be a call to swap(x[j],x[r]). What I want to count is the number of calls to swap. I need the average number of calls to swap.
becko is offline  
June 20th, 2010, 05:39 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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:
Originally Posted by becko
Quote:
Originally Posted by CRGreathouse
There are n-1 outer loops, each of which has 1 to n-1 inner loops. In particular, the inner statement executes (n-1) + (n-2) + ... + 2 + 1 times. Total this up using high-school methods and that should give you Theta(n^2) directly.
This counts the number of comparisons ( x[j] < x[r] ? ) that are made. Only if the comparison returns true, will there be a call to swap(x[j],x[r]). What I want to count is the number of calls to swap. I need the average number of calls to swap.
Hmm, sorry I missed that. I suppose you should look at the number of elements that are expected to be out of order and the average distance they will travel. At least what I wrote is an upper bound on the number of comparisons, so you just need the low side of average.
CRGreathouse is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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 Covered-Rest Distance and Time poisonpoison Algebra 0 October 15th, 2011 01:00 PM
Primitive function Valar30 Calculus 5 April 23rd, 2011 05:58 PM





Copyright © 2019 My Math Forum. All rights reserved.