Pomůžete mi prosím se seřazením položek v array? (vyřešeno)

Zkoušela jsem hledat, opravdu, nenašla jsem ale lautr nic :( Děkuji, V.

Domácí úkol nemáš hledat, máš ho vyřešit. Je to cvičení na obecné dovednosti kolem UNIXu a na základy programování, čtení manuálových stránek atd. Pokud bude někdo řešit úkoly za tebe, u zkoušky nebo zápočtového testu přijdou krušné chvíle.

Nespecifikuješ, jestli to musí být efektivní. Předpokládám, že ne. Tak prosím, tady je výstavní kvadratický hnus:

sort_by_number_after_last_slash() {
  local -i -r INT_MAX=9223372036854775807  # 2^63 - 1
  local -n -r input_reference="$1"
  local -n output_reference="$2"
  local -a input=("${input_reference[@]}")
  local -i index sorting_key minimum minimum_index

  for index in "${!output_reference[@]}"; do
    unset output_reference[index]
  done
  while ((${#input[@]} > 0)); do
    minimum=INT_MAX
    for index in "${!input[@]}"; do
      sorting_key="${input[index]##*/}"
      if ((sorting_key < minimum)); then
        minimum=sorting_key
        minimum_index=index
      fi
    done
    output_reference+=("${input[minimum_index]}")
    unset input[minimum_index]
  done
}

A tady je ukázka, jak se to používá (a drobný test, jestli to funguje, jak má):

declare -a unsorted_array=(
  '/foo/bar/1/3/10'
  '/foo/bar/1/3/11'
  '/foo/bar/1/3/18'
  '/foo/bar/1/3/2'
  '/foo/bar/1/3/24'
  '/foo/bar/1/3/25'
  '/foo/bar/1/3/5'
  '/foo/bar/1/3/6'
  '/foo/bar/1/3/8'
  '/foo/bar/1/3/9'
)
declare -a sorted_array=('nonsense, should disappear')

###########################################################
sort_by_number_after_last_slash unsorted_array sorted_array
###########################################################

echo "Original array (must be unchanged):"
for item in "${unsorted_array[@]}"; do
  echo "${item}"
done
echo "Sorted and unsorted array size (must be equal):"
echo "${#sorted_array[@]}" "${#unsorted_array[@]}"
echo "Sorted array (must be ... sorted):"
for item in "${sorted_array[@]}"; do
  echo "${item}"
done

26.2.2019 01:42 Andrej | skóre: 51 | blog: Republic of Mordor
Rozbalit Rozbalit vše Re: Pomůžete mi prosím se seřazením položek v array?

:-D :-D :-D
:-D :-D :-D
:-D :-D :-D

Zapomněl jsem, že řídká pole se iterují v pořadí podle indexů. Takže i tohle by mohlo fungovat. Lepší řídká pole než řídká stolice. (Jenom to nesnese záporná čísla v těch názvech souborů, ale co už.)

sort_by_number_after_last_slash() {
  local -n -r input_reference="$1"
  local -n output_reference="$2"
  local -a input_map
  local item

  for item in "${input_reference[@]}"; do
    input_map["${item##*/}"]="${item}"
  done
  output_reference=()
  for item in "${input_map[@]}"; do
    output_reference+=("${item}")
  done
}

26.2.2019 18:25 Veronika
Rozbalit Rozbalit vše Re: Pomůžete mi prosím se seřazením položek v array?

Díky. Ještě, že umím vařit :-(

26.2.2019 01:59 Andrej | skóre: 51 | blog: Republic of Mordor
Rozbalit Rozbalit vše Re: Pomůžete mi prosím se seřazením položek v array?

Ještě bych dodal, jen tak z prdele, co s tím, kdyby to muselo být efektivní a kdyby to náhodou nesmělo využívat řídká pole v Bashi. #firstworldproblems #becausewecan

Napřed si vyrobíme mergesort na integery:

mergesort() {
  local -n -r input_reference="$1"
  local -n output_reference="$2"
  local -r -i size="${#input_reference[@]}"
  local -a -i merge runs indices
  local -i index previous merged_idx \
           run_a_idx run_a_stop \
           run_b_idx run_b_stop

  output_reference=("${input_reference[@]}")
  if ((size == 0)); then return; fi

  previous=output_reference[0]
  runs=(0)
  for ((index = 0;;)) do
    for ((++index;; ++index)); do
      if ((index >= size)); then break 2; fi
      if ((output_reference[index] < previous)); then break; fi
      previous=output_reference[index]
    done
    previous=output_reference[index]
    runs+=(index)
  done
  runs+=(size)

  while (("${#runs[@]}" > 2)); do
    indices=("${!runs[@]}")
    merge=("${output_reference[@]}")
    for ((index = 0; index < "${#indices[@]}" - 2; index += 2)); do
      merged_idx=runs[indices[index]]
      run_a_idx=merged_idx
      previous=indices[$((index + 1))]
      run_a_stop=runs[previous]
      run_b_idx=runs[previous]
      run_b_stop=runs[indices[$((index + 2))]]
      unset runs[previous]
      while ((run_a_idx < run_a_stop && run_b_idx < run_b_stop)); do
        if ((merge[run_a_idx] < merge[run_b_idx])); then
          output_reference[merged_idx++]=merge[run_a_idx++]
        else
          output_reference[merged_idx++]=merge[run_b_idx++]
        fi
      done
      while ((run_a_idx < run_a_stop)); do
        output_reference[merged_idx++]=merge[run_a_idx++]
      done
      while ((run_b_idx < run_b_stop)); do
        output_reference[merged_idx++]=merge[run_b_idx++]
      done
    done
  done
}

A pak na to klidně napasujeme třídění těch cest k souborům. Míle a míle se táhnou těch cest. Tady už se ale řídká pole používají, ježto se mi to nechtělo řešit jinak, a v tom je ošklivost: Výraz "${!input_map[@]}" dá ty indexy už setříděné, takže následující mergesort krok je úplně k hovnu. Ale to nevadí, když máme ten mergesort tak úžasně efektivní, on se s tím moc párat nebude (1 běh a konec).

sort_by_number_after_last_slash() {
  local -n -r input_reference="$1"
  local -n output_reference="$2"
  local -a -i input output
  local -a input_map
  local item

  for item in "${input_reference[@]}"; do
    input_map["${item##*/}"]="${item}"
  done
  input=("${!input_map[@]}")
  mergesort input output  # na hovno
  echo "${input[@]}"
  echo "${output[@]}"
  output_reference=()
  for item in "${output[@]}"; do
    output_reference+=("${input_map[item]}")
  done
}

Byť je tohle všechno na prd, jako zajímavá ukázka na hraní s Bashem to může být dobré (ten mergesort přinejmenším).

declare -a -i unsorted=(RANDOM RANDOM RANDOM RANDOM RANDOM)
declare -a -i sorted
mergesort unsorted sorted
echo "${unsorted[@]}"
echo "${sorted[@]}"

27.2.2019 09:50 Milan Uhrák | skóre: 31 | blog: milan_at_ABC
Rozbalit Rozbalit vše Re: Pomůžete mi prosím se seřazením položek v array?

Zdravím Andreji, je vidět, že máte bash v malíčku. Kdyby jste měl problém se stravou, Veronika něco naznačovala .. :-D

Snad je opravdová a má to očekávané pohlaví, a ne některé z 64 nebo kolika schválených kajsi západně od našich hranic .. M.

Dotaz: Pomůžete mi prosím se seřazením položek v array?

Odpovědi