Program C++: Isih elemen tatasusunan dalam tertib menurun

Menyusun item data dalam bentuk yang betul adalah tugas penting semasa menyelesaikan beberapa masalah.

cara yang cekap Masalah penyusunan. Dalam artikel ini kita akan melihat cara menyusun elemen tatasusunan Isih mengikut nilai mereka dalam tertib menurun (dalam C++).

Terdapat banyak algoritma pengisihan yang berbeza dalam medan ini untuk mengisih nombor atau bukan nombor

elemen dalam susunan tertentu. Dalam artikel ini, kami akan memperkenalkan hanya dua kaedah mudah pengisihan. Isih gelembung dan isihan pemilihan Mari kita lihat satu persatu dengan betul Algoritma dan kod pelaksanaan C++.

Isih tatasusunan dalam tertib menurun menggunakan teknik isihan gelembung

Teknologi pengisihan gelembung adalah salah satu kaedah pengisihan yang paling biasa dan mudah.

elemen dalam tatasusunan. Kaedah ini menyemak dua elemen bersebelahan jika ia betul tertib, kemudian langkau ke elemen seterusnya, jika tidak, tukar elemen tersebut untuk meletakkannya dengan betul Susun elemen lain mengikut tertib dan kemudian langkau ke elemen seterusnya, jika tidak, tukar elemen tersebut untuk meletakkannya pada kedudukan yang betul perintah. Kemudian bergerak ke arah kanan dan lakukan perkara yang sama untuk pasangan nilai yang lain Susun mengikut urutan. Kemudian bergerak ke kanan dan lakukan perkara yang sama dengan pasangan nilai yang lain. gelembung Teknik pengisihan mempunyai beberapa peringkat, pada akhir setiap peringkat diletakkan elemen Kedudukan jangkaan yang betul. Mari kita lihat algoritma teknik isihan gelembung.

Algoritma

• Baca tatasusunan A dan saiz nnya sebagai input
• Untuk julat i dari 0 hingga n-1, laksanakan
  • Untuk j antara 0 hingga n - 2, lakukan
  • Jika A[j]
  • Tukar A[j] dan A[j + 1]
• Tamat jika

tamat untuk

tamat untuk

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: 96, 95, 89, 84, 78, 74, 63, 58, 45, 44, 36, 25, 12, 12, 10, 8, 5, 2,

Isih tatasusunan dalam tertib menurun menggunakan teknik isihan pemilihan

Dalam teknik isihan pemilihan kita dapati elemen minimum atau elemen maksimum Elemen daripada tatasusunan yang diberikan bermula dari indeks i hingga penghujung tatasusunan ini. Cari unsur terbesar. Dalam setiap peringkat ia mencari nilai minimum dari indeks i hingga akhir, kemudian Letakkan elemen di tempat yang sepatutnya dan cari semula elemen terbesar seterusnya indeks i + 1 dan seterusnya Selepas melengkapkan fasa ini, keseluruhan tatasusunan akan diisih indeks i + 1 dsb. Selepas melengkapkan peringkat ini, keseluruhan tatasusunan akan diisih sewajarnya.

Algoritma

• Baca tatasusunan A dan saiz nnya sebagai input
• Untuk julat i dari 0 hingga n-1, laksanakan
  • ind := indeks unsur terbesar A dari i ke n
  • Jika A[ i ] < A[ ind ], maka
    • Tukar A[i] dan A[ind]
  • Tamat jika
• tamat untuk

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 max_index( int arr[], int n, int s, int e ){
   int max = 0, max_ind = 0;
   for ( int i = s; i < e; i++ ) {
      if ( arr[i] > max ) {
         max = arr[i];
         max_ind = i;
      }
   }
   return max_ind;
}
void solve( int arr[], int n ){
   int i, j, ind;
   for ( i = 0; i < n; i++ ) {
      ind = max_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: 96, 95, 89, 84, 78, 74, 63, 58, 45, 44, 36, 25, 12, 12, 10, 8, 5, 2,

Kesimpulan

Masalah pengisihan ialah masalah asas di mana kita menyusun nombor atau nilai lain

dalam logik pilihatur tertentu. Terdapat banyak teknik pengisihan yang berbeza tersedia di sini memahami dan melaksanakan Dilaksanakan dan mudah difahami. Kedua-dua kaedah ini ialah teknik isihan gelembung dan Teknik pengisihan pemilihan. Menggunakan dua kaedah ini, kami telah mengisih set data Isih menurun (tidak bertambah). Kedua-dua kaedah pengisihan ini tidak begitu cekap Hormati masa, tetapi ia mudah difahami. Kedua-dua kaedah memerlukan masa O(n2). Jumlah masa, di mana n ialah saiz input. Isih buih boleh dibuat dengan lebih pantas dengan cara yang mudah Semak jika tiada pertukaran dalam mana-mana fasa, fasa berturut-turut seterusnya tidak akan berlaku Tukar apa sahaja.

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