Program C++: Isih elemen tatasusunan dalam tertib menaik

Untuk menyelesaikan beberapa masalah dengan berkesan, adalah sangat penting untuk menyusun item data pada kedudukan yang betul pesanan. Salah satu masalah pilih atur yang paling popular ialah masalah pesanan elemen. ini Artikel ini akan menunjukkan cara mengisih ahli tatasusunan dalam tertib menaik (mengikut nilai terus meningkat).

Terdapat banyak cara untuk menyusun elemen angka atau bukan angka dalam susunan tertentu Algoritma pengisihan boleh digunakan di kawasan ini. Hanya dua teknik pengisihan mudah akan diperkenalkan dalam artikel ini. Isih pilihan dan isihan gelembung. Mari kita semak satu persatu Laksanakan kod secara individu menggunakan teknologi yang sesuai dan C++.

Gunakan teknik isihan gelembung untuk mengisih tatasusunan dalam tertib menaik

Salah satu cara paling popular dan mudah untuk mengisih komponen tatasusunan ialah Kaedah isihan gelembung. Dalam kaedah ini, dua elemen diperiksa secara berurutan Lihat jika mereka berada dalam susunan yang betul. Jika tidak, kaedah menukar elemen sehingga mereka Perintah itu betul. Selepas itu, bergerak ke kanan dan ulangi proses dengan kumpulan lain nilai. Elemen individu diletakkan pada kedudukan yang dijangkakan pada penghujungnya Setiap daripada beberapa peringkat teknologi pengisihan gelembung. Lihat jenis gelembung algoritma.

Algoritma

• Baca tatasusunan A dan saiz nnya sebagai input
• Untuk i antara 0 hingga n-1, laksanakan
  • Untuk j antara 0 hingga n - 2, laksanakan
    • Jika A[j] > A[j + 1], maka
      • Tukar A[j] dan A[j + 1]
    • Jika ia berakhir
  • Tamat
• Tamat

Contoh

#include <iostream>
using namespace std;
void display( int arr[], int n ){
   for ( int i = 0; i < n; i++ ) {
      cout << arr[i] << ", ";
   }
}
void swap ( int &a, int &b ){
   int temp = a;
   a = b;
   b = temp;
}
void solve( int arr[], int n ){
   int i, j;
   for ( i = 0; i < n; i++ ) {
      for ( j = 0; j < n-1; j++ ) {
         if ( arr[j] > arr[ j+1 ] ) {
            swap( arr[j], arr[ j + 1 ] );
         }
      }
   }
}
int main(){
   int arr[] = {8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84};
   int n = sizeof( arr ) / sizeof( arr[0] );
   cout << "Array before sorting: ";
   display(arr, n);
   solve( arr, n );
   cout << "\nArray After sorting: ";
   display(arr, n);
}

Output

Array before sorting: 8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84, 
Array After sorting: 2, 5, 8, 10, 12, 12, 25, 36, 44, 45, 58, 63, 74, 78, 84, 89, 95, 96, 

Isih tatasusunan dalam tertib menaik menggunakan teknik isihan pemilihan

Apabila menggunakan strategi isihan pemilihan, kita bermula dari indeks I dan pergi ke penghujung Diberi tatasusunan, cari elemen minimum atau maksimum. Andaikan kita Dedahkan setiap ramuan. Ia menempatkan elemen terkecil dari indeks I hingga akhir Pada setiap peringkat, letakkan elemen di tempatnya dan ulangi proses itu Cari elemen terbesar seterusnya daripada indeks I + 1, dan seterusnya. Tahap-tahap ini hampir selesai, Kemudian keseluruhan tatasusunan akan diisih dengan sewajarnya.

Algoritma

• Baca tatasusunan A dan saiz nnya sebagai input
• Untuk i antara 0 hingga n-1, laksanakan
  • ind := Indeks unsur terkecil dari i ke n dalam A
  • Jika A[ i ] > A[ ind ], maka
    • Pertukaran A[ i ] dan A[ ind ]
  • Jika ia berakhir
• Tamat

Contoh

#include <iostream>
using namespace std;
void display( int arr[], int n ){
   for ( int i = 0; i < n; i++ ) {
      cout << arr[i] << ", ";
   }
}
void swap ( int &a, int &b ){
   int temp = a;
   a = b;
   b = temp;
}
int min_index( int arr[], int n, int s, int e ){
   int min = 99999, min_ind = -1;
   for ( int i = s; i < e; i++ ) {
      if ( arr[i] < min ) {
         min = arr[i];
         min_ind = i;
      }
   }
   return min_ind;
}
void solve( int arr[], int n ){
   int i, j, ind;
   for ( i = 0; i < n; i++ ) {
      ind = min_index( arr, n, i, n );
      if ( arr[i] > arr[ ind ] ) {
         swap( arr[i], arr[ ind ] );
      }
   }
}
int main(){
   int arr[] = {8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84};
   int n = sizeof( arr ) / sizeof( arr[0] );
   cout << "Array before sorting: ";
   display(arr, n);
   solve( arr, n );
   cout << "\nArray After sorting: ";
   display(arr, n);
}

Output

Array before sorting: 8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84, 
Array After sorting: 2, 5, 8, 10, 12, 12, 25, 36, 44, 45, 58, 63, 74, 78, 84, 89, 95, 96, 

KESIMPULAN

Masalah asas ialah menyusun, yang melibatkan penyusunan nombor atau item lain mengikut susunan Logik susun atur yang telah ditetapkan. Terdapat banyak teknik penjujukan lain yang terdapat dalam bidang ini, Tetapi dalam artikel ini, kami akan memfokuskan pada dua yang mudah digunakan dan difahami. dua ini Teknik pengisihan termasuk teknologi pengisihan pemilihan dan teknologi pengisihan gelembung. kita ada Gunakan kedua-dua teknik ini untuk menyusun set data dalam susunan menaik (bukan menurun). Walaupun tidak begitu cekap masa, kedua-dua teknik pengisihan ini adalah mudah. kedua-duanya Kedua-dua teknik memerlukan pelaburan masa O(n²), di mana n adalah masuk. Selagi dinilai sama ada terdapat perubahan, tidak akan ada perubahan pada peringkat seterusnya Tiada pertukaran pada mana-mana peringkat, menjadikan buih diisih lebih cepat.

Atas ialah kandungan terperinci Program C++: Isih elemen tatasusunan dalam tertib menaik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!