My Math Forum complexity of primitive sorting
 User Name Remember Me? Password

 Computer Science Computer Science Forum

 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]
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:
 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.

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.

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:
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.

 Tags complexity, primitive, sorting

### content

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top