Coding Hartbeat

Task #1; StrangeSort

Page 1 of 1

10 Replies - 1237 Views - Last Post: 19 July 2010 - 10:35 AM

#1 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2267
  • View blog
  • Posts: 9,480
  • Joined: 29-May 08

Coding Hartbeat

Posted 18 July 2010 - 09:42 AM

Task#1 StrangeSort
If anyone does the proper name for this sort? Pyramid Sort?

Write a program (in any language) to do the following:

Input n integers in an array of size n.

Rearrange these integers in the following manner:
- Put the maximum value in the centre of the array
- Next largest value to its right
- Next largest value to its left, and so on.

Example:

Input- 1, 3, 5, 9, 4, 7,2 ; Output- 1, 3, 5, 9, 7, 4, 2


And now it's time for the gallery.

Codebugcfoley Solutions

import java.util.Arrays;

public class FunnyNumberSorter {

    public static void main(String[] args) {

        int[] n = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 

        int[] sorted = new int[n.length];

        final int center = (n.length / 2) - 1 + (n.length % 2);

        for(int i = 1, sgn = -1; i <= n.length; i++, sgn *= -1) {

            sorted[center + (sgn*i/2)] = n[i-1];

        }

        System.out.println(Arrays.toString(sorted));

    }
}





baavgai's Java Solution
Of course, they're half answers, since you're really only giving the order index and not actually sorting a list yet.

Here's mine:
int[] getOrder(int n) {
	int[] order = new int[n];
	int head=0, tail=n-1, pos;
	for(int i=0; i<n; i++) {
		order[(i%2==0) ? head++ : tail--] = i;
	}
	return order;
}



Raynes's Clojure Versions


