Mengurutkan array dalam C ++ menggunakan Bubble sort

Question

Berikut adalah algoritme bubble sort yang ingin saya tingkatkan dengan cara apa pun

#include<iostream>

int main(){
    int arr[6] = {5,2,3,7,2,6};
    int f = 0;
    int b = 0;
    for(int i = 1;i < 6;i++){
        if(arr[i] < arr[i-1]){
            f = arr[i];
            b = arr[i-1];
            arr[i] = b;
            arr[i-1] = f;
            i=1;
        }

    }
    for(int i = 0;i < 6;i++) std::cout << arr[i] << " ";
}

Apa pun dihargai

Answer 1

Beberapa catatan:

• Saya akan menghindari menjalankan loop saat mengubah idi dalam, itu sangat tidak jelas bagi pembaca. Saya lebih suka menggunakan dua loop bersarang.
• Pertukaran dapat dilakukan dalam satu langkah lebih sedikit
• Saya akan menginisialisasi variabel ukuran dan menggunakannya di seluruh kode, bukan hard-coding 6.
• Mencetak array ke konsol harus dalam fungsi terpisah (dan juga fungsi pengurutan).

#include<iostream>

int main(){
    const int sz = 6;
    int arr[sz] = {5,2,3,7,2,6};
    do{
        swapped = false;
        for(int i = 1;i < sz; i++){
            if(arr[i] < arr[i-1]){
                int tmp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = tmp;
                swapped = true;
            }
        }
    } while(swapped);
    print_array(arr, sz);
}

Answer 2

1. Itu salah. Misalnya untuk input yang {5,9,3,7,2,6}Anda cetak 5 2 3 6 7 9.
2. Ini bukan jenis gelembung. Lebih seperti penyisipan yang tidak efisien.
3. Ini bukan O (n ² ) tetapi hanya O (n ³ ). Misalnya untuk input int arr[100] = {99,98,97,...,2,1,0}Anda memiliki 161.799 iterasi loop Anda (itu 100C3 + 99).

Answer 3

Anda tidak menerapkan pengoptimalan yang jelas ke Bubble sort. Jika Anda menjalankan melalui loop dalam dan tidak ada swapping yang dilakukan maka array sekarang diurutkan.

Ini mengurangi kompleksitas "Kasus Terbaik" O(n)daripada O(n^2)yang telah Anda terapkan.

---

Urutan Anda didasarkan pada bilangan bulat. Itu tidak terlalu berguna di C ++ karena array bisa terdiri dari hampir semua hal. Jadi, Anda harus menganggap ini sebagai kemampuan untuk menyortir daftar apa pun.

Tentu Anda mengatakan saya hanya mengubah jenis <int>menjadi sesuatu yang saya inginkan dan kompilasi ulang.

Tentu saya katakan. Tetapi jika Anda memilih jenis Tyang besar kode Anda menjadi sangat tidak efisien karena Anda membuat salinan dari objek tersebut di tengah-tengah perulangan.

    std::array<MyBigType>  arr;

            int tmp = arr[i];  // You made a copy of the object here.
            f = arr[i];        // You made a copy of the object here. 
            b = arr[i-1];      // You made a copy of another object here.

Jadi setiap kali Anda melakukan pertukaran, Anda membuat tiga salinan objek.

Anda dapat melakukan lebih baik dengan menggunakan std::move()untuk memindahkan objek. Atau Anda dapat menggunakan std::swap()atau std::swap_iter()melakukan pekerjaan yang lebih efisien untuk memindahkan benda-benda besar.

---

Kode Anda mengasumsikan bahwa Anda sedang mengurutkan C-array. Di C ++ kami menangani hal-hal secara berbeda, kami memisahkan wadah dengan merujuk hal-hal dengan iterator. Dengan begitu, kita dapat mengurutkan semua jenis container hanya dengan menyediakan iterator.

Sekarang iterator yang berbeda memiliki properti yang berbeda dan Anda berpotensi dapat mengoptimalkan algoritme berdasarkan jenis iterator yang Anda gunakan.

---

Yang terpenting, kode tersebut tidak berfungsi.
Anda hanya memiliki satu putaran. Anda membutuhkan loop bersarang (saya anggap beberapa

Anda melakukan semacam masalah salin tempel! Saya berasumsi itu tidak berhasil karena saya tidak memahami peretasan yang Anda lakukan untuk mensimulasikan loop kedua. Itu masih rusak.

---

Itu ditulis sedemikian rupa sehingga membuatnya sulit untuk dibaca.
Kode dirancang untuk dibaca oleh manusia. Tuliskan kode di tempat yang mudah dibaca.

Answer 4

Saya akan menyarankan untuk menggunakan barang-barang C ++ yang lebih baru setidaknya di mana itu sangat jelas menyederhanakan kode.

1. Itu

            int tmp = arr[i];
            arr[i] = arr[i-1];
            arr[i-1] = tmp;
   

dapat ditulis dalam satu baris, bukan tiga:

            std::swap(arr[i], arr[i-1]);

1. std::array sama dengan larik lama biasa tetapi mengetahui ukurannya sendiri:

            std::array<int,6> arr = {5,2,3,7,2,6};
   

dan kemudian Anda dapat menggunakan arr.size()sebagai ganti kode keras 6 di seluruh kode. Tidak seperti std::vector, std::arrayadalah struktur ringan tanpa bidang internal atau alokasi heap.

1. Untuk mencetak array, loop C ++ 11 sangat berguna:

   for (auto a: arr) std::cout << a << " ";
   

Saya tidak yakin, mungkin meminta untuk menggunakan iterator akan terlalu banyak tetapi mungkin untuk menulis ulang dengan iterator:

  std::array<int,6> arr = {5, 2, 3, 7, 2, 6};

  static_assert(arr.size() >= 2);
  auto current = arr.begin();
  auto prev = current++;

  while (current != arr.end()) {
    if (*current < *prev) {
      std::swap(*current, *prev);
      current = arr.begin();
    }
    prev = current++;
  }

  for (int a: arr) std::cout << a << " ";

Kode ini akan bermanfaat ketika menyortir sesuatu seperti di std::dequemana akses acak arr[i]tidak begitu efisien. Algoritma ini hanya membutuhkan akses langsung ke posisi saat ini dan sebelumnya. Mari kita jadikan ini sisi yang kuat.

static_assertyang saya tambahkan akan gagal pada waktu kompilasi, bukan pada waktu proses, jika lariknya terlalu kecil. Ukuran larik ini dikenal untuk kompiler.