Problem of the Day -- Pyramid Sort

Pyramid Sort

The pyramids of Egypt are some of the most fascinating structures in the world. To honor the great pyramids we'll be introducing pyramid sort. Pyramid sort works so that the highest numbers are in the center of the array and the lowest are on the edges. When comparing 2 numbers the smaller number goes on the left. So if the array contains 1,2,3 then 1 goes on the left with 2 on the far right and 3 in the middle. Here are 2 more examples:

> psort([1,2,3,4,5])
[1,3,5,4,2]

> psort([1,3,5,7,9,11])
[1,5,9,11,7,3]

Permalink: http://problemotd.com/problem/pyramid-sort/

Comments:

Karl T - 10 years ago

Here's my attempt. It might be a little cheating because C# has an Array.Sort function if using Linq, but it was still hard to get the logic for alternating the array index right.

using System;
using System.Linq;

namespace PyramidSort
{
    internal class Program
    {
        private static void Main()
        {
            string strNums; //The input by the user
            string[] arrayNumString; //The array of nums to loop through

            int[] arrayNumInts; //Converted array
            int[] arrayPyramidSortedList; //New array

            Console.WriteLine("Enter a set of numbers separated by commas, then hit enter.");

        GoAgain:
            strNums = Console.ReadLine();

            Console.Clear();

            if (strNums.Trim() == "")
            {
                Console.WriteLine("You gotta give me something to work with!");

                goto GoAgain;
            }

            arrayNumString = strNums.Split(',');

            Console.WriteLine("Numbers entered:\t" + string.Join(", ", arrayNumString));

            try
            {
                arrayNumInts = arrayNumString.Select(x => int.Parse(x.Trim())).ToArray();

                //Console.WriteLine("Regular sorted list:\t" + string.Join(", ", arrayNumInts.Select(x => x.ToString()).ToArray()));

                arrayPyramidSortedList = PyramidSort(arrayNumInts);

                Console.WriteLine("Pyramid sorted:\t\t" + string.Join(", ", arrayPyramidSortedList.Select(x => x.ToString()).ToArray()));

            }
            catch (Exception ex)
            {
                Console.WriteLine("Error: " + ex.ToString());
            }

            Console.WriteLine();
            Console.WriteLine("Enter another set of numbers if you want, or hit escape to quit.");

            goto GoAgain;
        }

        private static int[] PyramidSort(int[] inArray)
        {
            Array.Sort(inArray);

            int[] arrayPyramidSortedList = new int[inArray.Length];

            int intSecondIndex = 0;
            int tally = 0;

            for (int i = 0; i < inArray.Length; i++)
            {
                //We want the order of intSecondIndex to be 0, arraylen, 1, arraylen-1, 2, arraylen-2, etc.
                if ((i + 2) % 2 == 0) //Every other, since first i == 0, i + 2 == 2, and 2 % 2 == 0
                {
                    intSecondIndex = tally;
                }
                else
                {
                    intSecondIndex = (inArray.Length - tally++) - 1;
                }

                arrayPyramidSortedList[intSecondIndex] = inArray[i];
            }

            return arrayPyramidSortedList;
        }
    }
}

reply permalink

Tom - 10 years ago

Here is my Java solution.

/** * PyramidSort.java */

import java.util.Scanner; import java.util.ArrayList; import java.util.Arrays;