(defn sideways-sort [aseq]
  (reduce
   (fn [acc [f x]] (f x acc)) []
   (partition 2 (interleave
                 (cycle [cons #(concat %2 [%])])
                 (sort #(if (= 1 (compare % %2)) 0 1) aseq)))))



(defn loop-s-sort [aseq]
  (loop [x (sort #(if (= 1 (compare % %2)) 0 1) aseq)
         acc []
         cons? true]
    (if (seq x)
      (recur (next x)
             ((if cons? cons #(concat %2 [%])) (first x) acc)
             (not= cons? true))
      acc)))



AdamSpeight2008 vb.net verion
Public Module Module1
  Public Sub Main()
   Dim sr = {1, 3, 5, 9, 4, 7, 2} 
    Dim rr = sr.SidewaysSort()
  End Sub

   <Runtime.CompilerServices.Extension()>
  Public Function SidewaysSort(Of T As IComparable)(ByVal Source As IEnumerable(Of T),
                    Optional ByVal output As IEnumerable(Of T) = Nothing, Optional ByVal s As Boolean = True) As IEnumerable(Of T)
    Return If(Source.Any(),
              If(output Is Nothing,
                 Source.OrderBy(Function(x) x).Reverse.SidewaysSort(Enumerable.Empty(Of T), s),
                 Source.ToArray.Skip(1).SidewaysSort(If(s,
                                                        Source.Take(1).Concat(output),
                                                        output.Concat(Source.Take(1))
                                                        ), Not s)),
                                                  If(output Is Nothing, Enumerable.Empty(Of T)(), output))
 
  End Function
End Module


and C#4 verision
public static IEnumerable<T> SidewaySort< T >(this IEnumerable<T> source, IEnumerable<T> output=null,bool s=true)
   {
     return source.Any()? (output == null) ? 
      source.OrderBy(x => x).Reverse().SidewaySort(Enumerable.Empty<T>(),s) :
       source.Skip(1).SidewaySort( s? source.Take(1).Concat(output) :
        output.Concat(source.Take(1)),!s) :
          output == null? Enumerable.Empty<T>(): output;
   }



baavgai's pyhton version
def strangeSort(a):
	sorted = []
	for i in range(len(a)):
		v = max(a)
		a.remove(v)
		if i%2==0:
			sorted.insert(0,v)
		else:
			sorted.append(v)
	return sorted



Reply with your version.

Is This A Good Question/Topic? 2
  • +

Replies To: Coding Hartbeat

#2 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2267
  • View blog
  • Posts: 9,480
  • Joined: 29-May 08

Re: Coding Hartbeat

Posted 18 July 2010 - 09:54 AM

Another vb.net version
 <Runtime.CompilerServices.Extension()>
  Public Function SidewaysSort(Of T As IComparable)(ByVal Source As IEnumerable(Of T)) As IEnumerable(Of T)
    Dim outt As New LinkedList(Of T)
    Dim s = True
    Source.OrderByDescending(Function(x) x).ToList.ForEach(Sub(X)
                                                             If s Then
                                                               outt.AddFirst(X)
                                                             Else
                                                               outt.AddLast(X)
                                                             End If
                                                             s = Not s
                                                           End Sub)


    Return outt.AsEnumerable

  End Function

Was This Post Helpful? 0
  • +
  • -

#3 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 2044
  • View blog
  • Posts: 4,226
  • Joined: 11-December 07

Re: Coding Hartbeat

Posted 18 July 2010 - 05:42 PM

I think you gave Codebug the credit for my solution:
http://www.dreaminco...ost__p__1065989
Was This Post Helpful? 0
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2267
  • View blog
  • Posts: 9,480
  • Joined: 29-May 08

Re: Coding Hartbeat

Posted 18 July 2010 - 06:12 PM

cfoley The code didn't come from that thread but this one. I edit the original to reflect that.
Codebug Solution
class ArraySort
{
		public static void main( String[] args )
		{
			int[] num = new int[  ]{ 10, 7, 5, 3, 1};

			int middle = num.length/2;

			int[] numTransfer = new int[ num.length ];
			
			for( int i = 0, j = middle + 1, k = middle - 1; i < num.length; i++ )
			{
				if ( i == 0 )
				{
					numTransfer[ middle ] = num[ 0 ];
				}

				else if( i % 2 == 0 )
				{
					numTransfer[ k ] = num [ i ];
					k--;
				}

				else
				{
					numTransfer[ j ] = num [ i ];
					j++;
				}

			}
			
			
		}
} 


Was This Post Helpful? 1
  • +
  • -

#5 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Coding Hartbeat

Posted 18 July 2010 - 08:49 PM

(defn psort [aseq]
  (reduce
   (fn [acc [n pn]] (cons n (if pn (concat acc [pn]) acc)))
   (partition-all 2 (sort #(if (= 1 (compare % %2)) 0 1) aseq))))



This one is my best example. I came up with it after learning about the partition-all function earlier. It's twice as slow as my lower-level and uglier example that uses loop, but extremely faster than the one that uses cycle. I'd appreciate it if you'd put this one at the top of my examples in the gallery because it is by far the best of my examples.
Was This Post Helpful? 0
  • +
  • -

#6 Nikhil_07n  Icon User is offline

  • The cheese stands alone..
  • member icon

Reputation: 49
  • View blog
  • Posts: 2,489
  • Joined: 09-January 09

Re: Coding Hartbeat

Posted 18 July 2010 - 10:14 PM

As a Java beginner with an experience of one week, this is the best that I can do.

	public int[] doIt(int[] arr) {
		int[] res;
		//Code for arranging the members in descending order//
		for(int i=0; i<arr.length;  i++) {
			for(int j=(i+1); j<arr.length; j++) {
				if(arr[j]>arr[i]) {
					int tempVar = arr[j];
					arr[j]=arr[i];
					arr[i]=tempVar;
				}
			}
		}
		
		res= new int[arr.length];
		int counter=0;
		int ORIGIN = (res.length)/2;
		//Code that arranges "anything" in the given pattern. I'm using this to arrange the already-in-descending-order array//
		for(int i=0; i<arr.length; i++) {
			if(counter==0) {
				res[ORIGIN]=arr[i];
				counter++;
			} else {
				res[ORIGIN+counter]=arr[i];
				if(counter>0) {
					counter=counter - (counter*2);
				} else {
					counter=counter + (counter*(-2));
					counter++;
				}
			}
		}
		return res;
	}


P.S. : It works properly only if the number of array elements are odd(a clear mid-point). I'm not sure about the position to use as a mid-point when array elements are even.

This post has been edited by Nikhil_07n: 18 July 2010 - 10:16 PM

Was This Post Helpful? 1
  • +
  • -

#7 sarmanu  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 966
  • View blog
  • Posts: 2,362
  • Joined: 04-December 09

Re: Coding Hartbeat

Posted 18 July 2010 - 11:24 PM

This is my C++ version, works with both vector size even/odd:
#include <iostream>
#include <algorithm>
#include <vector>

size_t getMaxElement(const std::vector<size_t> &v)
{
	return *std::max_element(v.begin(), v.end());
}

void removeElement(std::vector<size_t> &v, size_t const val)
{
	std::vector<size_t>::iterator itr = std::find(v.begin(), v.end(), val);
	v.erase(itr, itr + 1);
}

size_t getMiddle(const std::vector<size_t> &v)
{
	return (!(v.size() % 2)) ? v.size() / 2 - 1 : v.size() / 2;
}

std::vector<size_t> sidewaySort(std::vector<size_t> original)
{
	size_t middle = getMiddle(original);

	std::vector<size_t> sorted;
	sorted.resize(original.size());

	sorted[middle] = getMaxElement(original);
	removeElement(original, getMaxElement(original));

	size_t start = middle - 1, mid = middle + 1;
	size_t originalSize = original.size();
	for (size_t i = 0; i < originalSize; i++)
	{
		size_t maxElem = getMaxElement(original);
		if (!(i % 2))
			sorted[mid++] = maxElem;
		else
			sorted[start--] = maxElem;

		removeElement(original, maxElem);
	}

	return sorted;
}

void output(const std::vector<size_t> &v)
{
	std::copy(v.begin(), v.end(), std::ostream_iterator<size_t>(std::cout, " "));
}

int main()
{
	std::vector<size_t> v;
	v.push_back(1);
	v.push_back(16);
	v.push_back(41);
	v.push_back(33);
	v.push_back(11);
	v.push_back(333);
	v.push_back(33);

	std::vector<size_t> sorted = sidewaySort(v);
	output(sorted);

	return 0;
}


Was This Post Helpful? 0
  • +
  • -

#8 PsychoCoder  Icon User is offline

  • Google.Sucks.Init(true);
  • member icon

Reputation: 1641
  • View blog
  • Posts: 19,853
  • Joined: 26-July 07

Re: Coding Hartbeat

Posted 19 July 2010 - 12:09 AM

So, has anyone come up with the official sort algorithm you're working with? I've seen Sideways Sort (found nothing on it) and strangesort (found nothing on it).
Was This Post Helpful? 0
  • +
  • -

#9 janne_panne  Icon User is offline

  • WinRT Dev
  • member icon

Reputation: 429
  • View blog
  • Posts: 1,047
  • Joined: 09-June 09

Re: Coding Hartbeat

Posted 19 July 2010 - 12:21 AM

Another C# version which seems to have come out quite similar to AdamSpeight's VB.NET LinkedList version:

    class Program
    {
        static void Main(string[] args)
        {
            int[] arr1 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            int[] arr2 = new int[] { 1, 2, 3, 4 };

            Print(arr1);
            Sort(ref arr1);
            Print(arr1);

            Print(arr2);
            Sort(ref arr2);
            Print(arr2);
        }

        public static void Print(int[] arr)
        {
            foreach (int i in arr)
            {
                Console.Write(i + ", ");
            }
            Console.WriteLine("");
        }

        public static void Sort(ref int[] arr)
        {
            Array.Sort<int>(arr);
            Array.Reverse(arr);
            LinkedList<int> lst = new LinkedList<int>();
            for (int i = 0; i < arr.Length; i++)
            {
                if (i % 2 == 0)
                {
                    lst.AddFirst(arr[i]);
                }
                else
                {
                    lst.AddLast(arr[i]);
                }
            }
            arr = lst.ToArray();
        }
    }


Was This Post Helpful? 0
  • +
  • -

#10 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Coding Hartbeat

Posted 19 July 2010 - 01:37 AM

View PostPsychoCoder, on 18 July 2010 - 11:09 PM, said:

So, has anyone come up with the official sort algorithm you're working with? I've seen Sideways Sort (found nothing on it) and strangesort (found nothing on it).


I think Adam called it a "conceptual pyramid sort" or something. It's a pretty easy thing to go about. It's just like a pyramid that goes highest to lowest. Left right left right left right.
Was This Post Helpful? 0
  • +
  • -

#11 GWatt  Icon User is offline

  • member icon

Reputation: 278
  • View blog
  • Posts: 3,078
  • Joined: 01-December 05

Re: Coding Hartbeat

Posted 19 July 2010 - 10:35 AM

Taking advantage of perl arrays being dequeues.

#!/usr/bin/perl

sub psort {

	my @psorted;

	for (my $i = 0; $i < @_; $i++) {
		if ($i % 2 == 0) {
			unshift @psorted, $_[$i];
		}
		else {
			push @psorted, $_[$i];
		}
	}

	return @psorted;
}

for(<STDIN>) {
	push @nums, split(/\s/);
}
@psorted = psort (sort {$b <=> $a} @nums);

printf "@psorted\n";

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1