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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      