public class PyramidSort{ private static int [] nums;

public static void main(String[] args){
ArrayList<Integer> list = new ArrayList<Integer>();
Scanner sc = new Scanner(System.in);

while(sc.hasNextInt()){
    list.add(sc.nextInt());
}
nums = new int[list.size()];
for(int i: list){
    nums[list.indexOf(i)] = i;
}
System.out.println(Arrays.toString(pSort(nums)));
}

public static int[] pSort(int[] arr){
int[] result = new int[arr.length];
int startindex = 0;
int endindex = arr.length -1;
boolean side = true;
while(!isEmpty(arr)){
    int smallest = 100000000;
    for(int j: arr){
    if(j < smallest && j != 0){
        smallest = j;
    }
    }

    arr[getIndex(arr, smallest)] = 0;
    if(side){
    result[startindex++] = smallest;
    side = !side;
    }
    else{
    result[endindex--] = smallest;
    side = !side;
    }
}
return result;
}

public static boolean isEmpty(int[] a){
for(int i: a){
    if(i != 0){
    return false;
    }
}
return true;
}

public static int getIndex(int[] ar, int item){
int index = 0;
for(int i: ar){
    if(i == item){
    return index;
    }
    else{
    index++;
    }
}
return -1;
}

}

reply permalink

Tom - 10 years ago
apologys for the layout there, I don't know how to post my code properly on this site.

reply permalink
Max Burstein - 10 years ago

The site uses Github flavored markdown so this is how you can format your code https://help.github.com/articles/github-flavored-markdown#fenced-code-blocks

Thanks for the submission!

reply permalink

Zigo - 10 years ago

Here's something in Python. I think it could be simpler, but after using C for so long wrapping my head around this language is impossible.

def main():
    inputString = raw_input('Enter your input array, space delimited: ')
    inputArray = map(int, inputString.split())

    print psort(inputArray)

    raw_input('Press <ENTER> to continue')



def psort(array):

    array.sort()
    n = 0
    pyrArray = []
    index = 0

    while len(array) > 0:
        if n == 0:
            pyrArray.insert(index, array.pop(0))
            index += 1
            n = 1
        else:
            pyrArray.insert(len(pyrArray) - index, array.pop(0))
            n = 0

    pyrArray.reverse()

    return pyrArray


if __name__ == "__main__":
    main()

reply permalink

Heroka - 10 years ago

My attempt in R:

psort <- function(d){
  sorted = sort(d)
  length_s = length(sorted)
  #arrange; differs for arrays of even and odd length
  if(length_s%%2==0){
    pyramid = sorted[c(seq(1,length_s,by=2), seq(length_s,2,by=-2))]
  }else{
    pyramid = sorted[c(seq(1,length_s,by=2), seq(length_s-1,2,by=-2))]
  }
  return(pyramid)
}

reply permalink

Anonymous - 10 years ago

In J the solution is quite short:

