Jak posortować tablicę przy użyciu minimalnej liczby zapisów?

Question

Mój przyjaciel otrzymał pytanie w swoim wywiadzie:

Przeprowadzający wywiad dał mu szereg niesortowanych liczb i poprosił go o posortowanie. Ograniczeniem jest to, że liczba zapisów powinna być zminimalizowana, podczas gdy nie ma ograniczeń co do liczby odczytów.

Answer 1

Jeśli macierz jest krótsza (tj. Mniej niż około 100 elementów), to często najlepszym wyborem jest opcja Selection sort, jeśli użytkownik chce zmniejszyć liczbę zapisów.

Z Wikipedii:

Inną kluczową różnicą jest to, że wybór sortowania zawsze wykonuje Θ (n) swapy, natomiast Sortowanie przez wstawianie wykonuje Θ (n) zamienia się w średniej i najgorsze przypadki . Ponieważ zamiany wymagają zapisania do tablicy , sortowanie według wyboru to preferowane, jeśli zapis do pamięci jest znacznie droższy niż odczyt z . Zwykle ma to miejsce, gdy elementy są ogromne, ale klucze są małe. Innym przykładem, w którym kluczowe znaczenie ma wpisanie , jest tablica zapisana w pamięci EEPROM lub Flash w postaci . Nie ma innego algorytmu z mniejszym przepływem danych.

Dla większych tablic/list Quicksort i znajomi zapewnią lepszą wydajność, ale nadal mogą potrzebować więcej zapisów niż sortowanie.

Jeśli jesteś zainteresowany this is a fantastic sort visualization site, który pozwala ci oglądać określone algorytmy sortowania, wykonywać swoją pracę, a także "ścigać się" z różnymi algorytmami sortowania względem siebie.

Answer 2

Jeśli liczby znajdują się w określonym zakresie, zadanie może zostać wykonane w czasie O (n), który jest szczególnym przypadkiem zamawiania, jego wykonanie polega na utworzeniu tablicy i przypisaniu każdej liczby do określonej pozycji.

Jeśli liczby nie należą do zakresu, najlepszym sposobem na to jest użycie QuickSort lub HeapSort, które sortują int O (Log2N), ale niektóre preferują QuickSort, tak jak ja.

Możesz znaleźć implementację QuickSort w dowolnym języku w niemal każdym miejscu, wystarczy go Google, a znajdziesz ją w kilka sekund.

Adaptacja HeapSort jest dostępna podczas organizowania danych zewnętrznych, czyli danych, których nie ma w pamięci, ale na dysku twardym, najczęściej występujących w przypadku ogromnych tablic.

Mam nadzieję, że mogę pomóc Pozdrawiam i powodzenia!

Answer 3

Możesz użyć bardzo naiwnego algorytmu, który spełnia to, czego potrzebujesz.

Algorytm powinien wyglądać następująco:

i = 0 

do 
    search for the minimum in range [i..n) 
    swap a[i] with a[minPos] 
    i = i + 1 
repeat until i = n. 

Poszukiwanie minimum może kosztować prawie nic, swap kosztuje 3 pisze, I ++ kosztuje 1 ..

