Problem of the Day -- Pyramid Sort

Karl T - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 months 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, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 months ago

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

reply permalink

Anonymous - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 8 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 - 10 years, 6 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

Pyramid Sort

Comments:

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