subject:"\[R\] Variation of bubble sort \(based on divisors\)"

Re: [R] Variation of bubble sort (based on divisors)

2017-04-03 Thread Hervé Pagès


Hi Piotr,

On 03/31/2017 11:16 AM, Piotr Koller wrote:

Hi, I'd like to create a function that will sort values of a vector on a
given basis:

-zeros

-ones

-numbers divisible by 2

-numbers divisible by 3 (but not by 2)

-numbers divisible by 5 (but not by 2 and 3)


In other words, you want to sort your values by smallest divisor
(not regarding 1 as a divisor). The sorting part is easy if you can
map each value to its smaller divisor (mapping 0 to 0 and 1 to 1):

1) Map the values in 'x' to their smallest divisor:

  x <- as.integer(x)
  smallest_divisor <- sapply(x, smallestDivisor)
  smallest_divisor[x == 0L] <- 0L
  smallest_divisor[x == 1L] <- 1L

2) Then sort 'x' based on the values in 'smallest_divisor':

  x[order(smallest_divisor)]

So the real difficulty here is not the sorting, it's to find the
smallest divisor. Here is a function that does this:

  smallestDivisor <- function(x)
  {
if (!is.integer(x) || length(x) != 1L || is.na(x))
stop("'x' must be a single integer")

## All prime numbers <= 2*3*5*7 = ND
pm210 <- as.integer(c(2, 3, 5, 7, 11, 13, 17, 19,
  23, 29, 31, 37, 41, 43, 47,
  53, 59, 61, 67, 71, 73, 79,
  83, 89, 97, 101, 103, 107, 109,
  113, 127, 131, 137, 139, 149,
  151, 157, 163, 167, 173, 179,
  181, 191, 193, 197, 199))
ans <- which(x %% pm210 == 0L)[1L]
if (!is.na(ans))
return(pm210[ans])

## Use Sieve of Eratosthenes to prepare the divisors that
## are > ND and <= 2*ND.
pm0 <- c(3L, 5L, 7L)  # must start with 3, not 2
prod0 <- as.integer(cumprod(pm0)[length(pm0)])
ND <- 2L * prod0
div <- 1L + 2L*(0L:(prod0-1L))
for (p in pm0)
div <- setdiff(div, p*(1L:(ND%/%p-1L)))
div <- div + ND
sqrtx <- sqrt(x)
while (div[1L] <= sqrtx) {
ans <- which(x %% div == 0L)[1L]
if (!is.na(ans))
return(div[ans])
div <- div + ND
}
x
  }

I'm sure there are faster ways to do this.

Cheers,
H.




etc.

I also want to omit zeros in those turns. So when I have a given vector of
c(0:10), I want to receive 0 1 2 4 6 8 10 3 9 5 7 I think it'd be the best
to use some variation of bubble sort, so it'd look like that

sort <- function(x) {
 for (j in (length(x)-1):1) {
   for (i in j:(length(x)-1)) {
 if (x[i+1]%%divisor==0 && x[i]%%divisor!=0) {
  temp <- x[i]
  x[i] <- x[i+1]
  x[i+1] <- temp
  }
}
  }
 return(x)}

This function works out well on a given divisor and incresing sequences.

sort <- function(x) {
  for (j in (length(x)-1):1) {
 for (i in j:(length(x)-1)) {
   if (x[i+1]%%5==0 && x[i]%%5!=0) {
temp <- x[i]
x[i] <- x[i+1]
x[i+1] <- temp
   }
  }
 }
  return(x)
 }

x <- c(1:10)
print(x)
print(bubblesort(x))

This function does its job. It moves values divisible by 5 on the
beginning. The question is how to increase divisor every "round" ?

Thanks for any kind of help

[[alternative HTML version deleted]]

__
R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://urldefense.proofpoint.com/v2/url?u=https-3A__stat.ethz.ch_mailman_listinfo_r-2Dhelp=DwICAg=eRAMFD45gAfqt84VtBcfhQ=BK7q3XeAvimeWdGbWY_wJYbW0WYiZvSXAJJKaaPhzWA=AeHAcF7RnhWvQIqG5c2ucgFS0WIOmMFeRheLIeSwu0U=xJMmDOJLaQZ0QMmI7rkkNd2T5-zrh843rlJ-R1LQ9G8=
PLEASE do read the posting guide 
https://urldefense.proofpoint.com/v2/url?u=http-3A__www.R-2Dproject.org_posting-2Dguide.html=DwICAg=eRAMFD45gAfqt84VtBcfhQ=BK7q3XeAvimeWdGbWY_wJYbW0WYiZvSXAJJKaaPhzWA=AeHAcF7RnhWvQIqG5c2ucgFS0WIOmMFeRheLIeSwu0U=c9IcZitWvur2grg8C54Jnt5LmajX0ODDANY-BGRzMbk=
and provide commented, minimal, self-contained, reproducible code.



--
Hervé Pagès