psort=: ,`(,~)/@:/:~

And to show that it works (NB. is a comment in J):

psort 1 2 3 4 5     NB. => 1 3 5 4 2
psort 1 3 5 7 9 11  NB. => 1 5 9 11 7 3
psort ? $~ 25       NB. => 0 2 4 4 6 8 9 11 11 12 13 16 20 19 15 13 12 11 11 9 6 5 4 3 1

reply permalink

Anonymous - 10 years ago
By the way, Max, I'm not sure the problem description is correct for an even number of integers. In your second example,
```
[1, 5, 9, 11, 7, 3]
```
11 is at the top, 9 left of it, 7 right of it. But shouldn't 9 be on the right hand side?

reply permalink
Max Burstein - 10 years ago

9 vs 11 is how it would break down for the even case. Since 9 is the smaller number it goes to the left.

reply permalink
Anonymous - 10 years ago
Ah, right, I figured the pyramid should always have a single 'peak'. Thanks.

reply permalink

Anonymous - 10 years ago

Fixed.

psort=: (,`(,~)/)`(,~`,/)@.(0 = 2 | #) @: /:~

And the result:

psort 1 2 3 4 5     NB. => 1 3 5 4 2
psort 1 3 5 7 9 11  NB. => 3 7 11 9 5 1

Thanks for the challenge!

reply permalink

Pearce Keesling - 10 years ago

Sometimes it amazes me just how long it takes to write things in C, I could probably have written this in a few lines in Ruby, but just the formatting alone takes a collective 20 lines.

If anyone has any advice on how to do formatting more efficiently, I'm all ears :)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void reverse(int* ary, int size)
{
    int buff[size];
    int* b = buff;
    for(int* i = ary+size-1;i>=ary;i--)
    {
        *b = *i;
        b++;
    }
    memcpy(ary,buff,size*sizeof(int));
}

int compare(const void *a, const void *b)
{
    return (*(int*)a - *(int*) b);
}

void psort(int* nums, int size)
{
    qsort(nums,size,sizeof(int),compare);
    int d = (size%2==0?0:1);
    int first[size/2+d];
    int second[size/2];
    for(int i = 0;i <size;i++)
    {
        first[i/2] = nums[i];
        i++;
        if(i>=size)break;
        second[i/2] = nums[i];
    }
    memcpy(nums,first,sizeof(first));
    reverse(second,sizeof(second)/sizeof(int));
    memcpy(nums+sizeof(first)/sizeof(int),second,sizeof(second));
}
int main(int argc, char* argv[])
{
    int count = 1;
    for(char* c = argv[1];c<argv[1]+strlen(argv[1]);c++)
    {
        if(*c==',') count++;
    }
    int ary[count];
    int* p = ary;
    int buff = 0;
    for(char* c = argv[1];c<argv[1]+strlen(argv[1]);c++)
    {
        if(*c >=48 && *c<=57)
        {
            buff = buff * 10 + (*c-48);
        }else if(*c ==',')
        {
            *p = buff;
            p++;
            buff = 0;
        }
    }
    *p = buff;
    psort(ary,sizeof(ary)/sizeof(int));
    char out[10*sizeof(ary)/sizeof(int)];
    sprintf(out,"[");
    for(int* i = ary; i < ary + sizeof(ary)/sizeof(int);i++)
    {
        char buff[11];
        sprintf(buff,"%d,",*i);
        strncat(out,buff,10);
    }
    int len = strlen(out);
    out[len-1] = ']';
    printf("%s\n",out);
    return 0;
}

reply permalink

tl300 - 10 years ago

Possible, quick solution in Python...

import random

def psort(numbers):
    sorted_numbers = []
    flip_flop = len(numbers) % 2 != 0
    for n in sorted(numbers, reverse=True):
        if not sorted_numbers:
            sorted_numbers.append(n)
        else:
            if flip_flop:
                sorted_numbers.append(n)
            else:
                sorted_numbers.insert(0, n)
            flip_flop = not flip_flop
    return sorted_numbers

# Given test cases
print psort([5, 4, 3, 2, 1])
print psort([1,3,5,7,9,11])

# Random test case
numbers = [random.randrange(1, 10) for n in xrange(0, 5)]
print psort(numbers)

reply permalink

Hueho - 10 years ago

Easy mode: pre-sorting the array in crescent order, and swapping consecutive elements until it reached the mirrored equivalente to the original position.

Essentially bubblesort, but dumber.

# Adding swap method to Array class for convenience
class Array
  def swap i, j
    return self if i.nil? or j.nil?
    self[i], self[j] = self[j], self[i]
    self
  end
end

# Pretty much a bubble sort which doesn't go all the way down
module Second # There used to be a "first" - it was bad
  def self.psort(arr)
    result = arr.sort
    len = result.size

    (1...len).each do |i|
      (i..(len - i)).each_cons(2) do |j, k|
        result.swap j, k
      end
    end

    return result
  end
end

reply permalink

Anonymous - 10 years ago

Simple (but inefficient) Python:

def psort(lst):
    if len(lst) <= 1:
        return lst
    a = sorted(lst)
    return [a[0]] + psort(lst[2:]) + [a[1]]

print(psort([1,2,3,4,5]))
print(psort([1,3,5,7,9,11]))

reply permalink

Zach - 10 years ago

I took some time to make it output in a really nice pyramidal shape.

    static int RANDOM_NUMS = 25;

    public static void Main (string[] args)
    {
        Console.WriteLine ("Generating {0} random numbers:", RANDOM_NUMS);
        Random rng = new Random ();

        int[] randoms = new int[RANDOM_NUMS];
        int[] final = new int[RANDOM_NUMS];

        for (int i = 0; i < RANDOM_NUMS; i++) {
            randoms[i] = rng.Next (100);
        }
        Array.Sort (randoms);

        Console.WriteLine ("After sorting the numbers are:");

        for (int i = 0; i < RANDOM_NUMS; i++) {
            Console.Write (randoms [i] + "\t");
        }

        Console.WriteLine ("\nPretty picture incoming:\n");

        for (int i = 0; i < RANDOM_NUMS; i++) {
            string spacing = "";

            if (i % 2 == 0) {
                final [i/2] = randoms [i];
                for (int j = 0; j < i/2; j++) {
                    spacing += "  ";
                }
                Console.Write ("{0}{1}", spacing, randoms [i]);
            } else {
                final [RANDOM_NUMS - (i+1)/2] = randoms [i];
                for (int j = 0; j < RANDOM_NUMS - i; j++) {
                    spacing += "  ";
                }
                Console.WriteLine ("{0}{1}", spacing, randoms [i]);
            }
        }
    }
}

