Problem of the DayA 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 - 4 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;
}
}
}
``````
• Tom - 4 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;
}
``````

}

• Tom - 4 years, 8 months ago

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

• Max Burstein - 4 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!

• Zigo - 4 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()
``````
• Heroka - 4 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)
}
``````
• Anonymous - 4 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
``````
• Anonymous - 4 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?

• Max Burstein - 4 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.

• Anonymous - 4 years, 8 months ago

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

• Anonymous - 4 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!

• Pearce Keesling - 4 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;
}
``````
• tl300 - 4 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)
``````
• Hueho - 4 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
``````
• Anonymous - 4 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]))
``````
• Zach - 4 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]);
}
}
}
}
``````
• Bill Bejeck - 4 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;
};
``````

}

• - 4 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);
}
``````

}

Content curated by @MaxBurstein