ten został nazwany selection sort zgodnie z popiołem.(Przepraszam, nie wiedziałem, że to sortowanie sort :()

Answer 4

Porządek, który miałem na myśli w O (n), jest podobny do sortowania (poprzedni post), przydatny, gdy masz mały zakres klawiszy (lub zamawiasz numery między 2 zakresami)

Jeśli masz tablicę liczbową, gdzie liczby będą zawierać się w przedziale od -10 do 100, możesz utworzyć tablicę składającą się z 110 i upewnić się, że wszystkie liczby zmieszczą się tam, jeśli rozważasz powtórzenie numery idea jest taka sama, ale trzeba będzie list zamiast liczb w posortowanej tablicy

pseudo-idea jest tak

N: max value of your array 
tosort //array to be sorted 
sorted = int[N] 

for i = 0 to length(tosort) 
do 
    sorted[tosort[i]]++; 
end 

finalarray = int[length(tosort)] 

k = 0 
for i = 0 to N 
do 
    if (sorted[i] > 0) 
    finalarray[k] = i 
    k++; 
    endif 
end 

finalarray będzie mieć ostatnią posortowaną tablicę, a będziesz miał operacje zapisu o (N), gdzie N jest zakresem macierzy. Ponownie jest to przydatne, gdy używasz kluczy w określonym zakresie, ale być może jest to Twoja sprawa.

Pozdrawiamy i powodzenia!

Answer 5

Jednym rozwiązaniem dla dużych macierzy jest w następujący sposób (zakładając, że elementy n)

1. zainicjować tablicę z n elementów numerach 0..n 1
2. sortowania tablicy przy użyciu dowolnego algorytmu sortowania. Jako funkcja porównania, porównaj elementy w zestawie wejściowym z odpowiednimi liczbami (np., Aby porównać 2 i 4, porównaj 2. i 4. elementy w zestawie wejściowym). To zmienia tablicę z kroku 1 w permutację, która reprezentuje posortowaną kolejność zestawu wejściowego.
3. Powtórz te elementy w permutacji, wypisując bloki w kolejności określonej przez tablicę. Wymaga to dokładnie n pisze, minimum.

Aby posortować w miejscu, w kroku 3 należy zamiast tego zidentyfikować cykle w permutacji i "obrócić" je w razie potrzeby, aby uzyskać posortowaną kolejność.

Answer 6

Sortowanie zaznaczeń to nie prawy algorytm tutaj. Sortowanie zaznaczeń spowoduje zamianę wartości, co daje do dwóch zapisów na wybór, dając maksymalnie 2n zapisów na sortowanie.

Algorytm, który jest dwa razy lepszy od sortowania selekcji, to "cycle" sort, który nie ulega zamianie. Sortowanie cyklu daje maksymalnie n zapisów na sort. Liczba zapisów jest absolutnie zminimalizowana. Napisze numer tylko raz do miejsca docelowego i tylko wtedy, gdy jeszcze go tam nie ma.

Opiera się na idei, że all permutations are products of cycles i można po prostu przejść przez każdy cykl i napisać każdy element na jego właściwe miejsce tylko raz.

import java.util.Random; 
import java.util.Collections; 
import java.util.Arrays; 

public class CycleSort { 
    public static final <T extends Comparable<T>> int cycleSort(final T[] array) { 
    int writes = 0; 

    // Loop through the array to find cycles to rotate. 
    for (int cycleStart = 0; cycleStart < array.length - 1; cycleStart++) { 
     T item = array[cycleStart]; 

     // Find where to put the item. 
     int pos = cycleStart; 
     for (int i = cycleStart + 1; i < array.length; i++) 
     if (array[i].compareTo(item) < 0) pos++; 

     // If the item is already there, this is not a cycle. 
     if (pos == cycleStart) continue; 

     // Otherwise, put the item there or right after any duplicates. 
     while (item.equals(array[pos])) pos++; 
     { 
     final T temp = array[pos]; 
     array[pos] = item; 
     item = temp; 
     } 
     writes++; 

     // Rotate the rest of the cycle. 
     while (pos != cycleStart) { 
     // Find where to put the item. 
     pos = cycleStart; 
     for (int i = cycleStart + 1; i < array.length; i++) 
      if (array[i].compareTo(item) < 0) pos++; 

     // Put the item there or right after any duplicates. 
     while (item.equals(array[pos])) pos++; 
     { 
      final T temp = array[pos]; 
      array[pos] = item; 
      item = temp; 
     } 
     writes++; 
     } 
    } 
    return writes; 
    } 

    public static final void main(String[] args) { 
    final Random rand = new Random(); 

    final Integer[] array = new Integer[8]; 
    for (int i = 0; i < array.length; i++) { array[i] = rand.nextInt(8); } 

    for (int iteration = 0; iteration < 10; iteration++) { 
     System.out.printf("array: %s ", Arrays.toString(array)); 
     final int writes = cycleSort(array); 
     System.out.printf("sorted: %s writes: %d\n", Arrays.toString(array), writes); 
     Collections.shuffle(Arrays.asList(array)); 
    } 
    } 
} 

Kilka przykładów biegnie  :

 
array: [3, 2, 6, 1, 3, 1, 4, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6 
array: [1, 3, 4, 1, 3, 2, 4, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 4 
array: [3, 3, 1, 1, 4, 4, 2, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6 
array: [1, 1, 3, 2, 4, 3, 6, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6 
array: [3, 2, 3, 4, 6, 4, 1, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7 
array: [6, 2, 4, 3, 1, 3, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6 
array: [6, 3, 2, 4, 3, 1, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 5 
array: [4, 2, 6, 1, 1, 4, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7 
array: [4, 3, 3, 1, 2, 4, 6, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7 
array: [1, 6, 4, 2, 4, 1, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7 

 
array: [5, 1, 2, 3, 4, 3, 7, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 5 
array: [5, 1, 7, 3, 2, 3, 4, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6 
array: [4, 0, 3, 1, 5, 2, 7, 3] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 8 
array: [4, 0, 7, 3, 5, 1, 3, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7 
array: [3, 4, 2, 7, 5, 3, 1, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7 
array: [0, 5, 3, 2, 3, 7, 1, 4] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6 
array: [1, 4, 3, 7, 2, 3, 5, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7 
array: [1, 5, 0, 7, 3, 3, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7 
array: [0, 5, 7, 3, 3, 4, 2, 1] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 4 
array: [7, 3, 1, 0, 3, 5, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7