Comp Sci Which number was used as a pivot?

[chwala]

Homework Statement

Consider the following array of numbers $[ 17,33,14,25,23,28,21,13,9,6,10]$? which number was used as the pivot?

supposing we had say, $[ 17,33,14,25,12,28,21,13,9,6,15]$? Then how would we find the pivot?

secondly, apply the first-fit decreasing bin packing algorithm to the fully sorted list into bins of size $85$.

Relevant Equations

algorithms.

Okay i know the answer as indicated on ms ...i just want to check if there is a general rule for finding the number used as the pivot?

 

[chwala]

this part is straightforward.

for bin we have ...firstly, the fully sorted list as $[33, 28, 25,23, 21,17,14, 13,10,9,6]$

how bins work, $[85-33=52, 52-28=24, 24-23=1]$,

therefore,

$bin_1 = (33, 28, 23)$

$bin_2 = (25, 21, 17, 14, 6)$

$bin_3= (13, 10, 9)$

 

[pbuk]

supposing we had say, $[ 17,33,14,25,12,28,21,13,9,6,15]$? Then how would we find the pivot?

The pivot for what?

 

[chwala]

The pivot for what?

For the numbers indicated on that list. For the first arrangement it is clear that the number that was used as a pivot is $13$.

 

[pbuk]

For the numbers indicated on that list.

For doing what with the numbers indicated on that list?

The word "pivot" only means something in the context of certain algorithms, please explain what algorithm you are using that involves a pivot.

Note in particular that the first-fit decreasing bin packing algorithm does not have a pivot.

For the first arrangement it is clear that the number that was used as a pivot is $13$.

Is it? How?

 

[chwala]

For doing what with the numbers indicated on that list?

The word "pivot" only means something in the context of certain algorithms, please explain what algorithm you are using that involves a pivot.

Note in particular that the first-fit decreasing bin packing algorithm does not have a pivot.


Is it? How?

From ms again. I'll post the Ms here again for your reference.

 

[Mark44]

Okay i know the answer as indicated on ms

I'll post the Ms here again for your reference.

I'm going to guess, without knowing for sure, that "ms/Ms" is an abbreviation for "mark scheme." As far as I know this is not a widely used acronym. I've only ever seen it used by you. It's best to minimize acronyms that aren't well known so as to decrease confusion amongst readers.

I'm aware of quite a few sorting algorithms, but bin packing is not one of them. The closest I can come to it is the Knapsack Problem (https://en.wikipedia.org/wiki/Knapsack_problem) which may or may not be related. Since I wasn't familiar with bin packing, I found an entry for it, in several variations, on wikipedia. I didn't see the term "pivot" used in any of them. I believe @pbuk was asking about this as well.

 

[chwala]

Okay, this was the question

 

[Mark44]

With the full question shown, it turns out that the term pivot didn't have anything to do with bin packing, but it was relevant to quick sort.
After the first pass, and since the list should ultimately be sorted into decreasing order, the pivot should be such that all the numbers in the left part should be larger than the pivot, and all numbers to its right should be smaller. Evidently, 13 was used as the pivot.