Penyegaran algoritma. Mengapa heapsort merupakan algoritma insort?

Saya tidak bisa melihat mengapa heapsort dianggap sebagai algoritma penyortiran inplace .

Maksud saya struktur data ekstra diisi dengan elemen-elemen array yang akan diurutkan yaitu heap, digunakan untuk membantu dalam ekstraksi nilai min dan proses penyortiran.

Jadi mungkin saya salah paham definisi inplace di sini?

Tetapi jenis penyisipan misalnya jelas bahwa itu adalah algoritma inplace, yaitu tidak ada memori tambahan yang diperlukan untuk elemen.

Jadi mengapa itu dianggap tidak benar?

Maksud saya struktur data ekstra diisi dengan elemen-elemen array yang akan diurutkan yaitu heap, digunakan untuk membantu dalam ekstraksi nilai min dan proses penyortiran.

Tidak. Array ditransformasikan agar sesuai dengan batasan heap tanpa menggunakan lebih dari O (1) memori tambahan. (Sebenarnya yang Anda butuhkan adalah memori tambahan yang cukup untuk menampung satu elemen array, untuk tujuan swap, ditambah satu atau dua boolean dan satu atau dua variabel loop).

Ok, secara teknis mungkin heapsort biasanya dijelaskan menggunakan heap terpisah, tetapi sangat mungkin untuk mengimplementasikannya di tempat.

Anda mungkin kehilangan pemahaman mendasar bahwa array dapat digunakan untuk menentukan tata letak pohon.

Misalkan Anda memiliki pohon biner, dan simpul interior berada pada indeks i dari array. Kemudian indeks array dari orang tua dan anak-anak dari simpul itu dapat ditemukan oleh:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

Lihat:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Karena heap dapat disimpan dan diatur seluruhnya dalam sebuah array, maka heapsort dapat berjalan di tempat dengan menggerakkan elemen-elemen di dalam array input. Memang, heap dibangun dan dimanipulasi menggunakan array input asli.

Jika, seperti yang Anda katakan, seseorang benar-benar membutuhkan struktur tambahan untuk membangun heap maka heapsort TIDAK akan menjadi algoritma pengurutan inplace.

Namun, ini bukan masalahnya. Anda dapat membangun heap pada array yang sama seperti yang Anda inginkan, dan setelah itu Anda menerapkan algoritma heapsort, jadi itu semacam inplace.

Dalam ilmu komputer, algoritma in-place (atau dalam bahasa Latin in situ) adalah algoritma yang mengubah input menggunakan struktur data dengan jumlah ruang penyimpanan ekstra yang kecil dan konstan. Input biasanya ditimpa oleh output saat algoritma dijalankan. Algoritma yang tidak di tempat kadang-kadang disebut tidak di tempat atau di luar tempat.

Wikipedia - Algoritma in-place

Ini dianggap ada karena persyaratan ruangnya dapat diabaikan (konstan atau tidak sama sekali jika Anda menggunakan operasi bitwise untuk menukar item). MergeSort, misalnya, tidak ada di tempat karena set input tidak diubah di setiap iterasi dari contoh pencarian.

Cara terbaik untuk menggambarkan perbedaan antara algoritma in-place dan algoritma out-of-place mungkin dengan melihat kode pembalikan string C / C ++ berikut yang membuatnya ada di tempat (dari K&R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

Jika Anda, misalnya, membaca string input dari ujung dan menempatkan karakter dalam buffer lain, itu akan menjadi algoritma pembalikan string out-of place.