Program in Computational Biology
Division of Public Health Sciences
Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N, M1-B514
P.O. Box 19024
Seattle, WA 98109-1024

E-mail: hpa...@fredhutch.org
Phone:  (206) 667-5791
Fax:(206) 667-1319

__
R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

Re: [R] Variation of bubble sort (based on divisors)

2017-04-03 Thread Boris Steipe

Piotr - keep discussions on-list please.

I generally do not open attachments to eMails.

You are misinterpreting the results:

0:  0
1:  1
2:  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30
3:  3  9 15 21 27  (all even multiples of 3 have been sorted with 2)
5:  5 25  (10, 20, 30 are sorted as multiples of 2; 15 is a multiple of 3)
7:  7 (14, 28 are multiples of 2; 21 is a multiple of 3)
others: 11 13 17 19 23 29


B.






> On Apr 3, 2017, at 3:27 PM, Piotr Koller  wrote:
> 
> Hi, I've noticed some weird thing about this function. It's not treating one 
> digit numbers as divisible by themselves. For example, In 0:30 sequence
> 
> 
> It prints me a result of: 
> [1]  0  1  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30  3  9 15 21 27  5 25  
> 7 11 13 17
> [29] 19 23 29
> 
> 
> 
> So, it treats 15 as divisible by 5, 21 as divisible by 7, but not 5 as 
> divisible by 5 and 7 as divisble by 7. I've also noticed when I use 1:10 
> instead of 0:10 sequence, it prints a "double" result
>  0  1  2  4  6  8 10  3  9  5  7  2  4  6  8 10  3  9  5  7
> 
> What's the reason behind those problems? Code is in the attachment.
> 
> 
>   Wolny od wirusów. www.avast.com
> 
> On Sat, Apr 1, 2017 at 2:38 PM, Boris Steipe  wrote:
> The modulo operator returns remainder after division. The goal is to select a 
> number if the remainder is zero. Casting a number to logical returns FALSE if 
> it is zero, TRUE otherwise. The "!" operator inverts that.
> 
> 
> (2:9)
> (2:9) %% 3
> as.logical((2:9) %% 3)
> !as.logical((2:9) %% 3)
> 
> 
> B.
> 
> 
> 
> 
> > On Apr 1, 2017, at 8:16 AM, Piotr Koller  wrote:
> >
> > Thank you very much. You are very helpful. Can you explain what's the 
> > general purpose of this" !as.logical " operator in for loop?
> >
> >   Wolny od wirusów. www.avast.com
> >
> > On Sat, Apr 1, 2017 at 2:15 AM, Boris Steipe  
> > wrote:
> > This looks opaque and hard to maintain.
> > It seems to me that a better strategy is to subset your vector with modulo 
> > expressions, use a normal sort on each of the subsets, and add the result 
> > to each other. 0 and 1 need to be special-cased.
> >
> >
> > myPrimes <- c(2, 3, 5)
> > mySource <- sample(0:10)
> >
> > # special case 0,1
> > sel <- mySource < 2
> > myTarget <- sort(mySource[sel])
> > mySource <- mySource[!sel]
> >
> > # Iterate over requested primes
> > for (num in myPrimes) {
> > sel <- !as.logical(mySource %% num)
> > myTarget <- c(myTarget, sort(mySource[sel]))
> > mySource <- mySource[!sel]
> > }
> >
> > # Add remaining elements
> > myTarget <- c(myTarget, sort(mySource))
> >
> >
> > B.
> >
> >
> >
> >
> >
> >
> > > On Mar 31, 2017, at 2:16 PM, Piotr Koller  wrote:
> > >
> > > Hi, I'd like to create a function that will sort values of a vector on a
> > > given basis:
> > >
> > > -zeros
> > >
> > > -ones
> > >
> > > -numbers divisible by 2
> > >
> > > -numbers divisible by 3 (but not by 2)
> > >
> > > -numbers divisible by 5 (but not by 2 and 3)
> > >
> > > etc.
> > >
> > > I also want to omit zeros in those turns. So when I have a given vector of
> > > c(0:10), I want to receive 0 1 2 4 6 8 10 3 9 5 7 I think it'd be the best
> > > to use some variation of bubble sort, so it'd look like that
> > >
> > > sort <- function(x) {
> > > for (j in (length(x)-1):1) {
> > >   for (i in j:(length(x)-1)) {
> > > if (x[i+1]%%divisor==0 && x[i]%%divisor!=0) {
> > >  temp <- x[i]
> > >  x[i] <- x[i+1]
> > >  x[i+1] <- temp
> > >  }
> > >}
> > >  }
> > > return(x)}
> > >
> > > This function works out well on a given divisor and incresing sequences.
> > >
> > > sort <- function(x) {
> > >  for (j in (length(x)-1):1) {
> > > for (i in j:(length(x)-1)) {
> > >   if (x[i+1]%%5==0 && x[i]%%5!=0) {
> > >temp <- x[i]
> > >x[i] <- x[i+1]
> > >x[i+1] <- temp
> > >   }
> > >  }
> > > }
> > >  return(x)
> > > }
> > >
> > > x <- c(1:10)
> > > print(x)
> > > print(bubblesort(x))
> > >
> > > This function does its job. It moves values divisible by 5 on the
> > > beginning. The question is how to increase divisor every "round" ?
> > >
> > > Thanks for any kind of help
> > >
> > >   [[alternative HTML version deleted]]
> > >
> > > __
> > > R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> > > https://stat.ethz.ch/mailman/listinfo/r-help
> > > PLEASE do read the posting guide 
> > > http://www.R-project.org/posting-guide.html
> > > and provide commented, minimal, self-contained, reproducible code.
> >
> >
> 
> 
> 