reply permalink

Bill Bejeck - 10 years ago

Here's a solution in Java. /** * Assumes input is already sorted in ascending order and * a ',' delimited String */ public class PyramidSort {

public static void main(String[] args) throws Exception {

    String input;
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    input = reader.readLine();
    while (!input.toLowerCase().startsWith("q")) {

        int[] nums = convert.apply(input.split(","));

        int[] pyr = new int[nums.length];
        for (int i = 0, j=0; i < nums.length - 1; i+=2,j++) {
            pyr[j] = nums[i];
            pyr[(pyr.length - 1) - j] = nums[i + 1];
        }
        pyr[pyr.length / 2] = nums[nums.length - 1];
        System.out.println(Arrays.toString(pyr));
        input = reader.readLine();
    }
}

private static Function<String[], int[]> convert = (s) -> {
    int[] n = new int[s.length];
    int index = 0;
    for (String si : s) {
        n[index++] = Integer.parseInt(si);
    }
    return n;
};

}

reply permalink

Mre64 - 9 years, 10 months ago

/* Mre64 6/11/14

“I'm not dumb. I just have a command of thoroughly useless information.” 
    ― Bill Watterson

/ import java.util.;

public class PryamidSort {

public static void main(String[] args) {
    //list holds first half of data set
    List<Integer> firstHalf = new ArrayList<Integer>();
    //this list holds the second half of the data set
    List<Integer> secondHalf = new ArrayList<Integer>();
    //this list holds the end result of the pyramid
    List<Integer> pyramidSo = new ArrayList<Integer>();
    // holds the numbers to sort
    int[] pyramid = {1,22,3,17,5,6,14,8,900,10,11,12,13,7};
    // call the Pyramid sort method
    pyramidSort(pyramid, pyramidSo, firstHalf, secondHalf);
}

public static void pyramidSort(int[] pyramid, List<Integer> pyramidSo, List<Integer> first, List<Integer> second){
    //sort the data before handling algorithm
    Arrays.sort(pyramid);
    // this loop holds to values, which choose to pick the even or odd elements of the array
    for(int i = 0, j = 1; i < pyramid.length; i = i + 2, j = j + 2){
        //add the even elements to first list AKA --> [0] = 1, [2] = 3, [4] = 5 <--
        first.add(pyramid[i]);
        //add the odd elements to second list AKA --> [1] = 2, [3] = 4, [5] = 6 <--
        second.add(pyramid[j]);
    }
    //reverse the second list
    Collections.reverse(second);
    //add both lists together to get pyramid
    pyramidSo.addAll(first);
    pyramidSo.addAll(second);
    //print results
    System.out.println(pyramidSo);
}

}

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Pyramid Sort

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri