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

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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months ago

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

    reply permalink

  • Max Burstein - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months ago

    Ah, right, I figured the pyramid should always have a single 'peak'. Thanks.

    reply permalink

  • Anonymous - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 6 months 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 - 3 years, 4 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

Content curated by @MaxBurstein