__
R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

Re: [R] Variation of bubble sort (based on divisors)

2017-03-31 Thread Boris Steipe

This looks opaque and hard to maintain.
It seems to me that a better strategy is to subset your vector with modulo 
expressions, use a normal sort on each of the subsets, and add the result to 
each other. 0 and 1 need to be special-cased.


myPrimes <- c(2, 3, 5)
mySource <- sample(0:10)

# special case 0,1
sel <- mySource < 2  
myTarget <- sort(mySource[sel])
mySource <- mySource[!sel]

# Iterate over requested primes
for (num in myPrimes) {
sel <- !as.logical(mySource %% num)
myTarget <- c(myTarget, sort(mySource[sel]))
mySource <- mySource[!sel]
}

# Add remaining elements
myTarget <- c(myTarget, sort(mySource))  


B.






> On Mar 31, 2017, at 2:16 PM, Piotr Koller  wrote:
> 
> Hi, I'd like to create a function that will sort values of a vector on a
> given basis:
> 
> -zeros
> 
> -ones
> 
> -numbers divisible by 2
> 
> -numbers divisible by 3 (but not by 2)
> 
> -numbers divisible by 5 (but not by 2 and 3)
> 
> etc.
> 
> I also want to omit zeros in those turns. So when I have a given vector of
> c(0:10), I want to receive 0 1 2 4 6 8 10 3 9 5 7 I think it'd be the best
> to use some variation of bubble sort, so it'd look like that
> 
> sort <- function(x) {
> for (j in (length(x)-1):1) {
>   for (i in j:(length(x)-1)) {
> if (x[i+1]%%divisor==0 && x[i]%%divisor!=0) {
>  temp <- x[i]
>  x[i] <- x[i+1]
>  x[i+1] <- temp
>  }
>}
>  }
> return(x)}
> 
> This function works out well on a given divisor and incresing sequences.
> 
> sort <- function(x) {
>  for (j in (length(x)-1):1) {
> for (i in j:(length(x)-1)) {
>   if (x[i+1]%%5==0 && x[i]%%5!=0) {
>temp <- x[i]
>x[i] <- x[i+1]
>x[i+1] <- temp
>   }
>  }
> }
>  return(x)
> }
> 
> x <- c(1:10)
> print(x)
> print(bubblesort(x))
> 
> This function does its job. It moves values divisible by 5 on the
> beginning. The question is how to increase divisor every "round" ?
> 
> Thanks for any kind of help
> 
>   [[alternative HTML version deleted]]
> 
> __
> R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

__
R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

[R] Variation of bubble sort (based on divisors)

2017-03-31 Thread Piotr Koller

Hi, I'd like to create a function that will sort values of a vector on a
given basis:

-zeros

-ones

-numbers divisible by 2

-numbers divisible by 3 (but not by 2)

-numbers divisible by 5 (but not by 2 and 3)

etc.

I also want to omit zeros in those turns. So when I have a given vector of
c(0:10), I want to receive 0 1 2 4 6 8 10 3 9 5 7 I think it'd be the best
to use some variation of bubble sort, so it'd look like that

sort <- function(x) {
 for (j in (length(x)-1):1) {
   for (i in j:(length(x)-1)) {
 if (x[i+1]%%divisor==0 && x[i]%%divisor!=0) {
  temp <- x[i]
  x[i] <- x[i+1]
  x[i+1] <- temp
  }
}
  }
 return(x)}

This function works out well on a given divisor and incresing sequences.

sort <- function(x) {
  for (j in (length(x)-1):1) {
 for (i in j:(length(x)-1)) {
   if (x[i+1]%%5==0 && x[i]%%5!=0) {
temp <- x[i]
x[i] <- x[i+1]
x[i+1] <- temp
   }
  }
 }
  return(x)
 }

x <- c(1:10)
print(x)
print(bubblesort(x))

This function does its job. It moves values divisible by 5 on the
beginning. The question is how to increase divisor every "round" ?

Thanks for any kind of help

[[alternative HTML version deleted]]

__
R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

Re: [R] Variation of bubble sort (based on divisors)

Re: [R] Variation of bubble sort (based on divisors)

Re: [R] Variation of bubble sort (based on divisors)

[R] Variation of bubble sort (based on divisors)

4 matches

Site Navigation

Mail list logo

Footer information